The Drawing Challenge - a problem I made up and can't solve! I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be $\sf{NP}$-Complete.

I created a programming challenge type description to encourage my CS friends to have a go at it.

Charlie likes to draw.

He’s given a piece of paper of width $W$ and height $H$ and a list of $N$ numbers $a_1, a_2, a_3, ... a_N$

For each number, he wants to draw a rectangle on the piece of paper. If the rectangle has width $w$ and height $h$ then  $w > 0, h > 0, w \geq h$ and $w \leq W$ and $h \leq H$. Both w and h must be positive integers.

If a number $a_x > a_y$, then $a_x$’s rectangle must have area bigger or equal to $a_y$’s rectangle, where area is $w*h$. If $a_x = a_y$, then they can have different areas.

Charlie doesn’t like to waste ink. For a rectangle of width $w$ and height $h$, he must draw a line of length $2w + 2h$, using $2w + 2h$ units of ink. Clarification: even if two rectangles are adjacent, the adjacent side must be drawn twice.

What is the least units of ink that Charlie can use, drawing one rectangle for each number on the piece of paper, such that no rectangles overlap and the whole paper is covered by rectangles?

Input File:
Line 1       : The width W and height H of the piece of paper, separated by spaces
Line 2       : N, the number of numbers to draw
Lines 3..N+2 : One number on each line.

Constraints:
W and H are positive integers <= 1000
N is a positive integer <= W * H
ax, where 1  <= x <= N, is a positive integer <= 1000

Output file:
A single line containing the least units of ink Charlie can use.

Bonus:

Output, for each number ax, the position and size of its rectangle on the piece of paper for a solution that uses the least amount of ink (there can be more than one).

Sample input file:

2 2
4
1
1
1
1

Sample output file:

16

Sample bonus:

-----
| | |
-----
| | |
-----

As pointed out by Marzio, here's the decision problem version:

Given a $W × H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn, filling the entire paper, as described above?

A closely related problem is strongly NP-hard.

Leung et al. [1] prove that the following decision version of your problem is strongly NP-complete, by reduction from 3-Partition.

  Is it possible to pack $n$ squares of given widths $w_1, w_2, \dots, w_n$ into a larger square of width $W$?

I misread the original question as a generalization of the following decision problem:

  Is it possible to pack $n$ rectangles with given areas $a_1, a_2, \dots, a_n$ into a $H\times W$ rectangle?

The first problem can be reduced to the second as follows: Squares with widths $w_1,\dots,w_n$ can be packed into an outer square of width $W$ if and only if the minimum-perimeter packing of rectangles with areas $w_1^2, \dots, w_n^2$ into a $W\times W$ rectangle uses precisely $4\sum_i w_i$ units of ink.  (Proof: The minimum-perimeter rectangle with any given area is a square.)

However, this reduction does not imply that the actual posted question is NP-hard.

Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin.  Packing squares into a square.  J. Parallel and Distributed Computing 10(3):271–275, 1990.


Best known asymptotic PCP sizes / 3-SAT What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs?  Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am especially interested in inapproximability of 3-SAT.

Let 7/8+ε-3-SAT be 3-SAT with the promise that if 7/8+ε fraction of the clauses are satisfiable, then the instance is satisfiable.  What are the best known reductions of 3-SAT with $n$ clauses to 7/8+ε-3-SAT?  For example, is there a reduction using $O(n \log n)$ clauses? ($O(n)$ clauses is an open problem.)  A reduction in uniform quasilinear size NC?  What is the dependence on $ε$, including when $ε→0$? Is there a known linear size (dependent on $ε$) reduction of (1-ε)-3-SAT to 7/8+ε-3-SAT, and if not, do we have better bounds for (1-ε)-3-SAT?  Even a partial answer would be interesting.

Also, while it would perhaps make the question too broad, I should mention that another important issue here are the constant factors, which due to techniques like the long code are commonly infeasibly large.

The state-of-the-art for PCPs that yield a reduction to $(\frac{7}{8}+\varepsilon)$ 3-SAT (even for sub-constant $\varepsilon$) are those of Dana Moshkovitz and Ran Raz, which have length $n^{1 + o(1)}$. I do not know, however, if anyone tried to compute the exact dependence of the length on $\varepsilon$, or the computation complexity of the reduction. Their main technical result was simplified later by Irit Dinur and Prahladh Harsha.

If you are interested in short PCPs with a constant number of queries that do not necessarily give optimal hardness-of-approximation reductions (a.k.a. "high-error PCPs"), then the state-of-the-art result is PCPs of length $n\cdot \mathrm{poly}\log n$ due to Eli Ben-Sasson and Madhu Sudan and its improvement by Dinur. Again, I do not know if anyone what is the exact complexity of computing the reduction.


Complexity of testing if a hypergraph has generalized hypertreewidth $2$ A hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of hyperedges, i.e., subsets of $V$.

The generalized hypertreewidth (GHW) parameter is a measure of the cyclicity of a hypergraph which is a variant of its treewidth. Intuitively, it is like a tree decomposition but the width of each node is counted as the number of hyperedges required to cover it. Formally, a hypertree decomposition of a hypergraph is defined as a tree $T$ where each node $b \in T$ is labeled by some vertices $V(b) \subseteq V$ and $E(b) \subseteq E$. We that $T$ is a tree decomposition of $H$, namely, we impose the following on the vertex mapping:

for each hyperedge $e \in E$, there is a node $b \in T$ such that $e \subseteq V(b)$
for each vertex $v \in V$, the set $\{b \in T \mid v \in V(b)\}$ of the vertices where $b$ occurs is a connected subtree of $T$.

Further, we require the following on the edge mapping:

for each node $b \in T$, the hyperedges $E(b)$ cover $V(b)$, i.e., $V(b) \subseteq \bigcup_{e \in E(b)} e$.

The width of the decomposition $T$ is the maximum, over $b \in T$, of $|E(b)|$. The GHW of $H$ is the smallest $k$ such that $H$ has a generalized hypertree decomposition of size $k$.

My question is: Do we know the complexity of testing, given an input hypergraph $H$, whether it has GHW $\leq 2$?

It is known that testing whether an input hypergraph has GHW $\leq 3$ is NP-hard [GMS 2007] and having GHW $=1$ is tractable because it is equivalent to being $\alpha$-acyclic as mentioned in [GGS 2014] and this is testable in linear time. I did not find any reference about whether having GHW $\leq 2$ is also tractable, or if it is already hard.

Georg Gottlob, Zoltán Miklós, and Thomas Schwentick, "Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants", 2007
Georg Gottlob, Gianluigi Greco, and Francesco Scarcello, "Treewidth and Hypertree Width", 2014

We do not know (to best of my knowledge).


How hard is the Circuit Isomorphism problem? Given two circuits, how hard is it to tell if they represent the same function? Clearly, this must be at least as easy as Graph Isomorphism since you can represent any circuit as a graph.

As pointed out by @Marzio De Biasi, the problem you are asking about is $\mathsf{coNP}$-complete, by a direct reduction from TAUTOLOGY: given a boolean formula $\varphi$, is $\varphi$ equivalent to the constant 1 circuit? It is easily seen to be in $\mathsf{coNP}$. (Given that Marzio really answered the question, I suggest anyone thinking of upvoting this answer flip a coin and if it lands heads then go vote for one of Marzio's other answers.)

Let me also clarify: the problem you are asking about is more typically called Circuit Equivalence. Circuit Isomorphism is the problem: given two circuits $C_1, C_2$ on $n$ inputs, is there a permutation $\pi \in S_n$ such that $C_1(\vec{x})$ and $C_2(\pi(\vec{x}))$ are equivalent? Circuit Isomorphism has a status similar to that of Graph Isomorphism, but one level higher in $\mathsf{PH}$: it is $\mathsf{coNP}$-hard (by the same reduction above), not known to be in $\mathsf{coNP}$, in $\mathsf{\Sigma_2 P}$, but not $\mathsf{\Sigma_2 P}$-complete unless $\mathsf{PH} = \mathsf{\Sigma_3 P}$.


Polynomial algorithms for UPB (Unextendable Product Bases) Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle$ such that:

a) all $\vert v_i \rangle$ are mutually orthogonal

b) there is no product vector orthogonal to all $\vert v_i \rangle$

c) basis is nontrivial, i.e. doesn't span $H$

(such bases are of interest in quantum information)

Questions:

Is there a polynomial algorithm (in $n$) for finding UPBs? (note that in general there is no upper bound on the size of UPB, so a priori it might be exponential in $n$)
Is there a polynomial algorithm for checking if a given product basis is a UPB? (i.e. is unextendable)

Or is the problem NP-complete?

I'm a little baffled by question (1). An unextendable product basis exists in $H_1 \otimes H_2 \otimes \ldots \otimes H_n$ if $n\geq 3$ or if $n=2$ and $\dim H_1, \dim H_2 \geq 3$. In all of these cases, it is straightforward to find one.

For question (2), the question is equivalent to checking whether there is a tensor product state in the subspace which is the complement of the space spanned by the basis. Leonid Gurvits has shown that checking whether a general subspace contains a tensor product state is NP-hard, so I suspect that it is hard in this case as well.


Most efficient way to convert an $\text{AC}^0$ circuit to a circuit  (of any depth) with gate fanout 1 EDIT (Aug 22, 2011):

