Proof complexity and lower bounds One way to prove NP$\neq$ coNP is to show that for every propositional proof system $f$ computable in polynomial time, there exists a family of tautologies for which $f$ requires super polynomial proof lengths (w.r.t the length of tautology being proven).
Results like that of Haken and Ajtai fix a propositional proof system and prove that a certain family (PHP in this case) requires super polynomial length proofs.

My Question:
Are there results which do not fix a proof system and show, possibly very weak, but non-trivial lower bounds on proof length?
For Example: Are there results showing that for every propositional proof system, there exists a family of tautologies which requires superlinear proof lengths?

The statement is false for any polynomial time recognizable family of tautologies: the proof system will simply check if the formula is one of them and accept if it is. Proof length of them will be O(1). So I don't think any explicit example is known.

Recall that we don't even know if SAT $\notin$ DTime(O(n)) so we also don't know if SAT$\notin$ coNTime(O(n)) which is equivalent to your question TAUT $\notin$ NTime(O(n)) and follows from a positive answer to your question.

On the other hand, if NP is not equal to coNP, then the family consisting of all tautologies has super polynomial length in any efficient proof system.

Part of what people try to do in prof complexity is to rule out interesting classes of algorithms. A lower bound in a proof system implies a lower bound for all (co-nondeterministic) algorithms whose correctness can be efficiently proven in the proof system (if we can formalize and prove the correctness of an algorithm for SAT in a proof system we can consider its failing execution to find a satisfying assignment as proofs of the tautologihood).


Decidability of equality of CFL's Following problem is decidable:

Given a context-free grammar $G$, is $L(G) = \varnothing$?

Following problem is undecidable:

Given a context-free grammar $G$, is $L(G) = A^{\ast}$?

Is there a characterization of context-free languages $M$ with decidable equality $L(G) = M$?

I am not sure there is any general characterization for equivalence, but the following papers by Hopcroft, and Hunt and Rosenkrantz resp. might be a good start:

John E. Hopcroft, On the equivalence and containment problems for context-free languages, Theory of Computing Systems 3(2):119-124,  doi:10.1007/BF01746517;
Harry B. Hunt, III and Daniel J. Rosenkrantz, On Equivalence and Containment Problems for Formal Languages, Journal of the ACM 24(3):387--396, 1977, doi:10.1145/322017.322020.

Hopcroft shows in particular that, if $M$ is regular, then $L(G)=M$ is decidable iff $M$ is bounded, i.e. there exist $n$ words $w_1,w_2,\ldots,w_n$ s.t. $M\subseteq w_1^\ast w_2^\ast\cdots w_n^\ast$.


Why is lambda calculus a "calculus"? The only definition of "calculus" I'm aware of is the study of limits, derivatives, integrals, etc. in analysis. In what sense is lambda calculus (or things like mu calculus) a "calculus"? How does it relate to calculus in analysis?

A calculus is just a system of reasoning. One particular calculus (well, actually two closely related calculi: the differential calculus and the integral calculus) has become so widespread that it is just known as "calculus", as if it were the only one. But, as you have observed, there are other calculi, such as the lambda calculus, mu calculus, pi calculus, propositional calculus, predicate calculus, sequent calculus and Professor Calculus.


Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$? It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$.
It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$.
$\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) = \mathsf{BPP}/f(n)$ for all $f(n)$.

What is the smallest class of functions $f(n)$ such that
$\mathsf{P}/f(n) = \mathsf{BPP}/f(n)$ is known?

Nothing better than $\mathbf{BPP}/\text{poly} = \mathbf{P}/\text{poly}$ is known. On the other hand, better results are known in the space bounded setting. Fortnow and Klivans showed that $\mathbf{BPL} \subseteq \mathbf{L}/O(n)$ (see this paper for a refinement). It follows that $\mathbf{BPL}/O(n) = \mathbf{L}/O(n)$.


Efficient algorithm for finding directed cycle with smallest average weight Suppose we have a strongly connected directed graph with non-negative weights on its edges. Is there an efficient algorithm to find the directed cycle with the smallest average weight in the graph? (Here, smallest average weight of a directed cycle is the sum of the weights of all edges in the cycle divided by the number of edges.)

Karp has an algorithm that does exactly that. You can read about it in his paper "A characterization of the minimum cycle mean in a digraph."

There seem to be other algorithms proposed here which are perhaps easier to read.


Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied? By BPP/linear I refer to BPP machines with linear advice, which fulfills the promise when given the "correct" advice,
and the derandomization should give us, say, a P/linear or (SUBEXP/linear) algorithm.

If we use non-uniform assumptions, I think classical results should work, because we can "fool" non-uniform adversaries.

However, using uniform assumptions, say $EXP\neq BPP$,  non-trivial derandomization seems like a harder question.

Do there exist results regarding this kind of classes, not necessary BPP/linear?

I used the this scholar search, and the only result which seems somehow relevant is this:

Lance Fortnow, Adam Klivans, Linear Advice for Randomized Logarithmic Space, ECCC TR05-042, 2005.

Unfortunately, I think it is not exactly what you need. In particular, the main result of the paper is $\mathbf{RL} \subseteq \mathbf{L}/O(n)$. Yet I believe the techniques used there might be helpful in the case of your question.


On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$ It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses.
Being $s_k=\text{inf}\{\delta: \text{there exists }2^{\delta n}\text{ algorithm for solving }k\text{-SAT}\}$, it has been shown in [2] that, assuming $\text{ETH}$, $s_k$ increases infinitely often as $k\to \infty$, that is to say the complexity of $k\text{-SAT}$ grows as $k$ grows.

Question
Is the second statement known to hold, under $\text{ETH}$, also in the $2^{o(m)}$ realm?
More precisely, being $\mu_k=\text{inf}\{\delta: \text{there exists }2^{\delta m}\text{ algorithm for solving }k\text{-SAT}\}$, does $\text{ETH}$ imply that $\mu_k$ increases infinitely often as $k \to \infty$?

Which Problems Have Strongly Exponential Complexity? by R. Impagliazzo, R. Paturi and F. Zane (December 1999)
On the Complexity of $k$-SAT by R. Impagliazzo and R. Paturi (January 2001)

Update 22/11/2020
To avoid ambiguities or misunderstandings, let me clarify that here the number of clauses is not super-linear in the number of variables. The $k\text{-SAT}$ instance I'm talking about is already sparse, that is to say $m = \Theta(n)$. I'm interested in knowing the consequences on $\text{ETH}$, if any, of an algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$. The existence of such algorithm proves that the sequence $\mu_k$ as defined above decreases monotonically, rather than increasing infinitely often. That's precisely why I've asked this question in the first place.
Update 26/11/2020
Following daniello's comment below, let me clarify that here each clause has exactly $k$ distinct literals, and that trivial clauses are not allowed to be present.