I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts of the original question that are no longer relevant. (Thanks to Stasys Jukna and Ryan O'Donnell for partially answering the original question!)

Background:

Given an AC0 circuit with depth k and size S, there exists another AC0 circuit computing the same function with depth k and size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. In other words, the circuit looks like a tree (except at the inputs, since the inputs may fanout to more than one gate). One way to do this is by duplicating all the gates that have fanout > 1 until all gates have fanout = 1.

 But is this the most efficient way to convert AC0 circuits to AC0 circuits with fanout 1? I read the following in Lecture 14 of Ryan O'Donnell's course notes:

  Suppose C is any depth-k circuit of size S which computes Parity. It
  is an exercise to show that C can be converted into a leveled  depth-k
  circuit, where the levels alternate AND and OR gates, the inputs wires
  are the 2n literals, and each gate has fan-out 1 (i.e., it’s a tree) —
  and the size increases to at most $(2kS)^2 \leq O(S^4)$.

  Footnote: Actually, this is a slightly tricky exercise. It’s easier if
  you only have to get size $O(S^k)$, which is almost the same for our
  purposes if you think of k as a “constant”.

Does this mean there is a way to take any depth k AC0 circuit of size S and convert it to an AC0 circuit with fanout 1, depth k and size $(2kS)^2$? If so, how is this done and is this the best-known method?

Original Question:

  Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to an AC0 circuit of depth k and gate fanout 1? Are there any lower bounds known for this?

Newer, simpler question:

This question is a relaxation of the original one where I don't insist that the resultant circuit be constant depth. As explained above, there is a way to convert an AC0 circuit with depth k, size S into a circuit with size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. Is there a better construction?

  Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to a circuit of any depth with gate fanout 1?

I will try to summarize my previous comments.

Let us first ignore the fact that your original circuit has (constant) depth $k$; just assume it has size $S$. Let $A$ be the smallest number such that every unbounded fanin circuit size $S$ can be transformed into an unbounded fanin formula $F$ of size $O(S^A)$. I claim that the best we can do so far is to achieve $A=O(S/\log^2 S)$. Say, it is even not known whether whether any (fanin-2) circuit of size $S=O(n)$ can be simulated by a formula of size smaller than $\exp(n/\log n)$.

To show the claim, we transform the formula $F$ into a fanin-2 formula $F′$ of size $M=O(S^{2A})$. It is well known that the depth $D$ of every formula $F′$ can be made logarithmic in its size, that is $D=O(\log M)=O(A\log S)$. [This was first shown by Khrapchenko 1968, and then the constant under big-O was improved to $D\leq 1.73\log_2M$ by several authors.] On the other hand, the best known result for fanin-2 circuits [Paterson and Valiant, TCS 2(3), 397-400] says that $Depth=O(Size/\log Size)$. Thus, having a simulation with $A$ much smaller than $S/\log^2 S$ would improve the best known Size-Depth simulation for circuits.

This, however, is only a "word of caution" - it does not answer your question because you assume that your original circuit has constant depth $k$, implying that in this case we can just take $A=k$ (or $A=k−1$ if we have a single output gate). The power of Paterson-Valiant simulation is that it applies to arbitrary, even very unbalanced circuits whose depth is almost the entire size! But in your bounded-depth setting, even the case $k=3$ is not clear: can every depth-3 circuit of size $S$ be transformed into a depth-3 formula of size much smaller than $S^2$? I guess the answer should be "no" (could be an interesting exercise for students). A depth-3 formula is just a big OR of CNFs. The question is to find an OR of CNFs that share many clauses in common, but otherwise are "very different" to force a large depth-3 formula.

The problem is that we want to obtain a formula (a fanout-1 circuit). As was pointed above, allowing gates of fanout-2 makes simulation simpler: Hoover, Klawe and Pippenger [JACM 31(1), 1980] show that any fanin-2 circuit of size $S$ and depth $D$ has an equivalent fanin-2 and fanout-2 circuit of size $3S−2n$ and depth $2D$. Thus, if fanin is unbounded, then the resulting circuit will have size $O(S^2)$ and depth $O(D\log S)$.

There is yet another result somehow related to your question. Lozhkin (1981) proved that if a boolean function $f$ can be computed by an $AC^0$ formula of depth $k$ and size $S$, then $f$ can be computed by fanin-2 formula of depth $D\leq k-1+\lceil\log_2S\rceil$ (this follows from Theorem 6.2 in my book). Note that a trivial upper bound would only be $D\leq k\log S$ (if we would simulate each single gate by a tree of depth $\log S$).


Reference for the shortcomings of Google's PageRank algorithm? Sometimes, when using Google search, you don't immediately get quality results to your query. It is seems that PageRank algorithm gets distracted by widely used keywords that have different meanings and uses. Therefore, you need to spend extra time and possibly use different keywords to refine the search context.

  Is there a good reference that addresses the PageRank algorithm's shortcomings? Is there a contextual search algorithm?

to answer your specific question, there are many papers that discuss PageRank mathematically, such as:

Deeper Inside PageRank, (A. N. Langville and C.D. Meyer), Internet Mathematics (1), 335–400 (2004)

and in each one you might find discussion of computational and operational issues (computing it faster, using memory more efficiently), but I don't know of any that stand out as addressing shortcomings of -results- specifically.
to answer what you're getting at ("why does google not give me what I want without trying?")

google search does not equal PageRank (though PR is a major part of it)
PageRank itself doesn't address lexical ambiguity
Google's additions try to address multiple meanings of words (different meanings under different contexts), and synonyms (other strings that mean the same thing); they're not perfect, but more and more they are being addressed.


Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation What is the complexity of deciding whether an $\mathsf{NC}^0$ circuit
with $n$ input bits and $n$ output bits computes  a permutation
of $\{0,1\}^n$? in the other words, whether every bit strings in
$\{0,1\}^n$ is an output of the circuit for some input?
It looks like a problem which has been studied,
but I cannot find any references.

Hardness

Following your comment on the question, we will call a circuit where each output bit depends on at most k input bits a “NC0k circuit.”  Using this term, your problem is coNP-complete in case of NC05 circuits.  That is, the following problem is coNP-complete.

Instance: A Boolean circuit C with n input bits and n output bits where each output bit depends on at most five input bits.
Question: Is the mapping from {0,1}n to itself computed by C bijective?

As Kaveh commented, it is clearly in coNP, even without the bound on the number of input bits on which each output bit depends.  To prove the coNP-hardness, we will reduce 3SAT to the complement of the current problem.  The key idea of the reduction is the same as the one used in the paper [Dur94] by Durand, which I mentioned in a comment on the question, but the whole reduction is much simpler in our case.

Given a 3CNF formula φ with n variables and m clauses, we construct a Boolean circuit C with (n+m) input bits and (n+m) output bits as follows.  We label the input bits as x1, …, xn, y1, …, ym, and the output bits as x′1, …, x′n, z1, …, zm.  We consider that the input bits x1, …, xn specify a truth assignment to the n variables in φ.

x′i = xi for 1≤i≤n.  That is, the first n bits of input are always copied to the first n bits of output.
For 1≤i≤m, if the ith clause of φ is satisfied, then zi = yi ⊕ yi+1, where the subscript is interpreted modulo m.  Otherwise, zi = yi.

Note that each output bit depends on at most five input bits.  I omit the proof of the correctness of the reduction, but the key idea (which I borrowed from [Dur94]) is that if φ is satisfiable and input bits x1, …, xn are set to a satisfying assignment of φ, then the m output bits z1, …, zm are constrained to have the even parity, and therefore the circuit cannot be a permutation.  On the other hand, if input bits x1, …, xn are set to a non-satisfying assignment of φ, then output bits z1, …, zm can be set to anything; because of this, if φ is unsatisfiable, then the circuit is a permutation.

Tractability

On the tractable side, your problem is in P in case of NC02 circuits.  This is shown as follows.  In general, each output bit in a Boolean circuit for a permutation is balanced; i.e., exactly half of the input strings set the output bit to 1.  However, every balanced Boolean function from {0,1}2 to {0,1} is affine; i.e., a copy of a single input bit, the XOR of the two input bits, or the negation of them.  Therefore, we can first check that each output bit is balanced, and then check the bijectivity by the Gaussian elimination.

I do not know the complexity in case of NC03 circuits or in case of NC04 circuits.

References

[Dur94] Bruno Durand.  Inversion of 2D cellular automata: some complexity results.  Theoretical Computer Science, 134(2):387–401, Nov. 1994.  DOI: 10.1016/0304-3975(94)90244-5.


Finding the sparsest solution to a system of linear equations How hard is it to find the sparsest solution to a system of linear equations?

More formally, consider the following decision problem:

Instance: A system of linear equations with integer coefficients and a number $c$.

Question: Does there exist a solution to the system with at least $c$ variables assigned to zero?

I'm also trying to determine what the dependence is on $c$.  That is, maybe the problem is FPT with parameter $c$.

Any ideas or references are really appreciated.

Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$

Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn \times (kn+m)$ matrix, $\tilde{x}$ is now a $(kn+m)$ dimensional vector, and $\tilde{b}$ is a $kn$ dimensional vector:

$$\tilde{A} = \begin{bmatrix}
 A & I_n & &  & \\
 & I_n & -I_n & & \\
 & & I_n & -I_n & \\
 & & & \ddots &\ddots  \\
 & & & & I_n & -I_n \\
\end{bmatrix}, \tilde{b} = \begin{bmatrix} b \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$
where $I_n$ is the $n \times n$ identity matrix.

Note that this system is always satisfied by the vector $\tilde{x} = \begin{pmatrix} 0 & b & b & \cdots &  b \end{pmatrix}^T$. In fact, the first $m$ entries of $\tilde{x}$ can be arbitrary, and there is some solution vector with that prefix.

I now claim that $\delta$ fraction of equations of $Ax=b$ are satisfiable iff there exists a sparse solution of $\tilde{A}\tilde{x}=\tilde{b}$ which has at least $\delta nk$ zeros. This is because every satisfied row of $Ax=b$ yields $k$ potential zeros when $x$ is extended to $\tilde{x}$

Thus, if we find the sparsity of the sparsest solution to $\tilde{A}\tilde{x}=\tilde{b}$, we have also maximized $\delta$, by dividing the sparsity by $k$.

Therefore, I believe your problem is NP-hard.


Relation between Code Length and Symbol Weight in a Huffman Code I'm not sure if I should ask this here or over at StackOverflow (sorry if this is not the right place).

I'm constructing a Huffman code for a series of symbols with associated weights. I have a list of the code-lengths corresponding to each symbol, sorted by symbol weight (in non-decreasing order). Does it follow that this list is also sorted by code-length (in non-increasing order)?

I suspect that the answer is yes (since lower-weighted symbols will generally have shorter code lengths), but I'm not sure if this is guaranteed.

I guess what I really want to know is, "if a Huffman tree has two leaves a and b, where a had a higher weight than b, is b's code length always at least that of a's?"

Thanks!

Yes. A Huffman code is optimal. If a less frequent symbol had a shorter code length than a more frequent symbol, then you could get a code with better performance by exchanging them.


Number of simple paths between two vertices in a DAG Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$.

My problem is: how many simple $s-t$ paths exist on this DAG?
Most precisely, how can we write a function on the number of nodes $|N|$ which is an upper bound for the number of simple $s-t$ paths in $G$?

I'm aware that exists a polynomial-time dynamic programming algorithm that counts the number of such paths (see here) and that is an enumeration problem. This algorithm is #P-Complete on general digraphs, but is in $P$ for DAGs, as pointed out by @Joshua Grochow in the comments.

I'm also aware that this number is exponential on the size of the longest $s-t$ path.
However, I don't see a relation between this function and the number of nodes in the graph.

Thanks in advance :)

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through those vertices in the same order given by the topological order. So (since $s$ and $t$ must always be included) there are at most $2^{n-2}$ paths.

This bound is tight, for a complete DAG (one in which every pair of vertices is connected by an edge, oriented consistently with a single topological order).


What's the relationship between "free theorems" and "free objects" What's the relationship between free theorems and free objects from algebra. They seem quite similar. I'm wondering if there's an underlying principle here.

There is no relationship.  They both use the word "free", but with different meanings of the word "free".  It's just an accidental collision, which will happen when you have a language like English with a fixed number of words and the number of concepts we want to talk about exceeds the number of words in the language.

A free group is, roughly, a group that is about as generic as possible (it has no special structure).  Here, the word free means "having no non-trivial strucutre", i.e., free of special equalities.

In contrast, a free theorem about some code (e.g., a function) is one that follows automatically from the type signature of that code.  Here, the word free means "at no cost" or "with no extra reasoning about the code required"; it's an automatic consequence of the type signature, regardless of the implementation/code of the function.


Number of subgraphs with given edge parity I would like to know whether counting number of induced (full) subgraphs (of an undirected graph) that have even number of edges is P or #P-complete. Additionally, is the problem easier if we assume that given undirected graph has constant degree (all vertices have up to k incident edges)?

This problem is tractable.

Let $G = (V,E)$ be the input graph with $|V| = n$ and let $e$ and $o$ be the number of vertex-induced subgraphs of $G$ with an even and odd number of edges respectively. Of course, $e + o = 2^n$. In polynomial time, we can compute $e - o$, which I explain below.  With two equations and two unknowns, we can solve the linear system to determine the value of $e$.

From $G$, we create an instance of a counting constraint satisfaction problem (#CSP). Every vertex in $V$ is a Boolean variable and every edge in $E$ a constraint $f$ that depends on its incident vertices. The constraint $f$ evaluates to 1 unless the both vertices are assigned 1, in which case, $f$ evaluates to -1. The symmetric notation for this constraint is $[1,1,-1]$.

Now the answer to this #CSP instance is (by definition)
$$\sum_{\sigma : V \to \{0,1\}} \prod_{e \in E} f(\sigma|_{I(e)}),$$
which is a sum over all vertex subsets, the product of the outputs of every constraint $f$, where $I(e)$ is the vertices incident to $e$ and $\sigma|_{I(e)}$ is the restriction of $\sigma$ to $I(e)$.

Fix a subset of $V$. Assigned 1 to the vertices in the subset and 0 to the vertices not in the subset. If either vertex incident to the same edge is assigned 0, then this edge is not in the vertex-induced subgraph and the constraint $f$ on this edge contributes a 1 to the product, which has no effect. If both vertices incident to the same edge are assigned 1, then this edge is in the vertex-induced subgraph and the constraint $f$ on this edge contributes a -1 to the product.

Vertex-induced subgraphs with an even number of edges contribute a 1 to the sum while vertex-induced subgraphs with an odd number of edges contribute a -1. Thus, the answer to this #CSP instance is exactly $e - o$.

Since the constraint $f$ is affine, this #CSP is tractable. The polynomial algorithm for any set of affine signatures is given in The Complexity of Complex Weighted Boolean #CSP by Jin-Yi Cai, Pinyan Lu, and Mingji Xia. There may be a simpler algorithm for this particular case. If such an algorithm is known, it is probably contained in one of the references cited in the above paper.


Relativized world where $L^A=NP^A$ I wonder1 whether there is a known relativization barrier against proving $L\neq NP$. Hence I'm looking for a language $A$ for which $L^A=NP^A$.

My first idea was to try $A:=SAT$, but then I thought that $L^A\subset P^A = \Delta_2^P$ and $NP^A=\Sigma_2^P$. This seems to disqualify not only $A:=SAT$, but any complete problem $A$ from the polynomial hierarchy for my purpose.

My next idea was to try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide true quantified Boolean formulas. But $P^A=NP^A$ is well known, and $L^A=NP^A$ is a stronger statement, so $L^A=NP^A$ would be well known, if anybody had proved it.

  My question is just whether there is a known relativization barrier. We certainly can't prove that such a language $A$ can't exist, because otherwise we would get $L\neq NP$ as corollary.

 1. I know that logarithmically space bounded TMs with stack recognize exactly the languages from $P$, independent of whether the TM is deterministic or not. I don't know whether this result relativizes, but I guess it does. So I wonder whether there can be a language $A$ with $NL^A=P^A$. But asking for $L^A=NP^A$ instead seems easier, because of the connection to the polynomial hierarchy.

My question is just whether there is a known relativization barrier.

Yes, there is a known relativization barrier. It's given by $A:=TQBF$, because Emil Jeřábek (see comments) is right: the statement that $TQBF$ is $PSPACE$-complete under logspace many-one reductions is well known.

Emil Jeřábek's remark "(or even uniform $\mathbf{AC}^0$)" seems less relevant, because $\mathbf{AC}^0$ is easily separated from $L$ (or even uniform $\mathbf{NC}^1$). Because the resulting formula actually depends only very locally on the input for the $PSPACE$-Turing machine, one could even claim that $TQBF$ is $PSPACE$-complete under $L$-uniform $\mathbf{NC}^0$ (instead of uniform $\mathbf{AC}^0$). But I find this misleading, because the circuit doesn't really do any non-trivial work at all, it basically just writes down a template.

(The reduction writes down $n^k$ times $\exists c_{1.5}\forall (c_3, c_4) \in \{(c_1, c_{1.5}), (c_{1.5}, c_2)\}$ with systematically varying indices, where each $c_i$ are actually $n^k$ Boolean variables. This entire part only depends on the length of the input, hence the corresponding output variables are hardwired to constants. The final formula could be written as $\forall z. (z_1=i_i\land\dots\land z_n=i_n)\land \phi(x,y,z)$ such that only $i_i,\dots,i_n$ depends on the actual input, and such that this is the only place where $i_i,\dots,i_n$ appear. So this is nearly trivially an $\mathbf{NC}^0$, the entire work has been done by the $L$-algorithm writing down the circuit, whose outputs are nearly all directly hardwired to constant.)


Space complexity of integer programming Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x_1,\dots,x_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a deterministic algorithm that runs in $O((nk)^{ck})$ time for some $c>0$. What is the space complexity of the algorithm? Does it run in polynomial space?

According to this answer, "the space complexity of the algorithm" is polynomial when  2.5 < c .

That answer does not indicate the polynomial's exponent.


Encrypting or obfuscating transport stream identifiers in SSL-like connections First, a longish prologue.

Assume typical SSL/IKE/SSH-like connections where a Diffie-Hellman exchange is done first to establish session encryption and decryption keys, where those keys are subsequently used for all transmission in the connection, with a symmetric encryption algorithm, such as AES. Also assume that a single peer has many separate connections, with separate symmetric keys.

If the connections are not separated by other external means (such as TCP connections), a peer receiving a packet needs some way to distinguish which connection a packet belongs to, to know which symmetric keys to use for decrypting it.

This is obviously trivially handled by prefixing each message by a connection id (that is not cryptographically significant). This is the approach taken by IPSEC, for example (security association id, 32-bit integer).

And, here comes the question:

What would be a method to encrypt the connection id in such a way, that nobody else but the recipient can tell which packets belong to which connection?

The simple solution would be to encrypt the connection id with an asymmetric encryption method for the recipient's public key, and prefix this block to each message. However, this solution is computationally too expensive to be done per packet, atleast with the traditional methods of asymmetric encryption (RSA, ElGamal, Elliptic Curves, etc.).

An incomplete solution would be that the recipient server has one shared connection id encryption key, which is revealed to each communicating party inside the Diffie-Hellman handshake. This way, no passive attacker can know which packet belongs to which connection - but every party in active communication with the recipient has the same shared symmetric encryption key, and can tell all the connections apart.

Yet another solution would be for the recipient just to trial decrypt each packet with every symmetric key it has, and see which decryption produces a valid authenticator for the packet. But this becomes computationally too expensive, if the recipient has more than a few connections.

So, my question is really - are there any other methods I haven't thought of that could be used for the purpose? There are all sorts of funky encryption methods one could use, such as homomorphic encryption, but I haven't really come up with anything solid. Or is this problem a straight case of asymmetric encryption (or trapdoor function), for which there are no sufficiently fast solutions?

Or, if such a method can not be found, then I would like to find a simple obfuscation method, that wouldn't really give any guarantees, but which would make it hard for an attacker to determine the connection identities from just a few packets.

Use a variation on your shared secret-key encryption proposal: Every packet has an encrypted header for which the plaintext is the connection ID concatenated with the packet sequence number. After successfully receiving a (connection, n) packet, the next packet received on that connection will be (connection, n+1). Store the encryption of (connection, n+1) in a hash table and remove the expired entry for (connection, n). When receiving a packet, do a hash table lookup using the packet's encrypted header word to find out its associated connection. Obviously for this to work, sender and receiver must use synchronized ciphers (e.g. a stream cipher initialized with a negotiated IV and the shared secret key).

You can easily extend this algorithm to deal with longer sliding windows by adding hash table entries for sequence numbers n through n+k. The space cost is O(mk) where m is the number of open connections and k is the length of the sliding window.


What is the space complexity of calculating Eigenvalues? I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space complexity" part meaning work space complexity,
rather than time complexity since it is easier to trace time results.
I appreciate any reference in the matter.

Thanks.

The decision versions of many common problems in linear algebra over the integers (or rationals)
are in the class $\mathsf{DET}$, see the paper

Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)

$\mathsf{DET}$ is contained in $\mathsf{DSPACE}(\log^2)$.

Computing the eigenvalues is a little more delicate:

1) In $\mathsf{DSPACE}(\log^2)$, one can compute the coefficients
of the characteristic polynomial.

2) Then you can use the parallel algorithm by Reif and Neff
to compute approximations to the eigenvalues. The algorithm runs on
a CREW-PRAM in logarithmic time with polynomially many processors,
so it can be simulated with poly-logarithmic space.
(It is not explicitely stated in the paper, but their PRAM should to be
log-space uniform.)
The space used is
 polylogarithmic in the size of
the input matrix and the precision $p$. Precision $p$ means that
you get approximations up to an additive error of $2^{-p}$.

This is a concatenation of functions computable in poly-logarithmic space.
(Output tapes are write only and oneway.)

C. Andrew Neff, John H. Reif: An Efficient Algorithm for the Complex Roots Problem. J. Complexity 12(2): 81-115 (1996)


Where is relational parametricity in hyperdoctrine or topos models explored? Reynolds originally proposed a relational semantics for the second order polymorphic lambda calculus[1].  However he later showed[2] that this approach was inconsistent with classical  set theory.  Pitts described the framework of hyperdoctrine models and topos models[3] which are consistent with constructive logic.

Presumably relational hyperdoctrine and topos models were then developed.  Where can I read about them?

[1] Types, abstraction and parametric polymorphism
[2] Polymorphism is not set-theoretic
[3] Polymorphism is set theoretic, constructively