This is an answer to the updated question (the original question seems harder).
Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses has a $O(2^{\mu'_k m})$ time algorithm.
Let $\mu_k$ be the smallest constant such that $k$-SAT with any clauses of length at most $k$ has an $O(2^{\mu_k m})$ time algorithm. I will prove that $\mu'_k = \mu_k$.
Proof: Clearly we have $\mu'_k \le \mu_k$. To prove that $\mu_k \le \mu'_k$ suppose we have an algorithm for $k$-SAT with nontrivial clauses of length exactly $k$ with time complexity $O(2^{\mu'_k m})$. To solve general $k$-SAT with $m$ clauses, we add $k$ extra variables to the input formula and $2^k-1$ extra clauses over these new variables to forbid all assignments except the all-false assignment. Now, these $k$ extra variables can be freely added to any clauses of length less than $k$ to make them length exactly $k$. Now we have a restricted instance with $m + 2^k-1$ clauses, and solve it in $O(2^{\mu'_k (m + 2^k-1)})$ time, which for constant $k$ is $O(2^{\mu'_k m})$ time.$\square$
It is easy to see that for $a \le b$ it holds that $\mu_a \le \mu_b$, and it is well-known (e.g. in section 14.1 of the book Parameterized Algorithms) that assuming ETH, $\mu_3 > 0$. Therefore showing that $\mu'_k \rightarrow 0$ as $k \rightarrow \infty$ would break ETH.


How to check if a number is a perfect power in polynomial time The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in details. Can someone tell me how to do this in polynomial time? Thanks.

Given a number n, if at all it can be written as $a^b$ (b > 1), then $b < \log(n) + 1$. And for every fixed $b$, checking if there exists an $a$ with $a^b = n$ can be done using binary search. The total running time is therefore $O(\log^2 n)$ I guess.


Weighted balls and bins Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$.  We throw the balls into the bins randomly, i.e., each ball lands into a random bin.

Can we argue that with constant probability, if you take the heaviest ball that lands into each non-empty bin, you get a set of balls whose total weight is $c T$ for some constant $c \in [0,1]$? I prefer $c$  as close to $1$ as possible but I want to make sure that the probability that happens is at least a constant.

Suppose you have $n$ balls. Take a random ball from each non-empty bin. Your expected weight is approximately $(1-1/e)T$. This holds because the probability that a bin is empty is $(1-1/n)^n \approx 1/e$. Thus, the expected number of balls you get is $(1-1/e)n$, and these are a random sample of all the balls.

Now, suppose you have balls whose weights are not all equal. Then the expected weight is at least $(1-1/e)T$, because you always take the largest ball from each bin. However, you never get a total weight larger than $T$. This means that at least half the time, you must get a weight of at least $(1-2/e)T$.

You're never going to get $c > 1-1/e$. That's probably the right answer for $c$, but to get it you probably need to use probability theory that's at least a little more sophisticated than I did.


Circuit complexity and statistical tests A few years ago, I took a class on complexity theory from Steven Rudich, and I remember him giving an interesting lecture connecting statistical tests (as found in statistics departments!) with circuit complexity. I remember him claiming something vaguely like: you could use circuits to abstractly characterize what a statistical test was, and that there were fundamental limits on what sorts of patterns statistical tests could identify.

Unfortunately, I remember neither precisely what his claim was, nor even enough keywords to let me Google for it. Does anyone know what he could have meant, and supply me with some references?

(My apologies for the vagueness of this question: if I knew enough to ask precisely, I wouldn't need to ask!)

I think I remember what lecture you're talking about. I remember he was saying that most statistical tests that are done can be carried out in $LOGSPACE$. (Comparing the number of $1$'s versus the number of $0$'s, computing standard deviation, etc.) But the output of Nisan's pseudorandom generator will fool all of these statistical tests, and still is not a truly random sequence. This lecture by Ryan O'Donnell describes the details.

An alternative way of defining "statistical test" is given by Blum and Goldreich.


CLRS's Fibonacci Heap size(x) analysis has a flaw? In CLRS's Introduction to Algorithms 3rd edition P.525, when it analyzes the size($x$)'s lower bound, there is a sentence that I quote as "because adding children to a node cannot decrease the node’s size, the value of $s_k$ increases monotonically with $k$". But in fact, I think I can give a counterexample to show that $s_k$ does not necessarily increase monotonically with k.

In the following graph, the degree of the node with key 1 is 2, and there is no other node with degree of 2. So $s_2=8$. Similarly, $s_3=6$. But now $s_3$ is less than $s_2$ which means $s_k$ is not monotonically increasing with $k$ at all.

2 - 0 - 4 - 2 - 5 - 8 - 7 -  1
            |               /  \
            8              2    9
                              / | \
                             10 14 16
                             |  |
                             11 15

The heap can be derived from an unordered binomial subtree by executing a series of cuts and cascading-cuts.

I want to know whether the above structure is a valid Fibonacci heap. If so, then it is also a valid counterexample.

In CLRS, $s_k$ is defined to be "the minimum possible size of any node of degree $k$ in any Fibonacci heap." Assuming your example data structure is a valid Fibonacci heap, your Fibonacci heap has a node of degree 2 with size 8 and a node of degree 3 with size 6. Thus, these are possible sizes that nodes of degree 2 and 3 can have but not lower bounds on their sizes.

Using Lemma 19.1 (as in the proof of Lemma 19.4), $s_2 = 3$ and $s_3 = 5$, monotonically increasing as CLRS claim.


Stack memory usage for tail calls I'm puzzled by this statement from Wikipedia:

  For tail calls, there is no need to remember the place we are calling
  from — instead, we can perform tail call elimination by leaving the
  stack alone (except possibly for function arguments and local
  variables [my emphasis]) [...]

I thought that the amount of space for a tail call was constant.  I thought that it was O(1), not O(n) where n would be the depth of the stack (if it were not tail-recursive).  But what is this "(except possibly for function arguments and local variables)"?

Is memory usage for a tail call not constant and can you get a memory overflow?

Is memory usage for a tail call not constant and can you get a memory overflow?

The stack usage for tail-recursive functions is bounded by a constant (i.e., is $O(1)$). However, you may still need to manipulate the stack at each recursive call in order to ensure that arguments are where the procedure expects them to be. Here's an example of such a program, written in Ocaml.

let rec frob n a b c d e f g =
  if n = 0 then
    a
  else
    frob (n-1) b c d e f g a

What this does is take decrement a counter, and rotate its arguments until it reaches 0. This program will compile to the following machine code:

_camlFrob__frob_1030:
    subl    $28, %esp
L101:
    movl    %eax, 0(%esp)
    movl    %ebx, 24(%esp)
    movl    _caml_extra_params + 0, %ebp
    movl    _caml_extra_params + 4, %ebx
    movl    0(%esp), %eax
    cmpl    $1, %eax
    jne     L100
    movl    24(%esp), %eax
    addl    $28, %esp
        ret
        .align  16

    L100:
        movl    %ebx, 20(%esp)
        movl    %ebp, 16(%esp)
        movl    %edi, 12(%esp)
        movl    %esi, 8(%esp)
        movl    %edx, 4(%esp)
        movl    %ecx, 0(%esp)
        addl    $-2, %eax
    movl    0(%esp), %ebx
    movl    4(%esp), %ecx
    movl    8(%esp), %edx
    movl    12(%esp), %esi
    movl    16(%esp), %edi
    movl    20(%esp), %ebp
    movl    %ebp, _caml_extra_params + 0
    movl    24(%esp), %ebp
    movl    %ebp, _caml_extra_params + 4
    jmp     L101

As you can see, it is not pushing anything on the stack (the contents of %esp), but it does need to shuffle the contents of the stack around before making the tail call (jmp L101). (As an aside, decrementing the n variable is accomplished by subtracting 2 from %eax, since Ocaml uses a tagged representation of integers.)

I seem to recall that the problem of putting variables into slots so as to minimize the amount of stack/register shuffling you need to do is NP-complete, and that consequently most compilers rely on heuristics to figure out what to do.

(P.S. I don't know what's wrong with the indentation -- it's fine in the preview....)


Dichotomy of the spectra of directed graphs Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known:

It is known that a directed graph $G = (V,E)$ has an adjacency matrix $A(G)$ whose eigenvalues are binary $\{0,1\}$ if $G$ is a-cyclic.
This follows by sorting the vertices into strongly connected components: this fixes an enumeration of the vertices $v_1,.., v_n$ such that the permuted Laplacian according to this ordering is upper-triangular with $0/1$ entries.

But what is known if $G$ is the other extreme end - i.e. $G$ is a strongly-connected graph on $n$ vertices - meaning that there is a directed path between any pair of vertices.

Generally, one would need to compute the characteristic polynomial of $A(G)$ and compute its roots.
Despite $A(G)$ being a $\{0,1\}$ matrix this seems like a daunting task.
In particular, the roots of this polynomial are in general complex numbers.

The Perron-Frobenius theorem implies that at least the top eigenvalue is real and simple, but does not reveal information about the rest of the eigenvalues.

However, what if we're interested only in very weak bounds of the following form:

$\textbf{Conjecture: Dichotomy of eigenvalues}$:
Let $G$ be a directed graph on $n$ vertices.
Then either all eigenvalues of $A_G$ are real, or there exists at least one eigenvalue $\lambda$ such that $im(\lambda)\geq 1/poly(n)$.

Do such bounds follow trivially from known theorems?
Alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component?

The answer to “alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component” is YES (though I don’t understand what is “alternative” about this statement, as it does not in any way disprove the conjecture).

As I already wrote in a comment, it is a not very difficult exercise to show that if $f\in\mathbb Z[x]$ is a monic polynomial, there exists a directed graph $G$ on $O(\deg(f)+\|f\|_1)$ vertices whose eigenvalues include all roots of $f$. This implies the statement above modulo the fact that such polynomials may have roots with exponentially small imaginary part, which I assumed to be easy to find in the literature on minimal root separation. However, I realized that such bounds are actually not as readily found as I expected, so I decided to write it as a proper answer for the record.

Several examples of polynomials with exponentially small root separation are listed by Schönhage [1], in particular the family of polynomials
$$x^n-2(cx-1)^2\qquad(n\ge3,c\ge2)$$
attributed to Mignotte [2] (which I cannot verify as I have no access to it at the moment). Now, these polynomials have each a pair of real roots near $1/c$ in distance $<2/c^{1+n/2}$, whereas we need a pair of complex roots. This is, however, easily accomplished by modifying the polynomial slightly: let
$$f(x)=x^n\mathbin{\color{red}+}(2x-1)^2=x^n+4x^2-4x+1.$$
Clearly, this polynomial has no positive real root (and no negative real root either if $n$ is even). Moreover, it is easy to show that it still has a pair of (necessarily non-real) roots in exponentially small distance to $1/2$; if I didn’t mess up the computation, these roots are approximately
$$z_\pm=\frac12\pm i2^{-1-\frac n2}+O(n2^{-n}).$$
Now, $f(x)$ can be written as the determinant of e.g. the $n\times n$ matrix
$$\begin{pmatrix}
x&-1\\
&x&-1\\
&&x&-1\\
&&&\ddots\\
&&&&x&-1\\
1&-4&4&&&x
\end{pmatrix}$$
and therefore as the characteristic polynomial of the adjacency matrix of the weighted directed graph $G_0$ on $n$ vertices $\{0,\dots,n-1\}$ with edges $i\to i+1$ of weight $1$ for $i=0,\dots,n-2$; $n-1\to0$ of weight $-1$; $n-1\to1$ of weight $4$; and $n-1\to2$ of weight $-4$. The eigenvalues of $G_0$ are thus exactly the roots of $f$, including $z_\pm$.

Finally, the eigenvalues of $G_0$ are included among eigenvalues of the unweighted directed graph $G_1$ on $2n+6$ vertices
$$0_+,0_-,\dots,(n-2)_+,(n-2)_-,(n-1)_+^0,\dots,(n-1)_+^3,(n-1)_-^0,\dots,(n-1)_-^3$$
with edges $i_+\to(i+1)_+$ and $i_-\to(i+1)_-$ for $i=0,\dots,n-3$; $(n-2)_+\to(n-1)_+^j$ and $(n-2)_-\to(n-1)_-^j$ for $j=0,\dots,3$; $(n-1)_+^0\to0_-$, $(n-1)_-^0\to0_+$; and $(n-1)_+^j\to1_+$, $(n-1)_+^j\to2_-$, $(n-1)_-^j\to1_-$, $(n-1)_-^j\to2_+$ for $j=0,\dots,3$.

References:

[1] A. Schönhage, Polynomial root separation examples, Journal of Symbolic Computation 41 (2006), no. 10, pp. 1080–1090, doi:10.1016/j.jsc.2006.06.003.

[2] M. Mignotte, Some useful bounds, in: Buchberger, Collins, Loos (eds.), Computer Algebra: Symbolic and Algebraic Computation, 2nd ed., Springer-Verlag, 1983, pp. 259–263, doi:10.1007/978-3-7091-7551-4_16.


If an abstract machine can simulate itself, does that make it Turing complete? For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e.g. simulating Conway's Game of Life in Conway's Game of Life).

So my question is: is a system being able to simulate itself sufficient to prove it's Turing complete? It certainly is a necessary condition.

No, it's not. I know two major classes of techniques for avoiding inconsistency/Turing completeness.

The first line of attack is to set up the system so that syntax can be arithmetized, but Godel's fixed point theorem doesn't go through. Dan Willard has worked extensively on this and given consistent self-verifying logical systems. The trick is to eliminate the multiplication and addition function symbols, and replace them with divisibility and subtraction. This gives you enough horsepower to represent syntax arithmetically, but the fixed point theorem doesn't go through since multiplication is not provably total.

See Dan Willard. Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles. Journal of Symbolic Logic 66 (2001) pp. 536-596.
The second line of attack allows more use of fixed points, but to set things up so that syntax doesn't arithmetize. The prettiest systems for this are (IMO) based on variants of linear logic. For example, in Kazushige Terui's Light Affine Set Theory, even the full unrestricted set comprehension principle is sound, but since the ambient logic of the set theory is linear (and hence contraction is not allowed), Russell's paradox is not derivable.

The intuitive reason that arithmetization fails is that the light linear function space $A \multimap B$ is set up so that all its inhabitants are polynomial time. As a result, the light linear version of the Peano axioms can't prove exponentiation total (since exponentiation of unary numbers takes exponential time), and so there is no longer an isomorphism between the natural numbers and bit strings.

Kazushige Terui. Light affine set theory: A naive set theory of polynomial time. Studia Logica, Vol. 77, No. 1, pp. 9-40, 2004.

I think this paper is more accessible after reading the following paper of Yves Lafont:

Y. Lafont, Soft Linear Logic and Polynomial Time, Theoretical Computer Science 318 (special issue on Implicit Computational Complexity) p. 163-180, Elsevier (2004)

Terui's set theory is very expressive, but it's hard to compare with traditional set theories, since proof-theoretic ordinals are not a good tool for comparing very weak systems. For example, Terui's set theory obviously cannot prove exponentiation total, and hence its proof-theoretic strength cannot even reach up to $\omega$. Complexity classes are probably better -- it is complete for polytime (it can prove every polytime function total, but no more).

I tend to think of these kinds of systems as proofs-of-concept for the idea that complexity theory can serve as a foundation for certain kinds of ultrafinitism.


What's the complexity of recognizing equivalence for the following relation? Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers.

We say that two matrices $A$, $B \in \mathcal{M}_{m,n}(\mathbb{Z})$ are equivalent if $A$ can be obtained from $B$ by

permuting (i.e., swapping) rows and
permuting integers (i.e., applying a bijection $\mathbb{Z} \to \mathbb{Z}$ to every element of $B$).

Example:
$\left(\begin{matrix}1 & 0\\ 1 & 1\end{matrix}\right)$ is equivalent to $\left(\begin{matrix}0 & 0\\ 0 & 1\end{matrix}\right)$.

What is the complexity of the recognition problem, i.e., given two matrices, decide whether they are equivalent?

What is the complexity of the invariant problem, i.e., given a matrix $A$, calculate a complete invariant $f(A)$, that is, a function such that $A$ and $B$ are equivalent only if $f(A) = f(B)$?

The recognition problem is equivalent to the graph isomorphism (recognition) problem, and the invariant problem is equivalent to the graph isomorphism invariant problem.

To reduce the current problem to graph isomorphism, given an m×n matrix A, let S be the set of integers which appear as an entry of A at least once.  We construct a graph G(A) with m+mn+|S| labeled vertices as follows.

For each row i, the graph has a vertex ui labeled as “row.”
For each cell (i, j), the graph has a vertex vij labeled as “cell in column j.”
For each integer k∈S, the graph has a vertex wk labeled as “entry.”
For each cell (i, j), connect ui and vij by an edge, and connect vij and waij by an edge.

Then it is not hard to see that two matrices A and B are equivalent in the sense stated in the question if and only if there is an isomorphism between G(A) and G(B) which preserves labels.  But the isomorphism problem of vertex-labeled graphs is known to be equivalent to the isomorphism problem of usual, unlabeled graphs.

To reduce graph isomorphism to the current problem, given a graph G=(V, E), consider each edge as two directed edges, and construct a 2|E|×2 matrix M(G) by writing the two endpoints of each directed edge in one row.  Then again it is not hard to see that two graphs G and H are isomorphic if and only if M(G) and M(H) are equivalent in the sense stated in the question.


Estimating Average in Polynomial Time Let $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$ be a function. We want to estimate the average of $f$; that is: $\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$.

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Let $E$ be the (randomized) estimator algorithm. Assume that $E$ has black-box access to $f$. We denote this by $E^f$.

There are two conditions:

1) Estimator's running time: There exists a single polynomial $p(\cdot)$ such that for all $n$ and all $f$, the running time of the $E^f(1^n)$ is bounded by $\frac{p(n)}{\mathbb{E}[f(n)]}$.

2) Estimator's precision with confidence $\delta$: There exists a single polynomial $q(\cdot)$, such that for all $n$ and all $f$, we have ${1 \over {q(n)}} < \frac{E^f(1^n)}{\mathbb{E}[f(n)]} < q(n)$ with probability at least $\delta$.

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

  Do such estimators exist?

Background and Motivation

I did not mention my motivation at the beginning since it requires a great deal of background knowledge. Anyway, for the enthusiasts, I describe it briefly: The need for such estimators arise in the context of "Proofs of Ability," as defined in the following article:

Mihir Bellare, Oded Goldreich. Proving Computational Ability, 1992. Unpublished Manuscript.

Specifically, at the bottom of page 5, the authors implicitly assumed the existence of such estimators (There's no mention of precision, and the running time is not precisely defined; yet the context clearly defines everything.)

My first attempt was to read "A Sample of Samplers---A Computational Perspective on Sampling." It pertains to a very similar problem, yet the error probability defined is additive, while ours is multiplicative. (I didn't fully read the paper, maybe it mentions what I need somewhere.)

EDIT (as per Tsuyoshi's request): In fact, the definition of "Proofs of Computational Ability" requires the existence of a "knowledge extractor" whose (expected) running time is $p(n) \over E[f(n)]$. Since we don't know $E[f(n)]$, we want to estimate it; yet this must not change the running time considerably: it should change it up to a polynomial factor. The precision condition tries to capture such requirement.

EDIT: This solves the version of the problem where f only outputs 0 or 1. But I think the solution can be adapted to make it work for the more general case.

Maybe I misunderstood the question, but this doesn't look too hard.

Instead of estimating, the average, let's think of estimating the number of 1s, and call that number k. Let $N = 2^n$. So the average is k/N. You want to estimate this within a polynomial multiplicative factor in time O(N polylog(N)/k).

I think this can be done to within any constant multiplicative factor too. For example, let's say you want to estimate this to within a factor of 2. So the output $k'$ of the algorithm will be between k/2 and 2k.

I'll sketch an algorithm, which should have the appropriate running time. First check if k is between N/2 and N. This is easy, just sample a few random values and if you get more than half 1s, then it's in this interval. So you have a 2-approximation. If not, then check if it is between N/4 and N/2. And so on. Every time you make the interval smaller, it is more costly to estimate whether k lies in that range. But the cost is inversely proportional to how small the interval is.

For example, if you are checking if k is between $N/2^q$ and $2N/2^q$, then you need to make about $O(2^q)$ queries. Anyway, after repeating this procedure enough times, you should get the interval in which k lies. Say k lies between $N/2^q$ and $2N/2^q$. Then k is approximately $N/2^q$. So $2^q$ is about k/N. So in this step we would spend O(k/N) queries. But getting to this step required q other steps, but that's just an extra polylog(N) factor. So the overall running time is O(N polylog(N)/k), for a 2-approximation.

(One would actually have to do error amplification to get decent precision in each step. But that's only an extra polylog factor.)

The reason I like to think of it in this several stage process is that it highlights the process as a guess and check precedure. If someone told you $k$ is between $N/2^q$ and $2n/2^q$, then you could estimate it to even better precision knowing this fact, in the promised time bound. So we need to eliminate the step of being given a guess for $k$. This is done by binary searching over all possible intervals of that type.

To make this work for the case of non-boolean outputs, instead of counting the number of 1s, just sum the values seen. I'll try to find a reference to show that this works rigorously.


Counting occurences of 'a' in a book faster than O(n)? I was asked the following question in an interview:

  How would you count the occurrences of character a in a 500-page book? For simplicity, assume that you are given the book content as a string.

I answered that linear traversal through the book is the best possible solution, since the character can randomly occur in any position, and we cannot figure out until we check every character. However, the interviewer kept insisting on a more efficient algorithm. What algorithm would be more efficient than O(n) for this problem? (if any)

You could try sampling. The assumption that the proportion of a's on any given page is roughly the same as on any other one (and that all pages have roughly the same amount of text) seems reasonable. If $n$ is the total number of pages, you could pick, say $k=n^{4/5}$ random pages, count their average number of characters and the proportion of a's, and scale up to $n$. Your runtime would be $O(n^{4/5})$, and with high probability, your estimate for the number of a's would deviate from the true count by $\tilde O(n^{3/5})$.

You can play with the exponents to get other accuracy-runtime tradeoffs (e.g., in $O(n)$ time you can achieve whp a deviation of $\tilde O(\sqrt n)$).

As pointed out in the comments, an exact count requires $\Omega(n)$ runtime. If the interviewer absolutely insisted on a sublinear runtime, I would suggest sampling.


Effect of different graph operations at algebraic connectivity of graph laplacian? The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this value reflects how well connected the overall graph is.

for an example, "adding self-loops" does not change laplacian eigenvalues (specially  algebraic connectivity) of graph.
Because, laplacian(G)= D-A is invariant with respect to adding self-loops.

My question is:

Does anyone has studied effect of different operations (such as edge contraction) on spectrum of laplacian?
do you know good references?

Remark: the exact definition of the algebraic connectivity depends on the type of Laplacian used.  For this question I prefer to use Fan Chung definition in SPECTRAL GRAPH THEORY. In this book Fan Chung has uesed a rescaled version of the Laplacian, eliminating the dependence on the number of vertices.

Intuitively operations that preserve connectivity will not decrease the eigenvalues. For example, adding edges to the graph does not decrease the connectivity.

In general, if H is a subgraph of a graph G, by interlacing we know that the i-th largest Laplacian eigenvalue of H is no larger than the i-th largest Laplacian eigenvalue of G. A proof can be found in Proposition 3.2.1 of the book "Spectra of graphs" by Brouwer and Haemers. Note that the definition of Laplacian used in the book is not normalized; it has node degrees on the diagonal and -1 (or 0 if there is no edge) in the off-diagonal entries.


Zero of a multivariate cubic equation Given a multivariate cubic equation $f(\vec{x})$ over reals where all coefficients of $f$ are integers, and a hyper-rectangle $B=\bigwedge_i x_i\in[a_i, b_i]$ where $a_i, b_i$ are constant integers, the problem is to check whether $f$ has a zero in $B$.

What’s the complexity of this problem?

Obviously, it is in PSPACE; more precisely, it is a special case of the existential theory of the reals, hence it is in the class $\exists\mathbb R$. A related problem (denoted here as 4FEAS), viz. to check whether a quartic equation with integer coefficients (even without constraints in $B$) has a real zero is $\exists\mathbb R$-complete. Likewise, checking whether a set of quadratic (or cubic) equations has a common zero is $\exists\mathbb R$-complete. On the other hand, if one drops the constraint of $B$, a zero exists trivially if the cubic equation is nondegenerate. Hence, an obvious question is, can we reduce 4FEAS to the current problem?

A variant of 4FEAS with real coefficients is $\mathrm{NP}_\mathbb R$-complete in the Blum–Shub–Smale model, but this question is about the Boolean Turing model, not BSS.

A related question is here: Checking whether two quadratic equations have a common zero

That problem is strongly NP-hard by reduction from 3-SAT:

Each ai is 0, each bi is 1, each negative literal is represented by its propositional variable,

each positive literal is represented by 1 minus that, each clause is represented by the product

of the representations of its literals, and f is the sum of the representations of the clauses.

I don't have any evidence regarding possible ∃ℝ-completeness or membership in NP.


Task Multithreading analysis for a Divide and Conquer algorithm Suppose an algorithm that receive an input array of $n$ elements and it performs a task over each element. All tasks are independent and take $O(k)$ each (being $k$ a variable). Since all tasks are independent this is a fully parallelizable problem.

I have a basic algorithm that uses the Divide and Conquer technique. It receive the input array $A$ and if $|A| > 1$ then it spawn a new thread to process the first half of $A$, and recursively call itself to process the second half. This recursions stops when the function is called with a single element, in which case it runs a series of steps that takes $O(k)$.

I´m using the Dynamic Multithreading model (Introduction to Algorithms, chapter 27) to analyze this algorithm. So, I have an execution graph with n "leafs", representing the basic cases ($|A| = 1$), and it needs $O(n)$ "internal nodes" to divide the work until it reaches the leafs. Given that the longest path has length $O(\log n)$ with a constant cost for each internal node, then the total cost will be $T_\infty = O(\log (n) + k)$ (which is the span). I also can get other measures like the total work $T_1 = O(n + kn)$, and the parallelism $\frac{T_1}{T_\infty} = \frac{n + nk}{k + \log n}$.

Another performance measure of interest is the speedup, which is defined as $\frac{T_1}{T_p}$ (where p is the number of processors used to compute $T_p$).

Finally my question is how do I get $T_p$ (analytically) so I can calculate the speedup?
I cannot simply divide $T_1/p$ since in the first levels of the graph/tree I won't be using all the processors.

Is there any more elegant expression for this than simply dividing the height of the tree before and after $\log p$?

Since you know that you must process each element and tasks are independent, i.e., the algorithm is embarrassingly parallel, in the Dynamic Multithreading model you should simply use a parallel for instead of spawning threads as you do, and let the compiler implement this optimally.

The work (sequential time) is $T_1 = O(nk)$ because you need to process each element and each element requires O(k) time. The span is $T_\infty = O(log n + k)$, and the parallelism is $T_1 / T_\infty = nk / (log n + k)$. In general, you know that, regarding $T_p$, we can only say that:

$T_1/p \leq T_p \leq T_1/p +  T_\infty$

$T_\infty \leq T_p \leq T_1/p + T_\infty$

This is because $T_p$ is a function of the work, span, size $n$ and scheduler behavior. And $T_\infty$ actually means for your algorithm $p = n$.

Now, let's analyze what happens to the speedup by using the Generalized Amdahl's law (derived by Lee). This law describes the speedup of parallel applications in which the computation is made of phases and in each phase a different number of processors is actually used. Think about each level of the directed acyclic graph corresponding to the computation as a phase.

Let $q_i$ be the percentage of a parallel application executed simultaneously by $i$ processors; then, we have:

${T_1} = \sum\limits_{i = 1}^p {{q_i}} {T_1}$

${T_p} = \sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} {T_1}$

Therefore, the speedup is

$\frac{{{T_1}}}{{{T_p}}} = \frac{{\sum\limits_{i = 1}^p {{q_i}} {T_1}}}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} {T_1}}} = \frac{{\sum\limits_{i = 1}^p {{q_i}} }}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }}$

Why is this useful? Because in general it allows you to derive useful bounds. For instance, assuming $q_i = 1/p$ then we can derive an upper bound for the speedup as follows:

$\frac{{{T_1}}}{{{T_p}}} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\frac{1}{p}\sum\limits_{i = 1}^p {\frac{1}{i}} }} = \frac{p}{{\sum\limits_{i = 1}^p {\frac{1}{i}} }} \leqslant \frac{p}{{\log p}}$

In your algorithm, $q_i$ is different from zero only for values of $p$ which are powers of 2; i.e.,  $q_i = 2^i, i = 0,...,\log p$. In the corresponding summation $q_i$ will be divided by $2^i$, giving rise to a summation in which each term is 1. As an example, for $p=16$ the nonzero $q_i$ values are 1,2,4,8,16 and these values must be divided respectively by 1,2,4,8,16 so the sum is 5 and the speedup is 1/5. In general, the speedup of your algorithm is:

$\frac{{{T_1}}}{{{T_p}}} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\sum\limits_{j = 0}^{\log p} {\frac{{{2^i}}}{{{2^i}}}} }} = \frac{1}{{(\log p) + 1}}$

Now compare this with the performances you can obtain in the message passing model, in which your algorithm is executed on $p$ processors. Since the algorithm is embarrassingly parallel, $T_p = O(\frac{n}{p} k)$ (domain decomposition is trivial and requires O(1) time) and the speedup is (as expected for an embarrassingly parallel algorithm) $T_1/T_p = p.$


Is any related work to this m-trails problem ? Yesterday, I discussed with one of my EE friends. She asked me an interesting problem and I simplify it by ignoring the bandwidth cost and model as following:
Given a graph $G=(V,E)$ with its path set $P=\{P_1,P_2,\ldots, P_m\}$ where $P_i$ is a path
between two points in $V$. A path $P_i$ is colored by red if only and only if one of it's edges is colored by red, i.e. $P^c=red$; otherwise $P_i$ is colored by blue, i.e. $P^c=blue$. Find a subset $P_s\subseteq P$ s.t. 1) If for every $j$ color all edges in $G$ by blue except only one $e_j\in E$ by red,
there is a subset $P_s' =\{P_1,P_2,\ldots,P_t\}$ in $P_s$ such that $f(P_1^c,\ldots,P_t^c)=e_j$ where f() is one-to-one mapping; 2) minimize the size of the result set $P_s$.