For technical reasons, there hasn't been much work on parametric topos models. The internal logic of a topos is a form of set theory, and F-style impredicative indexing and the powerset axiom are incompatible. See Andy Pitts's Non-trivial Power Types Can't Be Subtypes of Polymorphic Types:

  This paper establishes a new, limitative relation between the polymorphic lambda calculus and the kind of higher-order type theory which is embodied in the logic of toposes. It is shown that any embedding in a topos of the cartesian closed category of (closed) types of a model of the polymorphic lambda calculus must place the polymorphic types well away from the powertypes, P(X), of the topos, in the sense that P(X) is a subtype of a polymorphic type only in the case that X is empty (and hence P(X) is terminal). As corollaries, we obtain strengthenings of Reynolds' result on the non-existence of set-theoretic models of polymorphism.

As a result, even though you can give a universe interpreting F's types in topos logic, you can't let it interact in interesting ways with the full universe of sets. However, all is not lost!

The fact that a (non-parametric) universe of sets interpreting System F means that you can give a parametric model of System F in the internal logic of the topos, much more easily than you can in ordinary set theory. Essentially, you don't have to muck around with PERs, since you can just assume that you have a suitable collection of sets. Bob Atkey used this idea in his paper Relational Parametricity for Higher Kinds, where he worked out parametricity for $F_\omega$ by working in the impredicative calculus of constructions.
Another reaction to Pitts's result is to not work with a set theory, but a dependent type theory. Since there's no power type former in dependent type theory, you don't have to worry about the interaction of power types and polymorphism. See Atkey, Ghani and Johann's A Relationally Parametric Model of Dependent Type Theory.

However there are no such obstacles to building hyperdoctrine-ish models, where terms of System F are objects of the logic. Research along these lines was probably initiated by Abadi and Plotkin in their seminal paper A Logic for Parametric Polymorphism. Lars Birkedal and his collaborators have worked heavily on formulating categorical models for this and similar logics --- see in particular Birkedal, Møgelberg, and Petersen's Category-Theoretic Models of Linear Abadi and Plotkin Logic, which gives a logic for reasoning about linear System F, plus a proof that it is sound and complete with respect to a certain class of categorical models.


Self-intersecting walk in expander graphs Consider a random walk in an expander graph.
How much time it typically takes to visit the same vertex twice.
It seems to me that it should be something between $\sqrt{n}$ to $\sqrt{n}\log n$.
Is there any reference on this or similar things

I think only knowing the graph is an expander does not fix the value you are asking. If you are doing random walk naively then when the graph has bounded degree there is constant probability that the walk will reach the same vertex after just 2 steps, and therefore the expected number of steps is constant.

I guess you want to exclude that case by saying the random walk cannot take the same edge in two consecutive steps. But still there are different cases here: if we take the union of a degree 4 expander graph and a grid, it will still be an expander (with worse parameters), but there is constant probability that the walk return to the same position in 4 steps, and therefore the expected number of steps is again constant. On the other hand, if we take a random graph, since the girth is high the expected number (or in fact the minimum) of steps for any vertex to be revisited will be super-constant.

$\sqrt{n}\log n$ is definitely a safe upperbound because of the birthday paradox argument. I guess the answer for random graphs might be $\sqrt{n}$, because if you take a random walk of length significantly smaller than $\sqrt{n}$, with good probability the induced subgraph will be just the path and do not have more edges. In general if the induced graph on the set of visited vertices has a lot of edges outside the path, it means the walk "had many chances" to visit some vertex twice.

I understand this may not answer your question completely but I couldn't figure out how to leave a comment like Suresh Venkat did.


Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths? This is a question about nonuniform circuit families that's kind of bothering me. Let $\lbrace C_n \rbrace$ be a family of circuits for a language $L$ such that for inputs $x$ of length $n$, $C_n(x) = L(x)$. This implies that $C_n$ has to answer correctly on all inputs of the form $0y$, where $|y| \leq n-1$, right? In that case, that implies that in specifying a circuit family $\lbrace C_n \rbrace$, you can leave out arbitrary long (but finite) sequences of circuits in this (infinitary) "description", and you wouldn't have lost any part of your description.

I'm sure this is not profound in the slightest, but it does seem strange to me - that for each $n$, the circuit $C_n$ subsumes all of the $C_k$ for $k < n$.

Although families of circuits aren't usually defined this way, you actually could require this for non-uniform families of circuits; i.e., require circuit families to be consistent. There still would be circuit families for non-uniform languages, and P/poly would still contain all the same languages with this definition (P/log would change, though). Then you could indeed leave out any finite number of circuits, and the function would still be well-defined.
You wouldn't cause any paradoxes.

One question you could ask is: are there any advantages to this alternate definition of P/log? My guess is that there are.


A subset lookup algorithm Suppose I have a list $\cal X$ of subsets of $\{1, ..., n\}$. I can do preprocessing on this list if necessary.  After this preprocessing, I am presented with another set $A \subseteq \{1, ..., n \}$. I want to identify any sets $B \in \mathcal X$ with $B \subseteq A$.

The obvious algorithm (without any preprocessing) takes time $O(n |\cal X|)$ -- you simply test $A$ against each $B \in \mathcal X$ separately. Is there anything better than this?

If it helps, you can assume that, for any $A$, the total number of matches $B \in \mathcal X$ is bounded by something like $O(1)$.

This is not an answer. It is a simple but long observation. I hope it will be useful.

The decision version of your problem is: Does $\cal X$ contain a subset of $A$?

This problem is related to the problem of evaluating monotone boolean functions of $n$ variables. A subset of $\{1,\ldots,n\}$ is equivalent to an $n$-bitstring, so the family $\cal X$ is equivalent to a boolean function $f$ of $n$ variables. Given a function $f$, one can define the least monotone function that is not bigger than $f$, namely $g(y)=(\exists x\subseteq y,\,f(x))$. The original problem is then reduced to evaluating $g(A)$. Conversely, the problem of evaluating a monotone boolean function can be reduced to the original problem, either naively by taking $f=g$ or by choosing an $f$ that makes $\cal X$ smaller.

In practice BDDs tend to work well. So one possible approach is to build the BDD for $f$, derive from it the BDD for $g$, and then evaluate $g$. The average size of the BDD for $g$ must be $\Omega\left(\binom{n}{n/2}\right)$, because there are many monotone boolean functions. Hence, in theory this is a bad solution.