My questions are:
1) is there any similar work done in TCS?
2) is there any similar work done in graph theory?
3)2) is there any similar work done in networks?
3) any discussions about this problem are welcome.

What is $f$? I seems that you're asking for a one-to-one mapping between a power set over a power set of edges and the edges - which would surely be possible only if there's no more than one edge.


Good books on parser theory? One of my Java projects is a fork of parboiled, and unlike, say, Antlr or JavaCC, parsers are generated at runtime. Grammars generated are Parsing Expression Grammars, or PEGs (I hear another term for them is "packrat").

While the runtime generation adds complexity (bytecode generation involved), another aspect relates to parser theory itself. As I have, unfortunately, no solid background in computer science, I lack theoretical knowledge to map existing code to existing concepts -- in this case, parsers.

Is there a good reference book on parsers which I can purchase and read, or even links on the Internet, which can help me build such a "mapping", accounting for my poor theoretical knowledge?

One book that I can recommend is D. Grune, C. J. H. Jacobs, Parsing Techniques: a Practical Guide.


Algorithm for computing unordered tree edit distance I am trying to compute the edit distance between two dendrograms, one produced from hierarchical clustering, and the other manually constructed from some tree structure. In this setting, the rename operations on leaves of the tree are not allowed, and renames of other nodes (parent nodes) is free.

The tree edit distance for rooted ordered trees has been well studied, but this problem should be considered for the case where input trees are unordered. For the general case, it is known that tree edit distance problem for unordered trees is NP-hard. However, I don't seem to find an algorithm to find the unordered tree edit distance.

Any pointers or insights into this problem is highly appreciated.

A student of ours recently looked into a dynamic programming A* algorithm for computing the unordered tree edit distance (although we adapted it for the ordered tree edit distance). I was not directly involved into this project, but as far as I know, this algorithm explores a search tree that represents all possible edit distances and stops exploring unpromising paths. This way it returns the tree edit distance in the end.

The student also implemented this A* algorithm, so it is not just a theoretical one.

Here's the link: http://ieeexplore.ieee.org/document/6630333/

Hope this helps!


Barriers to show $P=NP$ We all know showing $P\ne NP$ has barriers. We all have studied these barriers because we believe $P\ne NP$.

However assume $P=NP$ and there are wise people who believe that possibility exists. If this is indeed the case then the very fact that we have not seen any good algorithms indicates there might be barriers in this alternate universe as well. Provability of $P\ne NP$ is barrier ridden and we do not know for sure $P\ne NP$ is the truth. We do not know for sure $P= NP$ is the truth either and so is provability of $P=NP$ also barrier ridden?

Mihalis Yannakakis has shown that the traveling salesman problem cannot be solved in polynomial time by using a symmetric linear program.

See the paper Expressing combinatorial optimization problems by Linear Programs, by Yannakakis.

This result was improved recently by  Fiorini,  Massar, Pokutta,  Tiwary, and De Wolf to drop the "symmetric" requirement in Yannakakis' result.


Conditional results implying difficulty of improving upper/lower bounds for permanent Let $A$ be a given square matrix.
Is there any evidence that beating quadratic lower bounds for $B$
such that $\text{det}(B) = \text{per}(A)$ could be hard?

Is there any plausible conjecture which implies that
proving lower bounds is difficult?
Is there any evidence that
proving an $\Omega(n^{2+\epsilon})$ rows (or columns) lower bound
for some $\epsilon > 0$ is hard
(e.g. equivalent to $\mathsf{VP} \ne \mathsf{VNP}$)?

Is there any plausible conjecture which implies that
proving upper bounds is difficult?
Is there any evidence that
proving an $O(2^{n^\epsilon})$ upper bound
for some $\epsilon \in (0,1)$ is hard?

An upper bound of $O(2^{n^{\epsilon}})$ may not be possible for any $\epsilon<1$ unless the Exponential Time Hypothesis (ETH) is false, see

Holger Dell, Thore Husfeldt, and Martin Wahlén.
Exponential time complexity of the permanent and the Tutte polynomial.
Full paper at ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/

That is, if your embedding of the $n\times n$ permanent into a determinant of size $O(2^{n^{\epsilon}})\times O(2^{n^{\epsilon}})$ is fast enough, you could

Transform a 3SAT-instance to a permanent as in the paper above

Transform the permanent to a determinant over the larger matrix

Compute the determinant to find the number of solutions to the
original 3SAT-instance.

The running time for an $n$-variate 3SAT instance would be $O(2^{n^{\epsilon'}})$ for some $\epsilon'<1$ depending on $\epsilon$ if step (2) is fast enough (say polynomial in n for each entry of the larger matrix). This would contradict the ETH.


Are there applications of modular graph decomposition in TCS/complexity theory? What are there some applications of modular graph decomposition in TCS/complexity theory?

I am especially interested in its use in proofs or upper/lower bounds if it occurs.

[1] Modular graph decomposition, Wikipedia.

[2] References for Modular Decomposition, TCS.SE.

Habib and Paul did a great survey on the algorithmic applications of graph modular decomposition.

In our recent result that shows parameterized tractability of INTERVAL DELETION problem (to remove at most $k$ vertices from the give graph to make it into an interval graph), graph modular decomposition does plays an important role. This problem does receive a lot of interest in the parameterized complexity community (though not in the tradition complexity community), and the problems related to graph classes are the most natural candidates of applications of graph modular decomposition.

However, I am not aware of any application of graph modular decomposition in proofs of lower bounds, and I doubt its applicability on the negative side (only a personal biased view).

A final remark.  As far as I know, most algorithmic applications do not use the full power of graph modular decomposition.  For instance, critical cliques are the series modules at the second level of a modular decomposition tree (the first level consists of every single vertex); and twins are (not necessarily strong) modules made of two adjacent vertices.


Deterministic Parallel algorithm for perfect matching in general graphs? In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. And there are problems BELIEVED to be in $\mathsf{NC}$, but a proof is not found yet.

Perfect Matching problem is one of the most fundamental problem raised in graph theory: given a graph $G$, we have to find a perfect matching for $G$. As I could found on the internet, despite of the beautiful polynomial time Blossom algorithm by Edmonds, and a RANDOMIZED parallel algorithm by Karp, Upfal and Wigderson in 1986, only a few subclasses of graphs are known to have $\mathsf{NC}$ algorithms.

In Jan. 2005 there's a post in the blog Computational Complexity that claims it remains open whether Perfect Matching is in $\mathsf{NC}$. My question is:

  Is there any progress since then, beyond the randomized $\mathsf{NC}$ algorithm?

To clarify my interest, any algorithm which deals with GENERAL graphs are nice. Although algorithms for subclasses of graphs are OK too, that may be not on my attentions. Thank you all!

EDIT at 12/27:

Thank you for all your help, I try to summarize all the results in one figure:

The lowest known classes contain the following problems:

Matching in general graphs: $\mathsf{RNC}$ [KUW86], $\mathsf{RNC}^2$ [CRS93]
Matching in bipartite planar/constant genus graphs: $\mathsf{UL}$/$\mathsf{SPL}$ [DKT10]/[DKTV10]
Matching when the total number is polynomial: $\mathsf{SPL}$ [H09]
Lex-first maximal matching: $\mathsf{CC}$ [MS89]

Furthermore, under plausible complexity assumption: $\mathsf{SPACE[n]}$ requires exponential circuits, Matching in general graphs is in $\mathsf{SPL}$ [ARZ98].

$NC$ algorithms for perfect matchings in general graphs is still open but there has been some progress. Here are a few that I am aware of:

For general graphs, Agrawal-Hoang-Thierauf showed that given the promise that the number of perfect matchings is small, there is an $NC^2$ algorithm to enumerate all of them.

For the class of planar graphs, the pfaffian plays a big role. Kastelyn showed how every planar graph can be oriented in a way such that the pfaffian exactly equals the number of perfect matchings. (This was used by Valiant in to give "Holographic algorithms" for various problems) Mahajan-Subramanya-Vinay showed how the pfaffian can be computed in $NC$ using modifications of clow sequences. (Kastelyn in fact gives an algorithm to find the embedding in $P$ but I'm not sure if the pfaffian embedding can also be computed in $NC$; if yes, that would mean that counting perfect matchings in planar graphs is in $NC$.)

And a recent result of Vinodchandran-Tewari show that the isolation lemma can be "derandomized" for planar graphs (using Green's theorem!) to put planar reachability in $UL$. But $NC$ algorithms for planar matchings are still open (thanks to Raghunath for correcting my claim that it is in $UL$). An $NC$ algorithm for bipartite planar matchings was given by Datta-Kulkarni-Roy

Hope this helps.


Partition graph into complete disjoint subgraphs while maximising sum of edge weights Has this problem been studied?

We start with a complete, simple, undirected graph with edge weights. The problem is to delete edges so as to partition the graph into complete disjoint subgraphs while maximizing the sum of the edge weights over the whole graph (deleted edges not being counted).

There is no constraint on the size or number of subgraphs in the solution.

Note this is interesting only if there are negative edge weights. Otherwise the solution would be to take the whole graph.

Clearly we would like to delete all the negative-weight edges while keeping all positive-weight edges, but the requirement that disjoint subgraphs be complete makes a trade-off between these goals.

I have seen discussion of similar graph partitioning problems but not this exact one. (Eg it is a bit like the maximum clique problem, but here I want to put every node in a disjoint clique, in the optimal way). I am guessing it is NP-complete. I am interested to know where to start looking for efficient heuristics.

In addition to Correlation Clustering, this is known as Clique Partitioning or Weighted Cluster Editing, see e.g.

M. Grötschel and Y. Wakabayashi, A cutting plane algorithm for a clustering problem, or
Sebastian Böcker, Sebastian Briesemeister, and Gunnar W. Klau, Exact Algorithms for Cluster Editing: Evaluation and Experiments.


Definition of a hereditary relation Sassone, V., Nielsen, M. and Winskel, G. (1996) Models for Concurrency: Towards a Classification. Theoretical Computer Science, 170 (1-2). pp. 297-348., p. 307:

  Given a tree $S$, define … $\#$ is the
  least hereditary, symmetric,
  irreflexive relation on $Tran_S$ such
  that $(s,a,s')\#(s,b,s'')$ if $s'\neq s''$.

What is a hereditary relation? If I replace in the quote “the least hereditary, symmetric, irreflexive relation” with “the least hereditary relation”, do I get the equivalent statement?

In Definition 2.1 of Contextual Petri Nets, Asymmetric Event Structures, and Processes, Baldan, Corradini and Montanari are working in the setting of prime event structures, which consist of a set of events $E$ along with binary relations $\#$ and $\le$ on $E$, known as the conflict and causality relations, respectively. This is the close to what is going on in your your setting.

In this context, they state that the relation $\#$ is hereditary with respects to $\le$ whenever for all $e_0,e_1,e_2\in E$, if $e_0\#e_1$ and $e_1\le e_2$, then $e_0\#e_2$.

It does not make sense to say that a relation is hereditary on its own; it is always taken with respect to another relation.

In general, saying that a relation is the least hereditary relation is not equivalent to saying that it is the least hereditary, symmetry, irreflexive relation, as the definition of hereditary does not imply that the relation is symmetric.

In the specific case you mention, it does seem to be the case – after going into the details of the paper a little more – that one need not specify that the relation is symmetric or irreflexive, as these come for free from the context. Well spotted!!


Randomness versus Quantumness in factorization The best deterministic factorization algorithm that is currently known runs in $O(N^{\frac{1}4+\epsilon})$ arithmetic steps.

Randomness and quantumness improves upon this.

I believe Quadratic/Number field sieve run in randomized subexponential time. What is it that quantumness provides that sieve techniques cannot provide? What exact barrier does Shor's algorithm break that randomness cannot?

What is it that quantumness provides that sieve techniques cannot provide?

It is more a question why quantum computers are believed to be more powerful than classical  computation models. Short: Quantum computers provide superpositions of quantum states.

Randomized algorithms are restricted to be in a certain state with some (constant) error probablility. Quantumness provides the posibility of evaluating function on every possible state and afterwards measuring a certain state with some error probability.

What exact barrier does Shor's algorithm break that randomness cannot?

The quantum states represent the accepted states as well as the rejected states. Shor's algorithm evaluates the accepting states in such an extent that the accepting states are more likely to be measured. Also the quantum algorithm can manipulate all states at the same time. A randomized algorithm is bound to increase the probability of being in such a accepting state, looping often enough to get a certain probability (or extending some other variable).


Has this bipartite graph problem been studied? I have a directed bipartite graph with vertex sets $U$ and $V$, directed edge sets $E(U,V)$ and $E(V,U)$, and a demand function $d \colon U \rightarrow \mathbb{Z}$. I want to find a function $f \colon V \rightarrow \mathbb{Z}$ that "meets the demand" in the following way. Extend $f$ to a function on the edges $f' \colon E \rightarrow \mathbb{Z}$ defined by
\begin{equation}
f'(x, y) = \begin{cases}f(x) & (x,y) \in E(V,U)  \\
             -f(v) & (x,y) \in E(U,V)
\end{cases}.
\end{equation}
So, $f'(e) = f(u)$ when $e=(v,u)$ is directed from $V$ to $U$, and $f'(e) = -f(u)$ otherwise. Now I want to $f$ to satisfy the demand such that for each $u \in U$ the edges incident to $u$ sum up to the demand on $u$. That is,
\begin{equation}
\sum_{e \in E(V,U)} f'(e) - \sum_{e \in E(U,V)} f'(e) = d(u).
\end{equation}
My initial thought was that this could be reduced to some kind of flow problem, but I don't know how to deal with the fact that for each vertex the amount of flow on each edge incident to that vertex must be equal.

This can be solved in polynomial time: it is a system of linear equations over the integers, so you can solve it in polynomial time by forming the Hermite normal form.  This might not be the most efficient way to solve it...

If you want to express it as a flow, you could try the standard transformation of replacing every vertex $v$ with two vertices $v_\text{in},v_\text{out}$ with an edge $v_\text{in} \to v_\text{out}$; edges directed towards $v$ are replaced with edges to $v_\text{in}$, and edges out of $v$ are replaced with edges out of $v_\text{out}$.  I don't know whether that will help in your situation.


Can I get all min-cuts after executing Push-Relabel? The push-relabel algorithm (here is push-relabel as pseudo-code) assigns a distance-label to each node.

After executing push relabel, you have those distance labels and a max flow in a given network $N = ((V, E), s, t, c)$ with $E \subseteq V \times V$, $s,t \in V$, $c:E\rightarrow \mathbb{R}_0^+$.

How to get one min-cut after executing push-relabel:

Find a number $x \in \mathbb{N}: 0 < x < |V|$
$S := \{v \in V | dist(v) > x\}$ and $V \setminus S = \{v \in V | dist(v) < x\}$
There is no edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network.
$(S, V \setminus S)$ is a min-cut.

Proof of correctness:

Such a number $x$ exists, because you have $|V|$ nodes that can have labels, $s$ has the label $|V|$, $t$ has the label $0$. So you have $|V|-1$ possible numbers for $x$ and only $|V|-2$ nodes that can have labels.
This is a valid partition of $V$, as no node has label $x$.
If there was an edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network it would have to be ...

$dist(u) \geq dist(v) + 2$ as we defined $S$ like this:
$\begin{align}
                  & dist(u) > x \land x > dist(v) \\
      \Rightarrow & dist(u) - 1 \geq x \land x \geq dist(v) + 1\\
      \Rightarrow & dist(u) \geq dist(v) + 2 \end{align}$)
For every edge in the residual network you can say: $dist(u) \leq dist(v) +1$

$\Rightarrow 2 \leq 1 \Rightarrow $ Error $\Rightarrow$ there is no edge between $S$ and $V \setminus S$ in the residual network
As there is no free capacity in the residual network between the sets $S$ and $V \setminus S$, the value of the min cut is the max flow. According to max-flow min-cut theorem $(S, V \setminus S)$ is a min-cut.

So the given algorithm can find at least one min-cut quite fast after push-relabel was executed. As $x$ can have more values (the labels of some nodes might be the same and they can go up to $2|V|-1$ as far as I know), you can also find more than one min-cut.

My question:

Do I find all min-cuts this way?

I assume that your question is "Do I find all min s-t-cuts this way?"

I believe the answer is no. Note that there may be an exponential number of minimum s-t-cuts (connect vertex s to vertices {1,2,3, ...,n} and then each of these are
connected to vertex t -- then there are 2^n min-s-t-cuts).

The way that I know for sure to enumerate all min-s-t-cuts is to recursively enumerate all directed cuts in the residual graph after the contraction of all
strongly connected components. This algorithm can produce
each cut in linear time per cut. If you need a detailed description of the
enumeration algorithm I can provide to you the pseudocode.


Graph representation using edge sets Given a directed graph $(V,E)$ with $E\subseteq V\times V$, a source vertex $v_0\in V$ from which all other vertices are reachable, and a set $I$ of unique identifiers for the edges in $E$ (i.e., there is a bijection $I \rightarrow E$), we can construct a set $M\subseteq V \times \mathcal{P}(I)$ containing exactly those $(v,S)$ such that there is a path from $v_0$ to $v$ using exactly the edges represented by $S$ (in any order and repetition).
For example, the graph $(\{A,B\},\{(A,B),(B,A)\})$ with $v_0=A$ and $I(a)=(A,B), I(b)=(B,A)$ would be represented as $\{(A,\emptyset),(B,\{a\}),(A,\{a,b\}),(B,\{a,b\})\}$.

I wonder under which conditions the inverse construction is possible: assuming $M$ is "consistent" (there is at least one graph satisfying it), what conditions are needed for $M$ to represent a unique graph? Certainly $M$ has to satisfy some kind of "closure" property, like: for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $|S|=|P|+1$.
Then a (hopefully deterministic) algorithm would construct $G$ by picking elements from $M$ in order of increasing cardinality.

Edit: of course the closure property should be that for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $S= P\uplus\{x\}$.
But this is not strong enough if self-loops are allowed: $\{(A,\emptyset),(B,\{a\}),(B,\{a,b\})\}$ represents two non-isomorphic graphs (one with $b=(B,A)$, the other with $b=(B,B)$).

Edit: I just noticed that there are counter-examples even without self-loops: $M=\{(A,\emptyset),(B,\{a\}),(C,\{a,b\}),(C,\{a,b,c\})\}$ may imply $c=(C,B)$ or $c=(C,A)$ (or $c=(C,C)$).

Has somebody worked on this kind of problem?

I think you can build $G$ in iterations:

$M$ contains all $(v, \{e\})$ where $v \in \Gamma(v_0)$ ($\Gamma$ being neighborhood); so you can identify all edges to nodes that are distance 1 from $v_0$, as well as the nodes themselves; you can also identify the edges between nodes in $\Gamma(v_0)$ by looking for pairs $(v, \{e_1, e_2\})$, where $v \in \Gamma(v_0)$ and $e_1$ is an edge between $v_0$ and some $u \in \Gamma(v_0)$.
then, iteratively, you can identify all edges and nodes in the subgraph of $G$ induced on the vertices which are distance at most $i$ to $v_0$ (call it $G_{i}$), using $G_{i-1}$. The idea is the same as above: you look for pairs $(v, S)$, where all but one edges in $S$ are in $G_{i-1}$; this gives $V(G_i \setminus G_{i-1})$. Then you can identify edges between vertices $u, v \in V(G_i \setminus G_{i-1})$ by looking for pairs $(v, S)$, where $S = S' \cup \{e_1\} \cup \{e_2\}$, such that $S' \subseteq E(G_{i-1})$, and $e_1$ has one point in $G_{i-1}$ and the other point is $u$; $e_2$ is the edge $(u, v)$.

Are you aware of the reconstruction and edge reconstruction conjectures? They have the same spirit as your probelm and, as far as I know, are open. Check out this beautiful half page proof by Lovasz that the edge reconstruction conjecture is true for any graph that has more edges than its compliment.


Is the Witness Size of Membership for Every NP Language Already Known? The question occurred to me when I get Dana Moshkovitz answer to another topic.

Let $L$ be an NP Language, and let $R_L$ be the respective NP relation. We know that there exists some polynomial $p$ such that:

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

The above statement only requires the existence of such $p$, but it does not force it to be explicitly determined. In contrast, for every NP language I know, $p$ is already known:

For SAT, the size of witness is equal to the number of atoms appearing in the formula.
For Hamiltonicity, the size of witness is $O(|V|)$, where $V$ is the vertex set.
For Graph 3-Coloring, the size of witness is $O(|V|)$, where $V$ is the vertex set.

  Does there exist an NP language (even an artificial one), for which we know there exist some polynomial $p$ bounding the size of witness, yet we cannot explicitly determine $p$?

If you don't mind artificial languages, we can construct such problems using pretty much any number k whose value is unknown to mathematicians. For example, we don't know the value of R(5,5) (the fifth Ramsey number), or the size of the largest excluded minor of the family of knotless graphs (this number is finite due to the Robertson-Seymour theorem), or the value of BB(10), where BB() stands for the Busy Beaver function. Let k equal any of these numbers. We know that k is finite, but we don't know the value of k.

Now construct some problem in NP where the witness is of size $O(n^k)$. Off the top of my head I can't think of a nice way of doing this, but here's one way. Let the input be a succinct description of a graph. Since the description size is n, the graph is on exponentially many vertices. (For example, maybe the input is a circuit that accepts two inputs x and y and tells you if (x,y) is an edge in the graph.) The question is to determine if the graph contains a path of length $n^k$. This problem is in NP because the prover can send the list of vertices on the path in order, which the verifier can check. The size of the witness is $n^k$.


Iterating over all stabilizer operations on $k$ qubits Stabilizer circuits, i.e. quantum circuit that only use the $H$, $\sqrt{Z}$, and $CNOT$ gates, can only implement a finite subset of all possible unitary operations.

I want to iterate over all these operations for a small number of qubits, or sample from the space for a larger number of qubits.

I could just use the stabilizer circuits themselves as stands ins for the operations: iterate over the possible circuits with up to $n$ operations and $k$ qubits, sample from the possible circuits, etc. But many circuits encode the same operation, so focusing on the circuits would create extra work and bias the sampling. Also there's not a clear length cut-off.

What's a straightforward way to generate all the operations in the group? To sample from the group?

Since stabilizer circuits are exactly those which map stabilizers to stabilizers, you could characterize them via their action on a basis of stabilizers, see for instance Sec 2.3 of http://home.lu.lv/~sd20008/papers/essays/Clifford%20group%20[paper].pdf.


Collatz Conjecture & Grammars / Automata I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar?  (or any other attempts in the CS community to deal with this class of generative phenomena & their "halting" properties).

I guess these papers by Jeffrey C. Lagarias could help:

The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author).
The 3x+1 Problem: An Annotated Bibliography, II (2000-2009).

Another good source is the recent book "The Ultimate Challenge". In it  chapter "Generalized $3x+1$ functions and the theory of computation",section $\#$ 8, can also be of interest.


Bounds on the size of smallest decision tree for a boolean function? Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?

It seems to me that assuming $f$ has $n$ variables and $m$ true points then any minimal decision tree has at most $$ 2^{\lceil{\log_2 m}\rceil}−m+m⋅(n−\lceil{\log_2 m}\rceil) $$ 0-leaves (obviously, one can take the dual as well). I am wondering if whether this sort of thing has been covered before (I presume it has somewhere).

I think the number of true points isn't a good measure to say anything about the size of the smallest decision tree.

There is a chapter in Branching programs and binary decision diagrams: theory and applications by Ingo Wegener about the size of decision trees for boolean functions.

The size of the smallest DT is determined up to constant factors by the number of leaves of the tree. There is a lemma in the book that says: If you have a DT for a function $f$ with $s_0$ 0-leaves and $s_1$ 1-leaves then $f$ can be represented by a DNF with $s_1$ monomials and a CNF with $s_0$ clauses. So even if you have a function with only a small number of true points, the size of the smallest DT could be very large. So you need small size of CNF and DNF to have a small DT size.

There is a upper bound of the DT size with respect to the sum of the minimal number of monomials of $f$ and the minimal number of monomials of $\overline{f}$. Lets call this sum $DCNF(f)$. Then you have the following upper bound for the number of leaves $DT(f)$ of the smallest DT for the function $f: \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace$
$$ DT(f) \leq n^{O(log^2 DCNF(f))}. $$


Are AND&OR circuits P-complete? The AND&OR gate is a gate which is given two inputs and returns their AND and their OR. Are circuits made only out of the AND&OR gate, without fanout, capable of doing arbitrary computations? More precisely, is polynomial time computation logspace reducible to AND&OR circuits?

My motivation for this problem is rather strange. As described here, this question is important for computation inside the computer game Dwarf Fortress.

If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.

Comparator circuits are built by composing these comparator gates together but allowing no more fan-outs other than the two outputs produced by each gate. Thus, we can draw comparator  circuits using the notations below (similarly to how we draw sorting networks).

We can define the comparator circuit value problem (CCV) as follows: given a comparator circuit with specified Boolean inputs, determine the output value of a designated wire. By taking the closure of this CCV problem under logspace reductions, we get the complexity class CC, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate.

In this recent paper, Steve Cook, Yuval Filmus and I showed that even when we use AC$^0$ many-one closure, we still get the same class CC. To the best of our knowledge at this point, NL $\subseteq$ CC $\subseteq$ P. In our paper, we provided evidence that CC and NC are incomparable (so that CC is a proper subset of P), by giving oracle settings where relativized CC and relativized NC are incomparable. We also gave evidence that CC and SC are incomparable.


Is the Cheeger constant $\mathsf{NP}$-hard? I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for this statement. Whom should I give credit for it? In an old paper (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar only proves this assertion "for graphs with multiple edges".

I too encountered this issue when I was writing a paper that required a citation to hardness of edge expansion (or Cheeger constant) defined as $\min_{S \subset V, |S| \leq |V|/2} |\delta(S)|/|S|$. The classic paper of Leighton and Rao on separators ( http://dl.acm.org/citation.cfm?id=331526 ) mentions that this is a hard problem and refers to the paper of Garey, Johnson and Stockmeyer (http://www.sciencedirect.com/science/article/pii/0304397576900591). I could not figure out for a while what they were referring to since there is no mention of edge expansion in the referred to paper. I communicated with Avi Wigderson about this. It finally transpired that one can use the hardness of Max-Cut as shown in the Garey et al paper to relatively easily show that edge-expansion is hard. I forget the details now but it should not be hard to recreate. The paper of Blum etal on hardness of checking whether a graph is a superconcentrator does not directly imply hardness of edge expansion. They are technically not the same problem.


ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$ The PCP theorem can be stated like this :

There is a polynomial time reduction from SAT to  $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $\psi$ of  $Gap\text-MAX\text-3SAT_{c}$ such that

If $\phi$ is satisfiable, so is $\psi$.
If $\phi$ is unsatisfiable, then $OPT(\psi) \leq c$, i.e., there is no assignment to the variables of $\psi$ that satisfies more than a fraction $c$ of the  clauses.

What is the blow-up of this reduction? That is, what are the parameters of the instanceof  $Gap\text-MAX\text-3SAT_{c}$ in terms of parameter of the given instance of SAT. Is the blow-up linear?

I think the best known result is that the blow-up can be quasi-linear (the new instance has size $n\cdot(\log n)^{O(1)}$). This is given in Dinur's 2007 paper (Thm 8.1), which is also cited by the Moshkovitz-Raz paper mentioned by Yuval Filmus.

As far as I know it is still open if the blow-up can be brought down to linear. Some people call this the Linear PCP conjecture, see e.g. the recent paper by Bonnet, Egri and Marx


Constrained version of vertex cover in a bipartite graph Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if there is a vertex cover $A\cup B$ with $|A|\leq l$
and $|B|\leq k$,  where $A\subseteq V_1, B \subseteq V_2.$

Now, I have following two questions:

1) What is the complexity of the above problem when both $k$ and $l$ are part of input. (Intuitively, it appears to be hard.) If it is hard, then is there any PTAS known to approximate the problem.

2) What is the complexity of the problem when one of the parameters $k$ or $l$ is constant?

Pls let me know if there is any doubt about the problem.

The following is a list of results I'm going to prove:

if $k$ and $l$ are parts of the input and $d = 1$ is a fixed constant then the problem is polynomial time solvable
if $k$ and $l$ are parts of the input and $d \ge 2$ is a fixed constant then the problem is NP-complete
if $k$ is a fixed constant then the problem is polynomial time solvable
if $l$ is a fixed constant then the problem is polynomial time solvable

The first two bullet points address question number 1 and the last two address question number 2.

lemma: if we know $A \subseteq V_1$ with $|A| \le l$ (or $B \subseteq V_2$ with $|B| \le k$), we can decide in polynomial time whether there exists $B \subseteq V_2$ with $|B| \le k$ (resp $A \subseteq V_1$ with $|A| \le l$) such that $A \cup B$ is a vertex cover

For the proof of this lemma, we do not use the constraint that vertices in $V_1$ have degree at most $d$. Therefore, the situation is symmetric in the two parts of the bipartite graph, and we can restrict our attention to just one part of this lemma: we wish to show that if $A \subseteq V_1$ with $|A| \le l$ then we can decide in polynomial time whether there exists $B \subseteq V_2$ with $|B| \le k$ such that $A \cup B$ is a vertex cover.

Let $B' = \{v \in V_2 | \exists x \in V_1 \backslash A \text{ s.t. } (x, v) \in E\}$.

Suppose that for some $b \in B'$, it is the case that $b$ is not in $B$. By definition of $B'$, there exists an $x \in V_1 \backslash A$ such that $(x,b) \in E$. Then that edge has $x \in V_1$ with $x \not\in A$ and $b \in V_2$ with $b \not\in B$, so $A \cup B$ is not a vertex cover.

Thus in order for $A \cup B$ to be a vertex cover, it must be that $B' \subseteq B$.

Next suppose $B' \subseteq B$. Then consider any $(x, v) \in E$. If $x \in A$ then this edge is covered. If $x \not \in A$ then $v \in B'\subseteq B$ by definition of $B'$, so again the edge is covered. Thus $A \cup B$ is a vertex cover.

So $A \cup B$ is a vertex cover if and only if $B' \subseteq B$. Then there exists a $B$ with $|B| \le k$ such that $A \cup B$ is a vertex cover if and only if $|B'| \le k$.

So in order to decide whether there exists a $B$ with $|B| \le k$ such that $A \cup B$ is a vertex cover, all we have to do is compute $|B'|$ and compare with $k$. This can be done in polynomial time.

If $k$ and $l$ are parts of the input and $d = 1$ is a fixed constant then the problem is polynomial time solvable

Begin by removing all vertices of degree zero since the presence or absence of those vertices in a set does not affect whether that set is a vertex cover.

Since $d = 1$, we see that in the remaining graph, every element of $V_1$ has exactly one neighbor. We can conclude that $G$ has $|V_2|$ connected components, each of which consists of one element of $V_2$ together with all of its neighbors in $V_1$.

We wish to know whether it is possible to construct a vertex cover $A \cup B$ with $A \subseteq V_1$ and $B \subseteq V_2$ where $|A| \le l$ and $|B| \le k$.

Each connected component of the graph provides a choice: either $B$ must contain the element of $V_2$ in that component or $A$ must contain each element of $V_1$ from that component.

Then in order to minimize the size of $A$ while maintaining $|B| \le k$, it is clearly optimal to choose $B$ such that it contains the elements of $V_2$ with largest degree.

Since we know the optimal value of $B$ (in polynomial time), we can apply the lemma to solve the problem in polynomial time.

If $k$ and $l$ are parts of the input and $d \ge 2$ is a fixed constant then the problem is NP-complete

First note that the problem is clearly in NP since the set $A \cup B$ forms a certificate. Thus we must simply prove the problem NP-hard in order to show NP-completeness.

We do this by reduction from the clique problem.

Suppose we are given a clique instance in the form of a graph $G' = (V', E')$ and a value $k'$. This instance is a yes instance if and only if there exists a clique in $G'$ of size $k'$.

Then we construct an instance of our problem consisting of $G = (V_1, V_2, E)$, $k$, and $l$ as follows:

$V_1 = E'$
$V_2 = V'$
$E = \{(e, v) \in E' \times V'| v \text{ is an endpoint of } e\}$
$l = |E'| - \frac{k'(k' - 1)}{2}$
$k = k'$

Note that each element of $V_1$ has exactly two neighbors (which is ok since $d \ge 2$).

This reduction is clearly polynomial time, since each part of the output instance can be computed from the input instance very quickly.

Suppose the input instance in a yes instance. Then let $B$ be a clique in $G'$ of size $k'$ (which exists since the input instance is a yes instance). Let $A \subseteq E'$ contain those edges of $G'$ which are not in the clique $B$. There are $\frac{k'(k' - 1)}{2}$ edges in the clique, so $|A| = |E'| - \frac{k'(k' - 1)}{2}$.

Thus we have found $A \subseteq V_1$ and $B \subseteq V_2$ with $|A| \le l = |E'| - \frac{k'(k' - 1)}{2}$ and $|B| \le k = k'$. The only thing left to do in order to show that the output instance is a yes instance is to show that $A \cup B$ is a vertex cover.

So consider any edge $(e, v) \in E$ (where $e \in V_1 = E'$ and $v \in V_2 = V'$). If $e \in A$ then the edge is covered. If $e \not\in A$ then $e$ must by one of the edges in the clique $B$ (in graph $G'$). By the definition of $E$, $v$ is an endpoint of $e$ (which is an edge in the clique $B$). Thus $v \in B$ and again the edge $(e, v)$ is covered. We see that $A \cup B$ is a vertex cover.

We showed above that if the input instance is a yes instance, so is the output instance.

Now suppose that the input instance is not a yes instance. Suppose we have $A \subseteq V_1$ with $|A| \le l = |E'| - \frac{k'(k' - 1)}{2}$ and $B \subseteq V_2$ with $|B| \le k = k'$. Since the input is not a yes instance, there is no clique in $G'$ of size $k'$; therefore fewer than $\frac{k'(k' - 1)}{2}$ edges in $G'$ have both endpoints in $B$. Then since $V_1 \backslash A = E' \backslash A$ contains at least $\frac{k'(k' - 1)}{2}$ elements, each of which is an edge of $G'$, we conclude that at least one edge in $E' \backslash A$ has an endpoint not in $B$.

Let $e = (w, v)$ be an edge in $E'$ with $e \not\in A$ and $v \not\in B$. Then the edge $(e, v)$ (which is in $E$ by the definition of $E$) is not covered, and so $A \cup B$ is not a vertex cover.

We see then that in the case that the input instance is a no instance, the answer to the output instance is no as well.

We showed above that the reduction is polynomial time and answer preserving. Since the input problem (clique) is NP-hard, the output problem is NP-hard as well.

If $k$ is a fixed constant then the problem is polynomial time solvable

The number of sets $A$ with $|A| \le k$ is $|A| \choose kl$, which is polynomial in the size of the input since $k$ is a fixed constant.

Furthermore, these sets are easily enumerable.

For each candidate value of $A$, we simply apply the lemma to determine whether there exists a corresponding value of $B$ such that $A \cup B$ solves the problem.

If a solution is found, the answer to the overall problem is yes, and if no solution is found, the answer to the overall problem must be no.

If $l$ is a fixed constant then the problem is polynomial time solvable

The number of sets $B$ with $|B| \le l$ is $|B| \choose l$, which is polynomial in the size of the input since $l$ is a fixed constant.

Furthermore, these sets are easily enumerable.

For each candidate value of $B$, we simply apply the lemma to determine whether there exists a corresponding value of $A$ such that $A \cup B$ solves the problem.

If a solution is found, the answer to the overall problem is yes, and if no solution is found, the answer to the overall problem must be no.


Does bit commitment yield oblivious transfer in the information-theoretic security model? Suppose you have two arbitrarily powerful participants who don't trust each other. They have access to bit commitment (e.g., sealed envelopes containing data that one player can hand to the other but that can't be opened until the first player gives the second a key). Can you use this to build an oblivious transfer protocol. Is this true even if the players agree to open all the envelopes at the end to detect cheating (e.g., after the poker hand is played, everybody agrees to reveal their cards)?

I assume that you can't get oblivious transfer out of bit commitment, because oblivious transfer is cryptographically universal, and I can't find any references that say bit commitment is, but is there a proof somewhere that you can't do it?

Finally, has anybody looked at the problem if the players are quantum?

No, commitment has strictly lower complexity than OT. I think an easy way to see this is the approach taken in Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation by Maji, Prabhakaran, Rosulek in TCC 2009 (disclaimer: self promotion!). In that paper we have a result characterizing what you can do given access to ideal commitment in the UC model with statistical security.

Suppose there were a statistically secure protocol (against malicious adversaries) $\pi$ for OT using access to ideal black-box bit commitment. Then $\pi$ must be secure against honest-but-curious adversaries as well (not as trivial as it probably sounds, but not very difficult to show either). But you could compose $\pi$ with the trivial honest-but-curious protocol for commitment, and have an honest-but-curious OT protocol that is statistically secure with no setups. But this is known to be impossible.

Another way to see it is through Impagliazzo-Rudich. If you have computationally unbounded parties and a random oracle, you can do commitment (since all you need are one-way functions) but you cannot do things like key agreement, and thus not OT.


Is there a computation class describing FOR-programs, what are the limitations? I've written an unpublished paper that describes FOR-programs.

FOR-programs are programs that only contain bounded for loops and basic operations (assignment, addition, multiplication, etc.). A bounded for loop is a for loop with a bound on the number of times that it can loop. This bound is fixed before entering the for loop for the first time and is not changed until the loop completes.

Is there a complexity class that captures this type of programs? Since the number of for loops in a program is known in advance, the time complexity is of course limited to $O(n^k)$ with $k$ nested for loops. Thus, all FOR-programs run in polynomial time. Are there additional limitations to this class of programs?

Having just asked a very similar question:

The language of for programs can express exactly the primitive recursive functions -- see Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.  (I found a copy online here.)

The complexity class for the p.r. functions is called PR.


Shortest string containing all fixed-length substrings This is related to a math.SE question I asked, but I've realized I want a slightly different form and it's probably more of an algorithms question.

Fix an alphabet $\Sigma$.  Let $P(n)$ be all length-$n$ strings over $\Sigma$.  What is the shortest string $S$ such that every $s \in P(n)$ is a substring of $S$?

For example, let $\Sigma = \{a\}$ and $n=1$; then clearly $S=a$ is minimal.  If instead $\Sigma = {a,b}$ and $n=2$, $P(2) = {aa, ab, ba, bb}$ and $S = aabba$ is minimal.

Clearly we are solving "shortest common superstring" over $P(n)$, and it's known to be MaxSNP hard. I'm wondering if this special form, with $P(n)$ containing all substrings of $\Sigma$ might be easy?!

This is called a de Bruijn sequence ( http://en.wikipedia.org/wiki/De_Bruijn_sequence ).  You can generate it by taking an Euler tour of a de Bruijn graph, but there are also other ways.  You can use de Bruijn sequences to break into 1990s-era cars efficiently ( http://everything2.com/title/Weak+security+in+our+daily+lives ) among many other applications.


Exact algorithm for edge coloring Wikipedia lists several exact algorithms for graph vertex coloring.

Are there any exact algorithms that are designed specifically for graph edge coloring?

edit:

Just came across my mind, i think it should be ok (pure bruteforce). I didnt try to implement this yet. Please comment if you see something wrong. Just to say again - algorithm should check whether graph is edge colorable with d or d+1 colors where d is max degree of all vertices in given simple graph, and to find one coloring...

colorEdge(edge, color, extra) {
    if (edge colored) return;  //if already colored, return
    if (can be colored in color) color it; //if color can be applied, apply it
    else {
        //else, 'd+1'-st color neded, so color it with that color, continue finding
        //coloring with d+1 colors
        extra = !extra;
        color it in color extra;
    }

    //recursivly try to color adjacent edges with available colors
    for each color c' from set of d colors {
        for each edge k adjacent to current {
            colorE(k, c', extra)
        }
    }
}

//main
bool extra = false;
for each color b from set of d colors {
    colorEdge(some starting edge, b, extra)
    if (!extra) break;
}

You can edge color faster than applying the fastest vertex coloring algorithm to the line graph: see http://arxiv.org/abs/1007.1161 for one such algorithm. What interests me is why can't we find something that is much faster...


Confusion about covering number Problem

I do not understand why larger $p$ will give a larger covering number.

Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \| x \| _ { p }$ when $p > q>0$) and thus should give smaller covering set. Covering number is essentially the minimum cardinality of covering set, so it seems that larger $p$ should give smaller covering number?

Since you've tagged machine learning, I'll address this setting. Indeed, for the usual $\ell_p$ norms on $\mathbb{R}^n$, we have $||x||_p\le ||x||_q$ for $p>q$. However, in machine learning applications, these are normalized norms (see, e.g., Mendelson, A few notes on Statistical Learning Theory
https://people.eecs.berkeley.edu/~jordan/courses/281B-spring04/readings/mendelson.ps
).
Let $D$ be a distribution on $\{1,\ldots,n\}$. Then the corresponding $\ell_p(D)$ norm is defined by
$$
||x||_{\ell_p(D)}^p = \sum_{i=1}^n D(i)|x_i|^p.
$$
You can verify that for these norms, the inequality goes the other way:
$||x||_{\ell_p(D)}\ge ||x||_{\ell_q(D)}$ for $p>q$. This explains the covering number inequality as well.


What is the best exact algorithm to compute the core of a graph? A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H.
http://en.wikipedia.org/wiki/Core_%28graph_theory%29

Given a graph G, what is the best known exact algorithm to find its core?

Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see Hell and Nesetril.  There are settings where core computation can be done efficiently, see Efficient Core Computation in Data Exchange by Georg Gottlob and Alan Nash for a database setting; here some reasonable restrictions on the kinds of constraints in the database schema allow cores to be computed efficiently.

Edit: Other than the Gottlob/Nash work mentioned above, I am not aware of any other attempts to provide efficient algorithms for core computation.  Pointers to any algorithms better than brute force (exact or otherwise) would be welcome.


Techniques for showing non-derivability in logics and other formal proof systems In proof systems for classical propositional logic if one want to show that a certain formula $\psi$ is not derivable one simply shows that $\neg\psi$ can be derived (although other techniques certainly are possible). Non-derivability follows essentially from the soundness and completeness of the proof system.

Unfortunately for non-classical logics and more exotic proof systems (such as the rules underlying operational semantics) no such direct technique exists. This could be because the non-derivability of $\psi$ does not imply that $\neg\psi$ is derivable, as is the case with intuitionistic logics, or simply that no notion of negation exists.

My question is given a proof system $(\mathcal{L},\vdash)$, where $\vdash\;\subseteq\mathcal{L}^*\times\mathcal{L}$, (and presumably its semantics), what techniques exist to show non-derivability?

The proof systems of interest could include operational semantics of programming languages, Hoare logics, type systems, a non-classical logic, or inference rules for what-have-you.

IME, the following list is easiest to hardest (of course, it's also least to most powerful):

If your system is sound, and you can prove $\lnot \phi$, then you have a nonderivability result, of course.
If you have a lattice-theoretic semantics for your logic, relative to which all your proof rules are valid, then if the meaning of a proposition is not the topmost element of the lattice, then it is not a derivable proposition.
If you know that your logic is complete with respect to a class of models, check to see if there is a particular model in that class which invalidates $\phi$.
Sometimes you can get away with a translation into another logic, and show that derivability over here implies a known nonderivability result over there.
If you have a natural deduction or sequent calculus, check to see if there is a cut-elimination result known, or if you can prove one. If there is, then you can often exploit the subformula property to give simple inductive arguments about nonderivability. (Eg., consistency via cut-elimination is just the statement that there are no cut-free proofs of false, and so if all cuts can be eliminated then there are no inconsistencies.)
If nothing else works, then you can often show consistency/nonderivability results via a logical relations argument. This is the big gun, which works when nothing else does -- in set-theoretic terms, it boils down to a use of the axiom of Replacement, which lets you show huge sets are well-ordered. (This is why you can use it to prove things like normalization of System F.)


Differences between Quantum Computing and Parallelism What are the differences between Quantum Computing and Parallelism?

thanks in advance

The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number generation) and parallelism.

In randomized computation, depending on the outcome of the coin-flips, you explore one out of many possible computational possibilities. If the vast majority of those paths give quickly rise to a particular answer, then that is the answer. In quantum computation, one is tempted to consider these different computational possibilities as being more "real" than in randomized computation, for the reason that we can cause them to cancel each other out — which seems a little as though the different computational possibilities are distinct processes which communicate with one another to collaboratively give an answer. However, while these different computational paths do interfere, they do not interact: a partial answer in one cannot be communicated to another, and as with the purely randomized computation, we cannot choose which one we observe — that is chosen at random from among the possibilities whose amplitudes haven't been cancelled out. In the end, the result is (as with randomized computation) taken as a sort of uncontrolled democratic vote between different so-called "computational branches", with only a small chance of an upset due to getting the answer from a small minority of computations which cast the objecting vote.

By contrast, in a truly parallel computation, each parallel process is obviously and independently present for querying and inspection. The decomposition of the computation as being performed by a collection of communicating agents, or 'processes', is a much more meaningful description. Whether a particular part of the computation 'belongs' to a particular process is something which we might impose by fiat, e.g. if we design a piece of hardware or software which is given responsibility (by us) for performing that computation, but at least there we may consider the activity of an individual agent and in principle design a protocol so that it determines the final output of the computation. This is simply not what happens in the mathematical model of quantum computation.

In the end, one must remember that the (very rough) intuition that quantum computing involves any parallelism at all, is just part of a struggle to obtain robust insights into how quantum computation differs from classical computation. From a point of view of interpretations of quantum mechanics, it corresponds to the Many Worlds Interpretation: but it is dubious to say that any 'world' which is to be cancelled out by destructive interference 'exists' independently, as such. Especially in the case where we may have a large amount of destructive interference and tight control over something like time-reversible operations, the choice of how we decompose the state of the computation into multiple "classical looking" branches is likely to be a description that we impose on the system to understand it, not one that necessarily refers to the physics or the nature of the computation in itself. This is especially true if you consider the various transformations that we can apply on a single qubit: sure, we can describe them as variations on performing a bit-flip or not performing a bit-flip, but what is the meaning of the differences between these quantum-superpositions-of-performing-a-bit-flip-or-not?

Thus, the difference between quantum computation and parallelized computation is that the so-called 'parallel' processes in quantum computation are much more like the imaginary parallel processes of a randomized computation: they cannot be addressed directly, but only in statistical bulk.