But (1) a better analysis might be possible and (2) there might be tweaks to this approach that make it better. For example, I didn't use in any way the correlation between the size of $\cal X$ and the size of $g$'s BDD. (There must be a correlation, but I don't know if it is simple or usable here.)

For completeness, a simple algorithm for computing the BDD for $g$ from the BDD for $f$ is the following.
$$m(x?f_1:f_0)=x?(m(f_0)\lor m(f_1)):m(f_0)$$
Here $\lor$ is the standard or-operation on BDDs.


How to compute Integer Hash of a string Is it possible to convert a string to a unique number.

Similar to any hashing algorithm (MD5, SHA-1 and SHA-2), I want to compute a unique integer value for an arbitrary length string, which should be collusion resistant, hard to invert, and easy to compute.

Can you name the technique to compute it, so that I can dig into the theory of it.

Some useful criteria for evaluating string hashing functions are discussed here:

Performance in Practice of String Hashing Functions
Choosing Best Hashing Strategies and Hash Functions
Evaluating Hash Functions
Hash Function properties

There's an empirical comparison of some popular string hashing functions here which looks at some of the criteria you mentioned. The appropriateness of various hashes would depend on the application and data characteristics. Uniformity and efficiency are usually the major concerns.

If you know the input set in advance, you can generate a perfect hash function that is collision-free. Something like CMPH or gperf can automatically generate a PHF for a set of strings.

If the input isn't known in advance, it still might be biased toward a particular distribution that makes one hash more favorable than other. Benchmarking can be useful.

For a cryptographically secure hash, you'd want something that has good avalanche effect characteristics.

Bernstein's hash is often used in string dictionary data structure implementations, but of course there are many to choose from. (Also MurmurHash.)

I misunderstood the question - this is for integers that are word-sized. For a secure crypto hash like SHA-2, see Kaveh's comments.


obvious property of big O, big Omega, and big Theta I'm trying to determine under what conditions the following statement is true.

The statement is, suppose $f(n) = O[g(n)]$ and $f(n) \neq \Theta[g(n)]$ then $g(n) = \Omega[f(n)]$

where $O$ means "asymptotically bounded above (not necessarily tightly) by", $\Omega$ means "asymptotically bounded below (not necessarily tightly) by" and $\Theta$ means "asymptotically bounded both above and below".

I can't seem to find it stated outright in any of the books or wikipedia articles.

I'm sure there are counterexamples where we can construct weird functions to contradict the statement, but I'm wondering whether the statement is true for all "ordinary" functions we "typically" encounter (of course, it would be necessary to rigorously define "ordinary" here).

EDIT: Now that I have fresh eyes in the morning, I see that I have thoroughly misread the question. The answer below applies to “if $f(n)\ne O(g(n))$, then $f(n)=\Omega(g(n))$”. As noted in comments above, the question as actually stated has a trivially true answer for all functions, that is, $f(n)=O(g(n))$ is equivalent to $g(n)=\Omega(f(n))$ immediately from the definition.

The answer is positive if $f$ and $g$ belong to a “well-behaved” family of functions which ensures that they are asymptotically comparable; in particular, if they are (restrictions to $\mathbb N$ of) functions taken from a Hardy field. For example, this holds if both functions are first-order definable (with parameters) in the real exponential field $(\mathbb R,+,\cdot,\exp)$, or in any o-minimal expansion of the real field for that matter.


Pair of vertex disjoint cycles in a directed graph What is the fastest known deterministic algorithm that can recognize directed graphs with a pair of vertex disjoint cycles? I know graphs with min outdegree three always have such a pair (Thomassen'83), but even so I cannot find an efficient algorithm in the general case. Does anyone know a reference for this?

According to Grohe and Grüber "Parameterized approximability of the disjoint cycle problem" (ICALP 2007) there is an algorithm for finding $k$ vertex-disjoint cycles in a digraph, in time $n^{f(k)}$ for some function $f$ (polynomial for fixed $k$ but not FPT) in the section 5 of Reed, Robertson, Seymour and Thomas, "Packing directed circuits" (Combinatorica 1996) (which in turn uses theorem 3 of "The directed subgraph hemeomorphism problem" of Fortune, Hopcroft, and Wyllie.)


The non-metric k-median problem It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic approximation algorithms for this problem?

In some real world applications, the cost function does not satisfies the triangle inequality even in a weak sense. Also, the constraint of not having more than $k$ medians cannot be violated and the above approximation ratio is the ratio of solution cost over optimal cost.

For the non-metric $k$-median problem, we can show a stronger inapproximability result than $O(\log n)$. The following is a stronger claim:
Main Claim: The non-metric $k$-median problem can not be approximated to any factor better than $n^{c}$, for any constant $c>0$.
Proof:
The proof follows from the reduction from the hardness of the max $k$ coverage problem. Given a universe set $U = \{1,\dotsc,n\}$ and subsets $S_{1}, \dotsc,S_{m}$ of $U$. It is NP-hard to distinguish between the following instances:

Yes Instances: There are some $k$ sets $S_{t_{1}},\dotsc,S_{t_{k}}$ that covers all elements in $U$.

No Instances: There does not exists any $k$ sets in $S_{1}, \dotsc,S_{m}$ that can cover more than $(1-\frac{1}{e}) \cdot |U|$ elements of $U$.

Reduction: Using an instance of the max $k$ coverage, we construct a $k$-median instance $(L,C)$ as follows. A location in $L$ corresponds to a subset $S_{i}$. And, a client in
$C$ corresponds to an element $e_{j}$. Let $f_{i} \in L$ denote a
location corresponding to $S_{i}$, and $x_{j} \in C$ denote a client
corresponding to an element $e_{j} \in U$. The distance between
$f_{i}$ and $x_{j}$ is $1$ if $e_{j} \in S_{i}$ and $\Delta$
otherwise. Here $\Delta$ is some value $\gg 1$.

Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a Yes Instance.
Completeness: We open facilities at the locations that corresponds to $S_{t_{1}}, \dotsc,S_{t_{k}}$. The cost of every client to the closest facility would be exactly $1$ since every element belongs to some $S_{t_{i}}$. Therefore, the $k$-median cost is at most $|U|$.
Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a No Instance.
Soundness: No matter where we open $k$ facilities, there always exist at least $\frac{1}{e} \cdot |U|$ elements that are left uncovered. In other words, there are at least $\frac{1}{e} \cdot |U|$ clients at a distance of $\Delta$ from any open facility. Therefore, the $k$-median cost is at least $\Delta \cdot \frac{1}{e} \cdot |U|$
The completeness and soundness analysis imply that the non-metric $k$-median problem can not be approximated to any factor better than $\Delta \cdot \frac{1}{e}$. Here, we can set $\Delta$ to any arbitrary large value $\gg n^{c}$ for any constant $c>0$. This completes the proof of the main claim.

Note that I could not find the above result in any literature. However, the above reduction is similar to the one used by Guha and Khuller where they take a distance of $1$ if $e_{j} \in S_{i}$ and $3$ otherwise. Using it they show the hardness of approximation for the metric facility location problem and other related problems.


How to constrain a finite automaton (NFA and DFA) to a tree? I have a finite automaton by the standard model Hopcroft & Ullman define:
$$
M = (Q, \Sigma, \delta, q_0, F)
$$

Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such that $\delta(q, a)$ is a state for each state $q \in Q$, the set of all states, and input symbol $a \in \Sigma$, the alphabet. That allows for $\delta$ to map to any element of $Q$. So that's a graph, although it's not described using the usual $G = (V, E)$ notation.

Without specifying any particular definition for $\delta$, I'd like to be able to write the constraint that $\delta$ may only define transitions which form a tree. How can that be expressed?

My thought is that I might say that $\delta$ must be recursive somehow (to give a tree shape), but I'm not sure how to go about that.

Thank you,

I think the easiest way of enforcing tree shape is the set of conditions

$q_0$ is not in the image of $\delta$,
$\delta$ is injective, and
$M$ is connected (to avoid isolated cycles). Note that this one is global, not local, which may be unavoidable.

Then we can prove (by induction) that for any state $q$ there is a unique path from $q_0$ to $q$.


Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem? Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem？ In other words, could the Tarski–Seidenberg theorem subsume Buchberger's algorithm and Wu's method?

Actually, algorithms of both Buchberger and Wu may be just deduced from variants of Hilbert's Nullstellensatz.

For Buchberger, it depends what you want it for, but generally speaking the answer is no. First, as pointed out on the Wikipedia article, the complexity upper bound given by Tarski-Seidenberg is horrendous, whereas Buchberger's algorithm is exponential space, which is optimal (since ideal membership is EXPSPACE-complete).

Second, Tarski-Seidenberg is for semi-algebraic sets over the reals (that is, allowing $\leq, <, =, \neq$), whereas Buchberger's algorithm works not only for the reals, but for polynomials over any field, or even over other rings (such as $\mathbb{Z}$). With minor modifications, Buchberger's algorithm even works in various noncommutative analogues of polynomial rings.

Third, Grobner bases (and hence, Buchberger's algorithm) can be used for many more things besides quantifier elimination. For example, intersecting ideals, quotienting ideals, computing syzygy modules of ideals, proof systems (hence algorithms) for Tautologies, coding theory, group cohomology, applying toric geometry to algebraic geometry (where we think of the initial ideal as a way of deforming an arbitrary variety into a toric variety, and thereby learn things about the original variety that are easier to deduce for the toric one), the list goes on...

(I am less familiar with Wu's method.)


Reference for (odd-hole,antihole)-free graphs? X-free graphs are those that contain no graph from X as an induced subgraph.  A hole is a cycle with at least 4 vertices.  An odd-hole is a hole with an odd number of vertices.  An antihole is the complement of a hole.

The (odd-hole,odd-antihole)-free graphs are precisely the perfect graphs; this is the Strong Perfect Graph Theorem.  It is possible to find the largest independent set (and largest clique) in a perfect graph in polynomial time, but the only known method of doing so requires building a semi-definite program to compute the Lovász theta number.

The (hole,antihole)-free graphs are called weakly chordal, and constitute a rather easy class for many problems (including INDEPENDENT SET and CLIQUE).

  Does anyone know if (odd-hole,antihole)-free graphs have been studied or written about?

These graphs occur quite naturally in constraint satisfaction problems where the graph of related variables forms a tree.  Such problems are rather easy, so it would be nice if there were a way to find a largest independent set clique for graphs in this family without having to compute the Lovász theta.

Equivalently, one wants to find a largest independent set for (hole, odd-antihole)-free graphs.  Hsien-Chih Chang points out below why this is a more interesting class for INDEPENDENT SET than (odd-hole, antihole)-free graphs.

In fact, it is relatively easy. Instead for studying independent set problem in (odd-hole,antihole)-free graphs, we take complement of the graphs and try to find a maximum clique in it. Thus it becomes maximum clique problem in (hole, anti-odd-hole)-free graphs.

In section 2 of the paper "Triangulated Neighborhoods in Even-hole-free Graphs" by da Silva and Vuskovic, they stated that Farber first shows

  There are $O(n^2)$ maximal cliques in any 4-hole free graphs.

Then their main theorem stated that

  There are $O(n + m)$ maximal cliques in even-hole-free graphs, and all the maximal cliques can be found in time $O(n^2m)$.

Since we are dealing with (hole, anti-odd-hole)-free graphs which is clearly even-hole-free, finding a maximum clique takes at most $O(n^2m)$ time.

4-hole-free are critical to these kind of results like a poly-time algorithm for $\overline{K_{2,m}}$-free graphs, so the real challenge may be studying independent set problem in (hole, anti-odd-hole)-free graphs instead, which becomes the maximum clique problem in (odd-hole, anti-hole)-free graphs.

Edit:

Oh, another thought came out. (hole, anti-odd-hole)-free graphs are almost weakly chordal in the following sense: since 4-hole-free implies there are only anti-holes with size 4~7 remains (any k-anti-hole with size > 7 contains a 4-hole), and it is also anti-odd-hole-free which restrict the size of anti-holes down to 4 and 6, it is almost no holes/antiholes in the graph! Thus a poly-time algorithm seems plausible for such graphs.


Estimating inner product over $[r]^d$ Alice has a vector $x \in [r]^d$ and Bob has $y \in [r]^d$, where $[r] \stackrel{\rm def}{=} \{0,1,\dots,r\}$. Alice send a message $M(x)$ to Bob and Bob wants to estimate the inner product $\left<x,y\right>$ with multiplicative error $\epsilon$ with probability $1 - \delta$.

My question is. Is there any known lower bound on $|M(x)|$? My intuition tells me that Alice pretty much has to estimate each coordinate of $x$ up to $\epsilon$ precision since Bob can have an input that zeros out all but one of the entry. Does that give you something like $\Omega(d \log 1/\epsilon)$?

In the indexing problem Alice has a vector $x \in \{0,1\}^d$ and Bob has a number $i$, and Bob wants to learn $x_i$. The randomized one-way communication complexity of this problem is $\Omega(d)$ (see Section 3 of this paper), and it can be solved by approximating $x_i = \langle x, e_i\rangle$ up to any multiplicative factor where $e_i$ is the vector with $1$ in the $i$-th coordinate and $0$'s everywhere else. So your problem has $\Theta(d)$ randomized one-way communication complexity for $r=1$.


Curry-Howard and programs from non-constructive proofs This is a follow up question to

What is the difference between proofs and programs (or between propositions and types)?

What program would correspond to a non-constructive (classical) proof of the form $\forall k \ T(e,k) \lor \lnot \forall k \ T(e,k)$? (Assume that $T$ is some interesting decidable relation e.g. $e$-th TM does not halt in $k$ steps.)

(ps: I am posting this question partly because I am interested in learning more about what Neel means by "the Godel-Gentzen translation is a continuation-passing transformation" in his comment.)

This an interesting question. Obviously one can't expect to have a program that decides for each $e$ whether $\forall k T(e, k)$ holds or not, as this would decide the Halting Problem. As mentioned already, there are several ways of interpreting proofs computationally: extensions of Curry-Howard, realizability, dialectica, and so on. But they would all computationally interpret the theorem you mentioned more or less in the following way.

For simplicity consider the equivalent classical theorem

(1) $\exists i \forall j (\neg T(e, j) \to \neg T(e, i))$

This is (constructively) equivalent to the one mentioned because given $i$ we can decide whether $\forall k T(e, k)$ holds or not by simply checking the value of $\neg T(e, i)$. If $\neg T(e, i)$ holds then $\exists i \neg T(e, i)$ and hence $\neg \forall i T(e, i)$. If on the other hand $\neg T(e, i)$ does not hold then by (1) we have $\forall j (\neg T(e, j) \to \bot)$ which implies $\forall j T(e, j)$.

Now, again we can't compute $i$ in (1) for each given $e$ because we would again solve the Halting Problem. What all interpretations mentioned above would do is to look at the equivalent theorem

(2) $\forall f \exists i' (\neg T(e, f(i')) \to \neg T(e, i'))$

The function $f$ is called the Herbrand function. It tries to compute a counter example $j$ for each given potential witness $i$. It is clear that (1) and (2) are equivalent. From left to right this is constructive, simply take $i' = i$ in (2), where $i$ is the assumed witness of (1). From right to left one has to reason classically. Assume (1) was not true. Then,

(3) $\forall i \exists j \neg (\neg T(e, j) \to \neg T(e, i))$

Let $f'$ be a function witnessing this, i.e.

(4) $\forall i \neg (\neg T(e, f'(i)) \to \neg T(e, i))$

Now, take $f = f'$ in (2) and we have $(\neg T(e, f'(i')) \to \neg T(e, i'))$, for some $i'$. But taking $i = i'$ in (4) we obtain the negation of that, contradiction. Hence (2) implies (1).

So, we have that (1) and (2) are classically equivalent. But the interesting thing is that (2) has now a very simple constructive witness. Simply take $i' = f(0)$ if $T(e, f(0))$ does not hold, because then the conclusion of (2) is true; or else take $i' = 0$ if $T(e, f(0))$ holds, because then $\neg T(e, f(0))$ does not hold and the premise of (2) is false, making it again true.

Hence, the way to computationally interpret a classical theorem like (1) is to look at a (classically) equivalent formulation which can be proven constructively, in our case (2).

The different interpretations mentioned above only diverge on the way the function $f$ pops up. In the case of realizability and the dialectica interpretation this is explicitly given by the interpretation, when combined with some form of negative translation (like Goedel-Gentzen's). In the case of Curry-Howard extensions with call-cc and continuation operators the function $f$ arises from the fact that the program is allowed to "know" how a certain value (in our case $i$) will be used, so $f$ is the continuation of the program around the point where $i$ is computed.

Another important point is that you want the passage from (1) to (2) to be "modular", i.e. if (1) is used to prove (1'), then its interpretation (2) should be used used in similar way to prove the interpretation of (1'), say (2'). All the interpretations mentioned above do that, including the Goedel-Gentzen negative translation.


On the need for a self-correcting function in the PCP theorem Original proof of the PCP theorem, uses self-correction property of linear functions.
Assume we have $f: \{0,1\}^n \rightarrow \{0,1\}$, a function or table of values,
that is $(1-\delta)$-close to some linear function $L$.
Using $f$ we would like to compute $L(x)$ for any desired $x$ with high accuracy. Such a
procedure is called a self-correction procedure since a small amount of errors in the table $f$ can be corrected using probes only to $f$ to provide access to a noise-free version of the linear function L.

Procedure $\text{SelfCorr}(f,x)$ is:

Select $y\in\{0,1\}^n$ uniformly at random.
Return $f(x+y)−f(y)$

One can prove if $f$ is $\delta$-close to a linear function $L$ for some $\delta<1/4$, then for any $x\in\{0,1\}^n$ the above procedure $\text{SelfCorr}(f,x)$ computes $L(x)$ with probability at least $1−2\delta$.

My question is: Why we don't probe $f$ at $x$ directly. By this way, error of procedure is at most $\delta$ (that is better than $2\delta$ error of $\text{SelfCorr}(f,x)$)?

The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2δ$ for all $x$ (not only random $x$)


Is joint Kolmogorov Complexity order invariant? Due to the symmetry of information, it follows up to an additive constant that

K(X,Y) = K(Y,X)

Does this hold for more than two data objects as well?

You don't need symmetry of information. The invariance theorem does the trick. Let $p$ the smallest program such that $U(p) = \langle x, y\rangle$. One way of producing $(y, x)$ is to take make a program $q$ that runs whatever program it is given as input, interprets the output as a pair, and flips the two parts. This gives you a program $\overline{q}p$ to produce $\langle y, x\rangle$. Since $\overline{q}$ is only a constant number of bits long, the two $K$'s are equal up to a constant.

Now for higher numbers of arguments, the same idea works in principle. However, the constant does depend on the number of arguments: if I want to write a $q$ program to compute some $n$-tuple of numbers and re-arrange it into an arbitrary order, I need to encode the order in $\log(n!)$ bits (if the ordering is random). So if the number of arguments is not fixed to a constant, you need to take that into account.

Isn't there some other way, besides the $q$ program? No, if there were we could encode free information in the ordering of the tuple.

Assume for a contradiction that $K(x_1, \ldots, x_n)$ is invariant up to a constant to permutation of the arguments, with the constant independent of $n$. Let $X = \langle x_1, \ldots, x_n\rangle$ be the enumeration of the first $n$ binary strings, so that $K(X) \leq_+ K(n)$. Let $z$ be a random string with $|z| = \log(n!)$ Let $\langle x_1, \ldots, x_n \rangle$ be a random string. Index all permutations of $n$ elements by binary strings and pick the one corresponding to $z$. Call this permutation of our tuple $X_z$. Let $p$ and $p_z$ be the shortest programs for $X$ and $X_z$ respectively. Build a program $q$ that reads input $\overline{p}p_z$ and returns $z$. Putting all this together gives us
$$\log(n!) \leq_+ K(z) \leq_+ |\overline{q}\overline{p}p_z| \leq_+ 2K(X) \leq_+ 2K(n) \leq_+ 4\log(n).$$


Is there a simple, intuitive explanation for why trees in Fibonacci heaps have the sizes they do? Fibonacci heaps have a simple rule that ensures its tree sizes grow exponentially with their ranks:

  A node can lose at most one child. Once that child is lost, the node must be cut from its parent.

I'm comfortable with the proof that a tree in a Fibonacci heap of rank $r$ has at least $F_{r+2}$ nodes, and can prove it cleanly use induction.

However, I don't have any intuitive understanding as to why the above rule would give rise to Fibonacci numbers this way. The "default" shape of the trees in a Fibonacci heap is given by the binomial trees, which have lots of nice mathematical properties but none that (immediately) seem like they'd translate into Fibonacci numbers after nodes are lost this way. The best guess I have is that this somehow relates to writing Fibonacci numbers as sums of diagonal binomial coefficients, but I don't see a way to connect that sum to the trees produced this way.

Is there a simple, intuitive, and, most importantly, non-inductive explanation as to why the marking rule in Fibonacci heaps would give rise to Fibonacci-sized trees?

I posed this question as a challenge to my students and I'm proud to report that they did not disappoint! Here's an argument based on ones developed by my students Kevin Tan and Max Arseneault, providing an intuition as to how the marking rule, applied to binomial trees, gives rise to the Fibonacci sequence.

Our goal will be to find a lower bound on the number of nodes that can be in a tree in a Fibonacci heap that has order $k$. We'll say that a maximally damaged tree of order $k$ is a binomial tree of order $k$ that has lost as many nodes as possible while obeying the Fibonacci heap marking rules, subject to the restriction that the root node still has $k$ children (and, thus, the tree has order $k$). For example, here's the first few maximally damaged trees:

Notice that cutting any of the remaining nodes from their parents would trigger a cascading cut that removes a child from the root.

Our goal will be to show that if $MD[n]$ denotes the number of nodes in a maximally-damaged tree of order $k$, then $MD[n]$ satisfies the recurrence relation

$$MD[k+2] = MD[k] + MD[k+1],$$

at which point it's no longer surprising that we see the Fibonacci sequence popping up.

To do so, consider a binomial tree of order $k+2$, like the one shown here:

We'd like to remove as many nodes from this tree as we can without cutting any direct children of the root. To do so, we'll imagine partitioning the nodes in this tree into two binomial trees of order $k+1$ by separating out the order-$k+1$ child from the remaining children, as shown here:

We haven't actually cut this link - that would remove a child of the root - and instead are just doing this for accounting purposes.

Now, think about the binomial tree of order $k+1$ containing the tree root. Focusing purely on this tree, we'd like to remove as many nodes as possible while still leaving the root with $k+1$ children. Stated differently, we have a binomial tree of order $k+1$ and want to remove as many nodes as possible without removing any children of the root, which is exactly what the maximally damaged trees represent. So let's restructure the root's binomial tree to look like a maximally-damaged tree of order $k+1$, as shown here:

Next, let's focus on the child subtree of order $k+1$. We can cut away as many nodes from this tree as we'd like, provided that we don't trigger a cascading cut that would cut this subtree from the overall order-$k+2$ tree root. Since this tree is allowed to lose a child without being cut from its parent, it makes sense to remove its largest child subtree, which would be its child of order $k$, since that would immediately eliminate the most nodes. Doing that gives us the following setup:

Notice that this tree is now a binomial tree of order k and that its root has been marked.

From here, we'd like to cut away as many nodes as we possibly can. However, since the root of this subtree is now marked, we cannot cut any direct children away from the root of this subtree. If we did, that would trigger a cascading cut that would cut the whole subtree away from the global tree root, which isn't allowed. And so we're left with a smaller copy of the same problem from earlier: we have a binomial tree of order $k$ and we want to cut away as many nodes as possible without cutting any direct children of the root. That means we want to form a maximally-damaged tree of order $k$, as shown here:

.

Putting everything together, we see that the shape of the overall tree can be partitioned into a maximally-damaged tree of order $k+1$ and a maximally-damaged tree of order $k$:

Overall, this shows that $MD[k+2] = MD[k] + MD[k+1]$, which is where the Fibonacci recurrence comes in. All that's left to do is to check that the base cases satisfy $MD[0] = F_2$ and $MD[1] = F_3$ (they do) and we've got the bound of $MD[k] \ge F_{k+2}$. Tada!


What's the difference between online and incremental optimization? Recently I've read some stuff about incremental optimization problems, but I can't see what's the difference between those and online optimization problems. My impression is that I can define every online problem as an incremental counterpart (the reverse is clearly true).

Here go the (not very formal) definitions. In an incremental problem, one is given a sequence of instances of an optimization problem. The (i+1)-th instance is an "extension" of the i-th one. The (i+1)-th solution must be calculated without knowledge of the "future" instances, and has to keep the decisions made at the i-th solution. The classical example is with the k-median problem: after opening k facilities, one wants to have k' > k facilities but does not want to demolish the old ones.

In an online problem, (the usual definition is that) one is given a sequence of "requests". Here, one also has to answer a request without knowledge of the future requests. One wants to optimize the cost/gain of answering the sequence as a whole.

I believe that for any online problem I can define an "offline" optimization problem that fits the incremental definition (and what I usually see is the reverse). If the definitions are equivalent, what is the point of using a different name for the same concept?

This is discussed in section 2.2.3 of Jeffrey Hartline's thesis: http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf

Online problems are all about informational uncertainty: you don't know what inputs are coming tomorrow, and the difficulty is often information theoretic, not computational. On the other hand, there is no uncertainty in an incremental optimization problem as Hartline defines it: every parameter of the problem is known at the outset. Without computational restrictions, the problems can always be solved optimally.

So perhaps your definition is wrong, since indeed yours sounds like an online problem. The problem of "incremental optimization" seems to be defined in this 2008 thesis, and differs from your definition in that there is no uncertainty.


FPRAS on #P complete problems and self reducibility I am quoting a phrase of Martin Dyer in his paper Approximate Counting by Dynamic Programming:

Since 0-1 knapsack is self-reducible, existence of an fpras for the problem now follows indirectly from a general result of Sinclair and Jerrum[19]

In that paper of Sinclair and Jerrum it is stated that:

It follows that, for self-reducible structures, polynomial time
randomised algorithms for counting to within factors of the form (1 +$n^{-\beta}$) are
available either for all $\beta \in R$ or for no $\beta \in R$.

Question 1: Does statement 2 mean that counting self reducible structures might have an FPRAS?

Question 2: What is the indirect method Dyer is talking about? Is it some folklore method considered well known?

This theorem from that paper of Sinclair and Jerrum is slightly stronger than the sentence quoted in the question, and gives the fpras mentioned by Dyer:

  THEOREM 4.6. Let $R\subseteq \Sigma^*\times\Sigma^*$ be self-reducible. If there exists a polynomially time-bounded randomised approximate counter for $R$ within
  ratio $1 + O(n^\alpha)$ for some $\alpha\in\mathbb R$, then there exists a fully polynomial randomised approximation scheme for $\#R$.

Note the quantification over $R$. Your first question asks if "counting self-reducible structures might have an FPRAS", but this theorem is looking at particular $R$'s and showing that if $R$ has a weak kind of approximation algorithm, then $R$ also has a stronger kind of approximation algorithm.

Jerrum and Sinclair explain it like this:

  The chief significance of Theorem 4.6 is that it establishes a notion of
  approximate counting which is robust with respect to polynomial time
  computation, at least for the large class of self-reducible relations [...] We suggest that this notion will be useful in the future classification
  of hard counting problems [...]


Zero Obstructed vertex induced subgraphs Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties:

It has no isolated vertices.
It is possible to add $i$ vertices to it without implying (by the very definition of vertex induced subgraph) the introduction of any new edge (in other words, it is possible to add $i$ isolated vertices).

Clearly, if a vertex induced subgraph is $i$ extendible it is also $j$ extendible for any $j < i$.

Now, let a vertex induced subgraph of $G$ be $i$ obstructed if and only if it is $i$ extendible but not $i+1$ extendible.

I'm interested in $0$ obstructed vertex induced subgraphs.

  Questions

  Let $N$ be the number of $0$ obstructed vertex induced subgraphs of $G$. Is $N$ polynomially bounded in the size of $G$? I believe yes (and I've made some empirical tests that seem to suggest so), but so far I was unable to prove it.
  If the answer to question 1. is no, is it nevertheless possible to compute $N$ in polynomial time?
  If the answer to question 2. is no, is it nevertheless possible to compute $N\ mod\ 2$ in polynomial time?

I'm curious to know if anyone already dealt with $0$ obstructed vertex induced subgraphs previously, how he encountered them in the first place, and what is known about them.

Another way to express question 1. is the following: which is the maximum number $\alpha$ of vertices that can be removed from $G$ without making it $1$ extendible? My sensation is that $\alpha \in O( log\ |V| )$, as I'm inclined to believe that $\alpha$ is strongly related to the diameter of $G$.

Sorry this is too long for a comment :)

Maybe the complete graph is a trivial graph but it illustrates that e.g. graphs $G = (V,E)$ with large cliques of size $\Omega(\vert V \vert)$ also have exponentially many $0$ obstructed induced subgraphs. And I don't think that $N$ can be easily computed in such graphs.

I also think that 3-regularity doesnt help: Let $A$, $B$ be a partition of $V$ each of size $\vert V \vert /2$. The induced subgraph consisting of nodes from either $A$ or $B$ is a cycle and the edges between $A$ and $B$ form a perfect matching. This graph is $3$-regular and every induced subgraph consisting of at least all nodes in $A$ or all nodes in $B$ is $0$ obstructed.


Treewidth and Packing My question is a bit vague. I have been wondering if (and how), we can apply the notion of treewidth to packing problems in graphs.

I would be happy with any insights or references of past research work on this (assuming their is some relation). Thanks.

I can interpret this question in two different ways:

1) When it comes to algorithmic properties of packing problems on graphs of bounded treewidth, Courcelle's Theorem shows that for every fixed $k$ we can optimally solve problems expressible in Monadic Second Order Logic in linear time on graphs of treewidth at most $k$ (see for example http://dx.doi.org/10.1093/comjnl/bxm037 for a survey on the algorithmic properties of bounded-treewidth graphs). As many packing problems can be formulated in MSOL, this proves tractability of many such problems on graphs of bounded treewidth, including Independent Set, Triangle Packing, Cycle Packing, packing vertex/edge disjoint copies of any fixed graph, packing vertex-disjoint minor models of some fixed graph H, and so on. But as this tractability extends to all MSOL-definable problems, it is not specific to packing.

2) When it comes to graph-structural relationships between packings and treewidth, the following might be of interest. Thanks to the work of Robertson and Seymour it is known that there is a function $f \colon \mathbb{N} \to \mathbb{N}$ such that every graph of treewidth at least $f(r)$ contains an $r \times r$ grid as a minor (the original bound for $f$ given by Seymour and Robertson was later improved in collaboration with Thomas; see http://www.sciencedirect.com/science/article/pii/S0095895684710732 for the current-best bound). Hence if you have a structure $S$ such that many copies of $S$ can be packed into an $r \times r$ grid minor, then you know that any graph of large treewidth contains a large packing of copies of $S$. For example, as an $r \times r$ grid (for even $r$) contains $(r/2)^2$ vertex-disjoint cycles, it follows that a graph of treewidth $f(r)$ contains at least $(r/2)^2$ disjoint cycles.


Comparison of Hashing and Modular Exponentiation Suppose we want to compare two protocols on the computational costs. One of the protocols is designed using random oracle model (we call it the first protocol) and the other protocol uses is designed over common reference string (we call it the second protocol).

Now if we want to compare these two, we have to rely on the most costly operation in them. In the first protocol it is the hashing operation and in the second, the modular exponentiation. How can I compare these two protocols assuming both of them work over the same length of security parameter.

For simplicity, assume that the first protocol uses "n" hashing operation to complete and the second protocol uses "2n" modular exponentiation to output the result.

  Is there any way to compare these two? What measures should I consider when comparing these protocols?

To give a little background on the models, the Common Reference String (CRS) is the model which a global coin is assumed, which means a reference string (mostly a random one) is distributed among the parties. The random oracle model is the model which is essentially formalizing the hash functions. In this model, every party has oracle access to a random function (i.e., they submit the query to a function (oracle) some where and get the results, which in this case is a random string). When implementing a protocol with this model, the queries are replaced by calculating a hash function.

Hashing is much cheaper than modular exponentiation, so much so that it is often taken as "free" in efficiency analysis that uses modular arithmetic. My suggestion would be to do a rough comparison, like you said: protocol 1 uses m hashes, protocol 2 uses n exponentiations.

If n>m, protocol 1 is much faster.
If m>a*n, I wouldn't start investigating further until a gets to be around 10^2 or 10^3. It seems unlikely that protocol 1 would use this many, unless if it is using a hash tree or similar data structure requiring lots of hashes.

There is no quick rule because the speed of an exponentiation at this level of scrutiny is dependent on the underlying group. Elliptic curves will be much faster than the integers mod p, and elliptic curve speed will depend on the type of curve.

Similarly, the speed of the hash function depends on how long the input message is. Does it fit into a single block, or does the hash need to iterate over it?

As one ballpark figure, a 100MHz FPGA can do about 100 ModExps (1024 bit with 160 bit subgroup) in one second, while it can hash about 5000 message blocks (SHA256) in a second.


Checking equivalence of two polytopes Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$.

Furthermore, consider two polytopes

$$\begin{align*}
P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\
P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\}
\end{align*}$$

where $f$'s and $g$'s are affine mappings. Namely, they are of the form $\vec{c}\cdot \vec{x} +d$. (We note that $P_1$ and $P_2$ are polytopes because they are "affine mappings" of the polytope $A\vec{x}\leq b$.)

The question is, how to decide whether $P_1$ and $P_2$ are equal as sets? What's the complexity?

The motivation of the problem is from sensor networks, but it seems to be a lovely (probably basic?) geometry problem. One can solve this in exptime, possibly by enumerating all the vertices of $P_1$ and $P_2$, but is there a better approach?

I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in the first-order theory of the rationals with addition and order. You have that $P_1$ is included in $P_2$ if and only if
\begin{align*}
\Phi :=
\forall \vec{x}.\exists \vec{y}.\left( A \cdot \vec{x} \le b \implies \left( A \cdot \vec{y} \le b \wedge \bigwedge_{1\le i\le m} f_i(\vec{x}) = g_i(\vec{y}) \right)\right)
\end{align*}
is valid. It is clear how to derive equivalence of $P_1$ and $P_2$ in the same way. Now $\Phi$ has a fixed quantifier-alternation prefix, and is consequently decidable in $\Pi_2^\text{P}$, the second level of the polynomial-time hierarchy (Sontag, 1985). I'm pretty confident that it is possible to also prove a matching lower bound, I recall reading somewhere that inclusion between two polytopes is $\Pi_2^\text{P}$-hard.

If you are looking for tool support in order to solve such problems in practice, modern SMT-solvers such as z3 fully support this theory.


A question of relationships between #P and PSPACE Let us assume there is some machine X that converts boolean formula to following form in polynomial time:

$$\Phi(x_1, x_2 .. x_m) = r_1(x_{i_1}, x_{j_1}, x_{k_1}) \land r_2(x_{i_2}, x_{j_2}, x_{k_2}) \ \land \ ... \ \land r_n(x_{i_n}, x_{j_n}, x_{k_n})$$

With following rules:

$r_l$ is given as it's table, example: $r_5 = 01101100$.
No different $r$ share all 3 same literals.
If $\Phi(... , x_i, x_j, x_k, ...) = 0$ for fixed $x_i, x_j, x_k$ then $r_l(..x_i..) = 0$.

What can this machine do after converting the formula? Really, if DTM has such formula as an input, following is true.

Solve SAT in $\mathcal{O}(1)$ time. It is a consequence of third rule. If $\Phi$ is not true for any arguments, it is not true for all $r$.
Solve TQBF in $\mathcal{O}(n)$ time. If all $r$ are true then $\Phi$ is true. Checking all $r$ takes linear time.
Return certificate for (TQ)BF in $\mathcal{O}(n)$ time. You can convert any $1$ bit to a set of 3 variables in $\mathcal{O}(1)$ time using Gray code.

What it can't do? It may be surprising.

It can't solve $\text{#SAT}$ in polynomial time. At least I don't know the algorithm.

Even if you know amount of solutions for all $r$ of non-quantified formula it doesn't give an answer.

Is this a proof that $PSPACE \subseteq \text{#}P$ ? And thus a much stronger theorem for $\text{#}P$ than Toda's.

How this will affect relationships between $PSPACE$ and $IP$ ?

It is known that $IP$ can solve exactly-k-#SAT. Can it answer if boolean formula has at least $k$ solutions?

It is already known that Sharp-P is contained in PSPACE. You are claiming that what you wrote shows that PSPACE is contained in Sharp-P. To do that, you would need to simulate TQBF formula with a Sharp-P oracle. What you wrote does not do that!


One-sided errors in probablistic proof systems In most probabilistic proof systems ( PCP theorem, for instance), the error-probabilities are usually defined on the side of the false-positives, i.e., a typical definition could look like :  if $x \in L$ then the verifier always accepts, but in other case the probability of rejection is at least 1/2.

Is there a problem in allowing the error to happen on the other side ? That means the verifier always rejects when it should, and makes no more than a constant error when it needs to accept. Another obvious possibility is allowing the error on both sides.
Will these definitions be equivalent to the one usually given? Or, they behave differently ? Or for that matter, is there a genuine problem in allowing the errors on the other side.?

Allowing completeness error has no problem, and it is often considered.  Here are some pointers.

On the other hand, generally speaking, disallowing soundness error removes the power of a model significantly.

In the case of interactive proof systems, disallowing soundness error renders interaction useless except for one-way communication from a prover to a verifier; that is, IP with perfect soundness is equal to NP.  This can be shown by considering an NP machine which guesses the verifier’s random bits and the transcript of the interaction which make the verifier accept [FGMSZ89].

In the case of probabilistically checkable proof (PCP) systems, the same reasoning shows that requiring perfect soundness makes randomness useless for choosing the locations to query.  More precisely, it can be shown that PCP(r(n), q(n)) with completeness c(n) and perfect soundness (even with adaptive queries) is equal to the class C of decision problems A=(Ayes, Ano) for which there exists a language B ⊆ {0,1}*×{0,1}*×{0,1}* in P such that

if x∈Ayes, then Pry∈{0,1}r(n)[∃z∈{0,1}q(n) such that (x, y, z)∈B] ≥ c(n), and
if x∈Ano, then ∀y∈{0,1}r(n) ∀z∈{0,1}q(n), (x, y, z)∉B,

where n=|x|.  (Note that in the definition of class C, the yes case does not require a whole certificate to be prepared before the verifier picks the random string y, unlike the usual definition of a PCP system.  A certificate can be prepared after knowing y, and only the queried portion of the certificate is needed, which is why the length of z is q(n).)  Combined with straightforward lower bounds, this implies the following:

PCP(log, log) with perfect soundness = P.
PCP(poly, log) with perfect soundness = RP.
PCP(poly, poly) with perfect soundness = NP.

Comparing these to the PCP theorems PCP(log, O(1)) = NP and PCP(poly, O(1)) = NEXP, we can see that requiring perfect soundness has a huge impact.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos.  On completeness and soundness in interactive proof systems.  In Randomness and Computation, vol. 5 of Advances in Computing Research, pp. 429–442, 1989.  http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps


What exactly is "large elimination"? I'm studying type theory (mostly Coq) and often encounter the term "large elimination", usually when talking about type universes hierarchy consistency, for example:

  impredicative polymorphism + excluded middle + large elimination => false

While I have an intuitive understanding of what it means, I wasn't been able to find or construct a more formal definition of what precisely is "large elimination".

In my understanding, large elimination is when a term t : T is eliminated (destructed) to get a value of type D, where D depends on the value of t.

For example, if vec_bool : nat -> Type is a type constructor for the boolean list of a fixed size with data constructors

nil  : vec_bool 0
cons : forall n:nat, bool -> vec_bool n -> vec_bool (S n)

the following recursive definition performs a large elimination on n:

Fixpoint construct_false_list (n:nat) : vec_bool n :=
   match n with
   | 0      => nil
   | Succ m => cons m false (construct_false_list m)
   end.

Is my understanding correct, or am I missing something?

You are incorrect about the definition of large elimination: it refers to the ability to build values of type $\mathrm{Type}$ by eliminating an inductive value. The canonical example:

bool_to_type : bool -> Type := fun b =>
     match b with
         | true => Unit
         | false => Empty

Where Unit and Empty are inductive types with 1 and 0 constructors, respectively. Notably, this allows you to prove the proposition $0 \not= 1$, which cannot be proven without this ability.

As noted in another answer (https://cstheory.stackexchange.com/a/21878/3984) a good resource that explains this is the following github repo: https://github.com/FStarLang/FStar/issues/360


Is there a Boolean formula that is resistant to bias from a polytime adversary? I am studying Coin Flipping protocols in cryptography, and the complexity of problems related to this.

Here, a question has come to my mind: Does there exist a public coin, coin flipping protocol?. Usual coin flipping protocols (as invented by Manuel Blum) involve that one party hides its random value by a bit commitment, and later makes it public. The coin-function is then just an XOR of the two bits.

Is it possible to drop the bit commitment part, and instead put the "hardness" into the coin function (i.e. something much harder than XOR)?

In other words:

Does there exists a PPT uniform family of circuits $\phi(x_1,\ldots, x_k, y_1 \ldots, y_k)$ for $k\in \mathbb N$, such that there for any PPT adversary $\mathcal A$ exists a negligible function $\gamma(k)$,  such that the family of circuits (under certain computational assumptions) have the following properties:

$\Pr[\phi(U_X,U_Y) = 1] = \frac{1}{2}$, where $U_X, U_Y$ are uniform distributions on $\{0,1\}^k$
Consider the function as the output of the following protocol: Alice decides the $x_i$ bits, and Bob decides the $y_i$ bits, and Alice wants $\phi$ to be 1 and Bob wants 0, and the bits have to be published in order $(x_1, y_1, x_2, y_2 , \ldots, x_k, y_k)$. $\phi$ should be resistant to more than negligible bias, when applying $\mathcal A$ against opponent that choses its bits uniformly. In other words:

When the variables are chosen in the following manner: Let $x_1$ be chosen by $\mathcal A$. Let $y_1$ be chosen uniformly. Let $x_2$ be chosen by  $\mathcal A$ using the knowledge of $(x_1,y_1)$. Let $y_2$ be chosen uniformly, and so on. Then the expected outcome of $\phi$ should be within $\gamma(k)$ of $\frac{1}{2}$
The same should hold where the $x$'s are uniform and $y$'s are chosen by $\mathcal A$

As a remark, one can see that the truth of this statement:
$ \exists x_1 \forall y_1 \ldots \exists x_k \forall y_k : \phi(x_1, \ldots, x_k, y_1, \ldots, y_k)$
correspond to the fact, that there exists a strategy for Party 1 to bias completely by $\frac{1}{2}$.

There does not exist such a family of circuits. Assume to the contrary that $\{\phi_k\}_{k \in \mathbb N}$ was such a family.

We will now show the strategy that achieves bias at least $\frac{1}{20k}$ for $k$ big enough, by referring to Impagliazzo's Theorem 4.7.2 on page 71 of http://cseweb.ucsd.edu/~russell/format.ps :

Let $\mathcal A$ be the strategy that:

1) Picks a bit string uniformly from $x \in \{0,1\}^k$, and picks a number $ i \in \{0,\ldots,2k-1\}$ uniformly. Now, $i = 2j+b$, for $b \in \{0,1\}$ for an unique $j$ and $b$.

2) $\mathcal A$ should send the first $j$ messages in correspondance with the first $j$ coordinates of $x$.

3) If $b=0$ Then $\mathcal A$ should wait for answer from the other party. Otherwise, it should just proceed:

4) $\mathcal A$ picks a new bit string $(x'_{j+1}, \ldots x'_k) \in \{ 0,1 \}^{k-j}$ uniformly, and then calculate 2 estimates of the Expected value of $\phi$, calculated by making polynomially many uniform samples from $\{0,1\}^{k-j-b}$ corresponding to the remaining conversation of the honest party:

$E_1$ : Estimate of expected value where preceding conversation is fixed, and  $(x_{j+1}, \ldots x_k)$ is fixed.
$E_2$ : Estimate of expected value where preceding conversation is fixed, and  $(x'_{j+1}, \ldots x'_k)$ is fixed.

5) The bit string corresponding to the highest expected value, is used for the rest of the conversation.

If assuming perfect estimation of expected value, we achieve at least $\frac{1}{16k}$ bias, and since there is some (exponentially decreasing error) caused by the estimation (which can be bounded by additive Chernoff-Hoeffding bound), we just say a bias of at least $\frac{1}{20k}$ for $k$ big enough.

For now, I will just refer to Impagliazzo's proof for the analysis. It is not the easiest proof to read, if one is not used to his style of writing, but it is correct, and I can explain specific details, if anybody have interest.


Dynamic Tree Marked Ancestor Queries Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it must be possible to insert leaves as well as internal nodes. Deletion is not needed. $M$ can only grow by adding new vertices as they are inserted into $V$ (no existing vertices of $V$ will be added to $M$ at a later point in time).

I need an algorithm that given any vertex $v \in V$ (not necessarily in $M$), it will find the nearest ancestor $u \in M$ of $v$, with space preferably being not worse than linear in $|V|$ and/or $|M|$ and time being somewhat logarithmic in $|M|$. Also the updates should be efficient.

This is known as the Marked Ancestor Problem [1] and also goes under the names of two-dimensional range searching and union-find problems. The problem with [1] is that for once it doesn't support insertion of internal nodes, and also it is extremely abstract and I definitely can't derive an algorithm and an implementation from it.

Also in my case, a solution involving Informative Labeling [2] would be highly desirable.

[1] S. Alstrup, T. Husfeldt and T. Rauhe, Marked Ancestor Problems. focs, pp.534, 39th Annual Symposium on Foundations of Computer Science, 1998
[2] D. Peleg, Informative labeling schemes for graphs. Mathematical Foundations of Computer Science, pp. 579--588, 2000

Here is another approach, maybe it can be "fixed": I can maintain versions of the tree which are linearized by a total order, one using pre-order traversal, the other using post-order traversal, using an approach developed by Dietz [3]. With these two lists I can query in $O(1)$ whether a vertex $u$ is an ancestor of another vertex $v$ in the tree ($u$ must be left of $v$ in the pre-order list and right of $v$ in the post-order list). If I could organize my vertices $M$ in a way that I can find the nearest ancestor of $v$ in logarithmic or polylogarithmic time, the problem is solved. Right now I can just go through all elements of $M$ and collect the nearest ancestor (closest to $v$ in the lists) in $O(|M|)$...

[3] P. Dietz, Maintaining order in a linked list. Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 122--127, 1982

If you don't need deletions, I think the first part of Lemma 4.1 on page 349 of the following paper:

Jeffery Westbrook: Fast Incremental Planarity Testing. ICALP 1992: 342-353
  http://dx.doi.org/10.1007/3-540-55719-9_86

gives you a linear time algorithm for any sequence of operations consisting of constructing and marking the tree, as well as conducting nearest marked ancestor queries (i.e. the query time is amortized constant).