Maximum subarray problem with weights The maximum sum subarray problem involves finding a contiguous subarray with the largest sum, within a given one-dimensional array $A[1...n]$ of numbers. Formally, the task is to find indices i and j with $1<=i<=j<=n$ s.t. the sum $\sum_{x=i}^j A[x]$ is as large as possible.
It is well-known that this problem can be solved in linear time $O(n)$.
I'm trying to solve a variation of this particular problem. In addition to array $A[1...n]$ we are also given an array $W[1...n]$ where $W[i]$ gives the weight of the ith item. The items are ordered in increasing weight, so $W[i] \leq W[j]$ if $i<j$. Moreover, all values in $W$ and $A$ are larger than 0, and $A[i] \geq W[i]$ for all $i=1...n$. Objective: find a contiguous subarray that maximizes $\sum_{x=i}^j (A[x]-W[j])$.
Here's a numerical example
i  W  A
1  6  14
2  7  12
3  8  10
4  9  10
5  12 18
6  13 16
7  14 25
8  18 22
9  19 26
10 20 23

The solution to the above example would be: i=5, j=7, with a score of: $A[5]-W[7]+A[6]-W[7]+A[7]-W[7]=18-14+16-14+25-14=17$
To solve this problem, I came up with the following $O(n²)$ algorithm:
best_score= -1
best_i = best_j = -1

for j=n..1:
  score=0
  for i=j..1:
    score=score + A[i]-W[j];

    if score > best_score:
      best_score=score
      best_i = i;
      best_j = j;
    if score < 0:
      continue; //skip inner loop and continue with outer loop

Can this problem be solved more efficiently than O(n²)? In particular, can you prune part of the search by using the best score you found thus far?

Please check the following proof, and see the final remark with a link to code for an $O(n)$-time algorithm.
Theorem 1. There is an $O(n\log n)$-time algorithm for the problem.
Proof.
Fix an instance $(n, A, W)$ of the problem. Define index set $I = \{(i, j) : 1\le i\le j \le n\}$. The goal is to compute $\max_{(i,j)\in I} M_{ij}$, where
$$\textstyle M_{ij} = \Big(\sum_{h=i}^j A[h]\Big) - (j-i+1) W[j].$$
Observe that $M_{ij}$ has the (upper-triangular) inverse Monge property (see e.g. this survey on Monge matrices):
Lemma 1. For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i<k$ and $j < \ell$, $$M_{i\ell} - M_{ij} \le M_{k\ell} - M_{kj}.$$
Proof of Lemma 1.  By calculation,
$$M_{i\ell} - M_{ij} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-i+1) W[j] - (\ell-i+1) W[\ell],$$
while
$$M_{k\ell} - M_{kj} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-k+1) W[j] - (\ell-k+1) W[\ell],$$
so
$$(M_{i\ell} - M_{ij}) - (M_{k\ell} - M_{kj}) =
(k-i) W[j] - (k - i) W[\ell] = (k-i)(W[j] - W[\ell]),$$
which is non-positive as $k > i$, and $j<\ell$ so $W[j] \le W[\ell]$.  This proves Lemma 1. $~~~\Box$
It is well-known (e.g. Section 3.7 of this survey) that the Monge property is sufficient to obtain a simple $O(n\log n)$-time algorithm, and it is easy to adapt that algorithm to the upper-triangular case.  For completeness I'll sketch the algorithm here.
Lemma 1 implies that $M$ is (upper-triangular) totally (inverse) monotone:
Corollary 1. For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i<k$ and $j < \ell$, if $M_{ij} \le M_{i\ell}$ then $M_{kj} \le M_{kl}$.
For $1\le i \le n$, define $J(i) = \arg\max_{j} M_{ij}$ to be the column index of the maximum entry in row $i$.  Corollary 1 implies the following additional corollary:
Corollary 2. $J(1) \le J(2) \le \cdots \le J(n)$
The algorithm computes $J(i)$ for the middle row $i=\lfloor n/2 \rfloor$ in $O(n)$ time (having precomputed all partial sums of $A$ in $O(n)$ time, so that the value of any given $M_{ij}$ can be computed in constant time), then subdivides $M$ into four quadrants around the point $(i, J(i))$, recurses on the upper-left and lower-right quadrants, and takes either $(i, J(i))$ or one of the two points returned recursively, whatever is best.
(Note that the algorithm does not explicitly construct all of $M$.  In fact, it examines $O(n\log n)$ entries of $M$.)
By Corollary 2, the maximum cannot be in the upper-right or lower-left quadrant, so the algorithm is correct.
Letting $T(n, m)$ denote the worst-case runtime on an $n\times m$ index set, we have $$T(n, m) \le m + \max_{1\le j\le m} ~T(\lfloor n/2 \rfloor -1, j) + T(n - \lfloor n/2\rfloor, m-j+1)$$
and $T(1, m) \le m$.  For any execution of the algorithm, the recursion tree has $O(\log n)$ levels. Within a given level, letting $(n_j, m_j)$ denote the dimensions of the $j$th subproblem on that level, we have $\sum_j m_j = O(m)$, from which it follows that the total work for all subproblems on that level (outside of their recursive calls) is $O(m)$, so that $T(n, m) = O(m\log n)$. (This can also be easily verified by induction.) So the run-time of the top-level call is $T(n, n) = O(n\log n)$. $~~~\Box$
Remarks. The total monotonicity of $M$ (Corollary 1 above) probably also implies an $O(n)$-time algorithm via the SMAWK algorithm. (It would if $M$ was totally (inverse) monotone, instead of just "upper-triangular" totally inverse monotone.)  I don't know whether SMAWK applies in this case, but I'd guess so. EDIT: See comment below.
Note that the above proof requires neither the assumption $A[i] \ge W[i]$, nor the non-negativity of the $A[i]$'s and $W[i]$'s.
EDIT: It seems to me that we can extend $M$ to make it totally inverse Monge simply by taking $M_{ij}$ to be, say, $-n W[n]$, for $1\le j < i \le n$.  Then we no longer require the "upper triangular" assumption: the property in Corollary 2 holds for all pairs $(i, j)$ and $(k, \ell)$ with $(1,1) \le (i, j) < (k, \ell) \le (n, n)$.  That is, $M$ extended in this way is totally (inverse) monotone. So the SMAWK algorithm can be applied to this $M$ to solve the problem in $O(n)$ time.
A quick google search gives this Python implementation of the SMAWK algorithm by David Eppstein.  I adapted his code to solve your problem; here is my adaptation.


Complexity of applying a permutation in-place To my surprise, I was not able to find papers about this - probably searched the wrong keywords.

So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.

How do we reorder the array according to $f$ with memory and runtime as close to $O(1)$ and $O(n)$ as possible?

Are there any additional conditions when this task becomes easier? E.g. when we explicitly know a function $g$ is the inverse of $f$?

I know of an algorithm that follows cycles and traverses a cycle for each index to check if it's the least in its cycle, but again, it has worst-case $O(n^2)$ run time, though on average it seems to behave better...

Option 0: Permuting In Place (1995) by Faith E. Fich , J. Ian Munro , Patricio V. Poblete $O(n \log n)$ time $O( \log^{2} n )$ space.

Option 1: Cheat by compressing your permutation to a succinct data structure, see Munro  http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Option 2:  Use a prime cycle decomposition to store the perm succinctly and use that extra space to cheat http://oeis.org/A186202

Option 3: Keep track of the largest index of each cycle manipulated. For each iteration use the largest unseen index to move everything in its cycle by one. If it hits a seen index undo all that work because the cycle has already been manipulated. $O(n^2)$ time, $O(\#\text{cycles} * \log n)$ space.

Option 4: Keep track of the largest index of each cycle manipulated, but only do them in batches of distinct cycle lengths. For each iteration use the largest unseen index to move everything in it's cycle by one. If it hits a seen index undo all that work because thae cycle has already been manipulated. $O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$ time, $O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$ space.

Option 5: From same paper by Munro as Option 0, For $i = 1 .. n$ rotate the cycle of $p(i)$ if $i$ is the largest index in that cycle. $O(n^2)$ time and $O(\log  n)$ space.


Is sorting pairwise distances as hard as sorting arbitrary points? If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances?

Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as sorting $n^2$ arbitrarily chosen numbers?

As a concrete sub question, is the complexity $\Theta(n^2\log{n})$ in the comparison model?

This is an open question even for one-dimensional point sets.  In this setting, the distance-sorting problem is equivalent to sorting X+Y, where $X$ is the input set and $Y=-X$.


A bounded-independence variant of the Berry-Esseen theorem I came across a presentation by Ryan O'Donnell regarding invariance principles. After proving the Berry-Esseen theorem, there is a slide that discusses extensions of the theorem and one that is mentioned there is a so-called "derandomized version'':

  If $X_{1},\ldots,X_{m}$ $C$-nice (that is, has bounded third moment), 3-wise independent., then $X_{1}+\ldots+X_{m}$ is $O(C)$-nice.

I am not sure whether the above is a statement regarding the third moment of the sum of 3-wise independent random variables, or there is indeed some variant of the Berry-Esseen theorem in the case of bounded independence.

Inspecting the proof, I see how 3-wise comes into play, however I could not find any source that discusses bounded-independence variants of this theorem. Are there any?

There are variants of Berry-Esseen for bounded independence, although I have not seen one which is as general as the original theorem. For example Theorem 5.1. in Diakonikolas, Kane, Nelson implies a Berry-Esseen theorem for weighted sums of Bernoulli random variables with bounded independence, as long as none of the weights is too large. If you want error $\varepsilon$ (i.e. Kolmogorov distance from the Gaussian distribution), then $\Theta(1/\varepsilon^2)$-wise independence is necessary and sufficient.


Polynomial time construction of families of pairwise nonhomomorphic graphs Is it true that for all $n$
there are $n$ pairwise nonhomomorphic graphs with $poly(n)$ vertices?

Is there a polynomial time algorithm for constructing such families of graphs?

Take cycles $C_{p_1}, \ldots, C_{p_n}$ where $p_i$ is the $i$th prime number.

We can find the first $n$ prime number in time polynomial in $n$.


$NP$-complete problem with quasi-polynomial bound on the number of solutions FewP is the class of $NP$-problems with polynomial bound on the number of solutions (in the input size). There is no known $NP$-complete problem in $fewP$. I am interested in how far we can stretch this observation.

  Is there any natural $NP$-complete problem with quasi-polynomial upper bound on the number of solutions (witnesses)? Is there a widely accepted conjecture that would rule out such possibility?

Natural means that the problem is not an artificially made up problem to answer the question (or similar ones) and people are interested in the problem independently (as defined by Kaveh).

EDIT: The bounty will be awarded to such natural $NP$-complete problem or a reasonable argument ruling out the existence of such problems (using widely accepted complexity-theoretic conjectures).

Motivation: My intuition is that $NP$-completeness imposes super-polynomial (or even exponential) lower bound on the number of witnesses.

This is a very interesting question.

First, a clarifying remark. Note that "upper bound on the number of witnesses" is not a property of a computational problem per se, but of a particular verifier used to decide an $NP$ problem, just as an "upper bound on number of states" would not be a property of a problem but of a Turing machine deciding it. So saying "$NP$ problem with upper bound on number of solutions" isn't quite accurate, and if $P = NP$ then every $NP$ problem has a verifier with any number of desired solutions (including zero, and including all possible strings).

So we have to make a definition, to address your question. For $s : {\mathbb N} \rightarrow {\mathbb N}$, let's say an $NP$ problem $L$ "has at most $s(n)$ solutions" if for some constant $c$ there is an $O(n^c)$ time verifier $V$ such that, for every input length $n$ and for every $x \in L$ of length $n$, there are distinct $y_1,\ldots,y_{s(n)}$ of length $n^c$ such that $V(x,y_i)$ accepts for all $i$, and $V(x,y)$ rejects all other $y$ of length $n^c$.

All I think I can say at the moment is this:

Every $NP$-complete problem I know (defined by some natural verifier) has an obvious corresponding $\#P$-complete counting version (with the same verifier).
For any $NP$-complete problem defined with a verifier having at most $poly(n)$ solutions (or even $2^{n^{o(1)}}$ solutions) the corresponding counting version probably isn't $\#P$-complete.

More details: Suppose $L$ is $NP$-complete, with a verifier $V$ that has at most $O(n^c)$ solutions. Then the natural counting "decision" version of $L$, which we define as

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

is computable in $FP^{NP[O(\log n)]}$, that is, a polytime function with $O(\log n)$ queries to $NP$. That is because deciding whether the number of solutions to $x$ is at most $k$ is in $NP$: the witness, if it exists, is simply the number of $y_i$'s making $V$ accept, which we know to be at most $O(n^c)$. Then we can binary search using this $NP$ problem to compute the exact number of solutions to $L$.

Therefore, an $NP$-complete problem of this kind could not be extended to a $\#P$-complete problem in the usual way, unless $\#P \subseteq FP^{NP[O(\log n)]}$. This looks unlikely; the whole polynomial time hierarchy would basically collapse to $P^{NP[O(\log n)]}$.

If you assume $s(n) = 2^{n^{o(1)}}$ in the above, you would still get an unlikely consequence. You would show that $\#P$ can be computed in $2^{n^{o(1)}}$ time with an $NP$ oracle. That's more than enough to prove, for instance, that $EXP^{NP} \neq PP$ and subsequently $EXP^{NP} \not\subset P/poly$. Not that those separations are unlikely, but it seems unlikely they'd be proved by giving a subexp time $NP$-oracle algorithm for the Permanent.

By the way, I have said nothing too insightful here. There is almost certainly an argument like this in the literature.


On a Linearization of the Quadratic Assignment Problem The Quadratic Assignment Problem formulated as an integer program:
\begin{align}
 \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n c_{ijkl}x_{ij}x_{kl}\\
 \mbox{subject to}\quad &\sum_{i=1}^n x_{ij} = 1 \quad \forall j=1,\ldots,n,\\
&\sum_{j=1}^n x_{ij} = 1 \quad \forall i=1,\ldots,n,\\
 &x_{ij}\in\{0,1\}\quad \forall i,j=1,\ldots,n.
 \end{align}

A simple and natural linearization:
\begin{align}
 \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n c_{ijkl}y_{ijkl}\\
 \mbox{subject to}\quad &\sum_{i=1}^n x_{ij} = 1 \quad \forall j=1,\ldots,n,\\
&\sum_{j=1}^n x_{ij} = 1 \quad \forall i=1,\ldots,n,\\
& y_{ijkl} \le x_{ij} \quad \forall i,j,k,l=1,\ldots,n,\\
& x_{ij} + x_{kl} \le 1+y_{ijkl} \quad \forall i,j,k,l=1,\ldots,n,\\
& y_{ijkl} = y_{klij} \quad \forall i,j,k,l=1,\ldots,n,\\
&x_{ij},y_{ijkl}\in\{0,1\}\quad \forall i,j,k,l=1,\ldots,n.
 \end{align}

My question is: Has this linearization already been considered in the literature?
I did not see it in any papers (this one for example).

I don't recall having seen this encoding anywhere in the literature. It would not be surprising if indeed no such academic literature exists, though.

First of all note that your trick to translate a binary quadratic programming problem to an integer programming one is pretty straight-forward. You can find a casual mentioning it on the web from 2005 here.

But there is more to it. Solving the Quadratic Assignment Problem is known to be NP-complete already, and you reduce it to an NP-hard problem. So in theory, you don't gain anything.

In practice, however, you might. But unless you have evidence that the ILP instances that you get are particularly easy to solve for modern solvers, I wouldn't use your encoding, and here is why: the efficiency from ILP solvers comes from the fact that they can use the convexity of the solution space to their advantage. This allows to perform a branch-and-bound search on the feasible solutions while using an LP solver to find not-quite-yet-valid candidate approximate solutions. But in your encoding, all values are binary! So the ILP solver can't really take advantage of it.

If we now have a look at state-of-the-art other methods to solve the problem, there seem to be both exact and heuristic methods (I found this page by following links from Wikipedia). One of the methods is reported to work well for problems with $n \leq 15$. For such instances, your encoding requires $15 \cdot 15$ variables of the type $x_{ij}$, and $15^4$ variables of the type $y_{ijkl}$. Even though we can reduce this number of variables by a factor of $16$ (I think), that is an awful lot of variables for an ILP problem where the ILP solver cannot really take advantage of the structure of the problem. So it is possible that the approach that you mention has been invented before but did not make it into any publication as it does not perform well.


Boolean circuits which correspond to L/poly Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$.
Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\mathrm{poly}$?

Intuitively, bounded space Turing machines seem to correspond to bounded width Boolean circuits, but I can't find a reference.
Is there a reason that branching programs are used for $\mathsf{L}/\mathrm{poly}$ and Boolean circuits are not used?

[Addition after Sam McGuire's answer (in comments)]

Actually, I'm most interested in Boolean circuits corresponding to $\mathsf{L}/\mathrm{quasipoly}$.
I guess that it is quasipolynomial-size $O(\log n)$-width Boolean circuits.

I would like to know that, whether it is right or not, whether I should prove it myself or not, whether it is known and there's a reference or not.

$\mathsf{L}/\mathrm{poly}$ can be characterized by polynomial size skew circuits. A boolean circuit is called skew if every AND-gate has at most one child that is not an input gate. Skew circuits and branching programs can simulate each other with polynomial blow-up, so polynomial size skew circuits and branching programs compute the same class of functions, which is $\mathsf{L}/\mathrm{poly}$.

A proof of these simulations can e.g. be found in this paper by Balaji, Krebs and Limaye.


Succinct Representation and Communication complexity Succinct representation is often used to define NEXP or EXP complete problems. For example, when a graph is given as a circuit to compute the existence of edge between vertex $i,j$ for indices of $i,j$ is assigned in the input wires, the hardness of P-complete  , NP-complete problems is amplified to EXP complete and NEXP-complete problems respectively .

My question is about relationship between communication complexity  and succinct representation.

For example, can Alice and Bob that have $A,B \subseteq \{1,...,n\}$ compute the disjointedness function with $O(\log n)$ bits to construct the following protocol ?
 However, disjointedness has a lower bound  $\Omega (n)$. The answer of this question must be $NO$. Why ?

Protocol:

1.Alice make a succinct representation of her input $A$ : this circuit output  $1$ iff $i\in A$ for given index of $i \in \{1,...,n\}$.

2.Bob gets $A$ from the succinct circuit by executing brute force evaluation of all assignments, and check whether $A \cap B =\emptyset$

Thank you for Igor's answer.Additional questions are:

What are examples of $nice$ $structures$ you mention ?(Why arbitrary undirected graphs,  boolean circuits, or formulae have $nice$ $structures$ in the sence of your answer ? Why  messages Alice sent do not have ? If $A,B\subseteq \{1,...,{n \choose 2}\}$ then can we consider their inputs as undirected graphs ?)

The circuit computed by Alice gets $\log(n)$ bits representing $i \in [n]$, and outputs $1$ iff $i \in A$. Note that if $A$ does not have a particularly nice structure, the size of this circuit will be exponential in the length of the input, that is $2^{\log(n)}$.


Global properties of hereditary classes? A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal.

Classes of graphs that exclude a minor have nice properties that do not depend on the specific excluded minor.  Martin Grohe showed that for graph classes excluding a minor there is a polynomial algorithm for isomorphism, and fixed-point logic with counting captures polynomial time for these graph classes.  (Grohe,   Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors, LICS, 2010.)  These can be thought of as "global" properties.

  Are there similar "global" properties known for hereditary classes (either graphs or more general structures)?

It would be good to see each answer focus on just one specific property.

Hereditary properties are very "robust" in the following sense.

Noga Alon and Asaf Shapira showed that for any hereditary property ${\cal P}$, if a graph $G$ needs more than $\epsilon n^2$ edges to be added or removed in order to satisfy ${\cal P}$, then there is a subgraph in $G$, of size at most $f_{\cal P}(\epsilon)$, which does not satisfy ${\cal P}$.  Here, the function $f$ only depends on the property ${\cal P}$ (and not on the size of the graph $G$, for instance).  Erdős had made such a conjecture only about the property of $k$-colorability.

Indeed, Alon and Shapira prove the following stronger fact: given ${\cal P}$, for any $\epsilon$ in $(0,1)$, there are $N(\epsilon)$, $h(\epsilon)$ and $\delta(\epsilon)$ such that if a graph $G$ has at least $N$ vertices and needs at least $\epsilon n^2$ edges added/removed in order to satisfy ${\cal P}$, then for at least $\delta$ fraction of induced subgraphs on $h$ vertices, the induced subgraph violates ${\cal P}$.  Thus, if $\epsilon$ and the property ${\cal P}$ are fixed, in order to test if an input graph satisfies ${\cal P}$ or is $\epsilon$-far from satisfying ${\cal P}$, then one only needs to query the edges of a random induced subgraph of constant size from the graph and check if it satisfies the property or not.  Such a tester would always accept graphs satisfying ${\cal P}$ and would reject graphs $\epsilon$-far from satisfying it with constant probability.  Furthermore, any property that is one-sided testable in this sense is a hereditary property!  See the paper by Alon and Shapira for details.


Follow-the-leader algorithm in swarm formation: literature on the subject? In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum decision without general knowledge of the map).

I'm trying to get a more rigorous understanding of any background literature on similar algorithms. Surely this is not an original idea, but I don't even know what terms to start googling for.

Here is diagram of the functioning of the algorithm.

Every circle is a soldier, with the center number representing a uniquely assigned soldier_id. Soliders have finite vision range but know the global position of the "X".

When prompted to form a swarm, soldiers start looking for the soldier within its vision range that had the smallest soldier_id and follows it. If it is itself the lowest soldier_id in range, it starts going in direction of the X. This leads to an organic formation of all the soldiers, with the soldier with the lowest soldier_id at the helm.

As I said, I'm trying to get a sense of general literature on similar algorithms and I don't have nearly enough experience general knowledge of computer science to know where to start. Perhaps there are similar ideas in place in bee or ant colonies or other biological systems. Perhaps even in cell formation?

I'm not even sure this is the appropriate place to ask this question. If it isn't, any pointers would be appreciated.

Bernard Chazelle has done some work on the convergence of bird flocking, and he's considered models such as follow-the-leader and variants.


Problems outside of P that are not P-hard While reading an answer by Peter Shor and an earlier question by Adam Crume I realized that I have some misconceptions about what it means to be $\mathsf{P}$-hard.

A problem is $\mathsf{P}$-hard if any problem in $\mathsf{P}$ is reducible to it with $\mathsf{L}$ (or if you prefer $\mathsf{NC}$) reductions. A problem is outside of $\mathsf{P}$ if there does not exist a polynomial time algorithm to solve it. This means that there should be problem that are outside $\mathsf{P}$ but are not $\mathsf{P}$-hard. If we asume that FACTORING is outside of $\mathsf{P}$, then Peter Shor's answer suggests that FACTORING could be such a problem.

Are there any known problems (natural or artificial) that are known to lay outside $\mathsf{P}$ but not be $\mathsf{P}$-hard? What about under assumptions weaker than the factoring assumption? Is there a name for this complexity class?

I think you can construct a set not in $P$ that is not $P$-hard by a Ladner-style argument. Here's a specific example.

In his paper "A Uniform Approach to Obtain Diagonal Sets in Complexity Classes" (Theor. Comp. Sci. 18, 1982), Schöning proves the following:

  Theorem Suppose $A_1 \notin C_1$, $A_2 \notin C_2$, $C_1$ and $C_2$ are recursively presentable complexity classes and are closed under finite variations. Then there's a set $A$ such that $A \notin C_1$, $A \notin C_2$, and if $A_1 \in P$ and $A_2$ is not trivial (empty set or all strings) then $A$ is polytime many-one reducible to $A_2$.

To apply this, set $A_1$ to be the empty set, and $A_2$ to be $EXP$-complete under polytime reductions, set $C_1$ be the set of $P$-hard sets that are in $EXP$, set $C_2 = P$. The empty set cannot be $P$-hard (the definition of $P$-hardness for a language requires that there is at least one instance in the language and one instance not in). $A_2$ is definitely not in $C_2$. The $C_1$ and $C_2$ can be verified to meet the above conditions (similar to how Schoening does it for the $NP$-complete sets; see also this related question). So we get an $A$ that is not a $P$-hard problem in $EXP$, and that $A$ is not in $P$. But because $A_1 \in P$ and $A_2$ is nontrivial, $A$ is many-one reducible to an $EXP$-complete set, so it is in $EXP$. Therefore, in particular, $A$ cannot be $P$-hard either.

In the above argument, the restriction to $P$-hard problems in $EXP$ is necessary to ensure recursive presentability, since the P-hard problems as a whole are not recursively presentable and not even countable.
Now, "natural" examples of this are a different story...


Monotone circuit complexity of computing functions on sparse inputs The weight $|x|$ of a binary string $x\in\{0,1\}^n$ is the number of ones in the string. What happens if we are interested in computing a monotone function on inputs with few ones?

We know that deciding if a graph has a $k$-clique is hard for monotone circuits (see among others Alon Boppana, 1987), but if a graph has for example at most $k^3$ edges it possible to find a monotone bounded depth circuit of size $f(k)\cdot n^{O(1)}$  which decides $k$-clique.

My question: is there any function which is hard to compute by a monotone circuit even on inputs of weight less than $k$? Here hard means circuit size  $n^{{k}^{\Omega(1)}}$.

Even better: is there an explicit monotone function which is hard to compute even if we only care about inputs of weight $k_1$ and $k_2$?

Emil Jeřábek already observed that known lower bounds hold  for monotone circuits that separate two classes of inputs ($a$-cliques vs maximal $(a-1)$-colorable graphs), thus at cost of some independence in the probabilistic argument it is possible to make it work for two classes of input of fixed weight.  This would cause $k_2$ to be a function of $n$ which I want to avoid.

What is would really like is an explicit hard function for $k_1$ and $k_2$ much smaller than $n$ (as in the parameterized complexity framework).  Even better if $k_1=k_2+1$.

Notice that a positive answer for $k_1=k_2$ would imply an exponential lower bound for arbitrary circuits.

Update: This question may be partially relevant.

specifically considering one part of the question (eg for $k_1$=1,$k_2$=2), Lokam studied "2-slice" functions in this paper & proves that strong lower bounds on them can be generalized, therefore this is a very hard open problem related to basic complexity class separation & any such construction/explicit function would be a breakthrough; from the abstract:

  A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1’s and evaluates to one on inputs with more than two 1’s. On inputs with exactly two 1’s f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of 2-slice functions would imply superpolynomial lower bounds over a complete basis for certain functions derived from them.

Graph Complexity and Slice Functions / Satyanarayana V. Lokam,
Theory Comput. Systems 36, 71–88 (2003)

also as in his comments SJ covers this similar case in his book in the section  exploring star complexity of graphs sec1.7.2.

Boolean function complexity: advances and frontiers, Stasys Jukna


Simple candidates for pseudorandom permutations? Even though it is not known whether one-way functions exist, there are several candidate functions used in practice for cryptographic applications that are efficiently computable but are conjectured to be hard to invert (such as modular exponentiation, the Rabin function etc.) Moreover, many of these functions are relatively simple to compute in some sense.

Are there any simple candidates for strongly pseudorandom permutations? By a simple candidate, I mean one with small circuit complexity (or maybe small complexity under some different complexity measure). For example, are there any candidates for PRPs that can be computed by $NC^1$ circuits? (I am looking for PRPs which work with arbitrarily long inputs, as opposed to block ciphers operating on fixed-length strings.)

Yes.  The following paper presents a candidate for a PRF that is implementable in $NC^1$, whose security is based on a lattice assumption (hardness of LWE):

Abhishek Banerjee, Chris Peikert, Alon Rosen.  Pseudorandom Functions and Lattices.  EUROCRYPT 2012.

It also has some discussion of related literature that might be helpful.

Also, here are two trivial observations.

First, there is a PRP that can be computed in $NC^1$ if and only if there is a PRF that can be computed in $NC^1$.  The "only if" part is immediate, as any PRP with large domain is also a PRF.  The "if" part follows from the Luby-Rackoff construction (i.e., the Feistel cipher), as that shows how to build a PRP out of any PRF; it increases the depth by only a constant factor.

Second, the following paper shows that no PRF can be computed by an AC0 circuit.

Nathan Linial, Yishay Mansour, Noam Nisan.  Constant depth circuits, Fourier transform, and learnability.  Journal of the ACM, 40(3):607--620, 1993.

It follows that no PRP can be computed by an $AC^0$ circuit.


Process modeling with fine-grained notions of location Is anyone aware of any process algebraic (or related) formalisms that capture fine-grained location information?  I'm familiar with ambients and bigraphs, which obviously have a location model, but what about attempts to model more concrete location information, such that the location of some agent is expressed within some (real or virtual) coordinate space?

It seems to me that it would be possible to take some existing formalism and enrich it with constructs to model location at some appropriate level of abstraction, but I would hate to reinvent the wheel needlessly if this is reminiscent of previous efforts.

As background, the application domain is essentially biological modeling where the traditional notions of location used in this domain to govern where interactions can occur are not fine-grained enough to capture the properties of interest.

Processes in Space by Luca Cardelli and Philippa Gardner is one paper in this direction. It specified a process algebra for describing the evolution of 3D structures.


Existence of $opt^c$-approximation of Dominating Set with $c < 1$? Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. it's possible to find in polynomial-time a solution $S$ such that $|S| \leq (1 + \log n) opt$, where $opt$ is the size of a minimum dominating set. There are bounds showing that we cannot improve the dependency on $\log n$ much http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf.

My question: is there an approximation algorithm which has a guarantee in terms of $opt$ instead of $n$? In graphs where $n$ is very large with respect to the optimum, a factor-$\log n$ approximation would be much worse than a factor $\log opt$ approximation. Is something like that known, or are there reasons why this cannot exist? I am happy with any polynomial-time algorithm which produces a solution $S$ such that $|S| \in O(opt^c)$ for some constant $c$.

I think it is still open if Dominating Set or Hitting Set have a f(OPT) approximation for some (nontrivial) function f. This is should be a very difficult (and possible deep) question to answer. I consider it the most exciting question in parameterized approximation (along with the analogous question for Clique). You might want to have a look at my survey [1] that discusses this. Note that it is shown in the more recent paper [2] that "monotone circuit satisfiability for weft-2 circuits", a problem which is more general than Dominating Set, does not have f(OPT) approximation for any f.

[1] D. Marx. Parameterized complexity and approximation algorithms.
The Computer Journal, 51(1):60-78, 2008.

[2] D. Marx. Completely inapproximable monotone and antimonotone parameterized problems.
In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, Cambridge, Massachusetts, 181-187, 2010.


Can strong NP-hardness really be shown using plain polytime reductions? I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I would have thought that you’d have to show that any numbers used in the reduction and the instances of the problem you’re reducing to were polynomially bounded in the problem size.

I then saw that Wikipedia gave the same general instructions for this sort of proof, but I wasn’t really convinced until I saw Garey & Johnson say basically the same thing. To be specific, they say, “If $\Pi$ is NP-hard in the strong sense and there exists a pseudo-polynomial transformation from $\Pi$ to $\Pi'$, then $\Pi'$ is NP-hard in the strong sense,” and “Note that, by definition, a polynomial time algorithm is also a pseudo-polynomial time algorithm."

Of course, I take the word of Garey & Johnson on this—I just don’t understand how it can be correct, which is what I’d like some help with. Here’s my (presumably flawed) reasoning…

There are strongly NP-complete problems, and all these are (by definition) strongly NP-hard as well as NP-complete. Every NP-complete problem can (by definition) be reduced to any other in polynomial (and therefore pseudopolynomial) time. Given the statements of Garey & Johnson, it would therefore seem to me that every NP-complete problem is strongly NP-complete, and, therefore, that every NP-hard problem is strongly NP-hard. This, of course, makes the concept of strong NP-hardness meaningless … so what am I missing?

Edit/update (based on Tsuyoshi Ito’s answer):

The requirement (d) from Garey & Johnson’s definition of a (pseudo)polynomial transformation (the kind of reduction needed to confer NP-hardness in the strong sense) is that the largest numerical magnitude in the resulting instance be polynomially bounded, as a function of the problem size and maximal numerical magnitude of the original. This, of course, means that if the original problem is NP-hard in the strong sense (that is, even when its numerical magnitudes are polynomially bounded in the problem size), this will also be true of the problem you reduce to. This would not necessarily be the case for an ordinary polytime reduction (that is, one without this extra requirement).

According to the terminology in the paper by Garey and Johnson, polynomial-time transformations are not necessarily pseudo-polynomial transformations because it may violate item (d) in Definition 4.


Counting the Number of Simple Paths in Undirected Graph How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths.

Recall that a simple path is a path with no cycles, so I'm talking about counting the number of paths with no cycle.

There are several algorithms that count the simple paths of length $k$ in $f(k)n^{k/2+O(1)}$ time, which is a whole lot better than brute force ($O(n^k)$ time). See e.g. Vassilevska and Williams, 2009.


Name of (and solution to) this generalization of linear assignment I would like to know if the following problem is known and has any efficient solution.

Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no row or column is selected more than $b$ times.

This can be re-formulated as the following integer linear program:
\begin{align}
\mbox{maximize} &\sum_{1\le i,j\le n} s_{ij}x_{ij},\\
\mbox{subject to} & \sum_{1\le i,j\le n} x_{ij} = a,\\
& \sum_{1\le i\le n} x_{ij} \le b \quad\forall 1\le j\le n,\\
& \sum_{1\le j\le n} x_{ij} \le b \quad\forall 1\le i\le n,\\
& x_{ij}\in\{0,1\}\quad\forall 1\le i,j\le n.
\end{align}

Thank you very much in advance for your help!

It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and whose capacity is 1.  Then add an edge of capacity $b$ from the source to each row, with cost 0, and similarly for the columns, and solve the resulting minimum cost flow problem -- which can be done in polynomial time.
Since all edge capacities are integers, stndard algorithms will return an optimal solution that is integral.


Equivalent definitions of time constructibility We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ steps and for each $n$ there exists some input of length $n$ on which $M$ makes exacltly $f(n)$ steps.
We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is fully time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes exactly $f(n)$ steps.

Q1: Does there exist a function which is time-construcible and not fully time-constructible?

The answer is yes (see this answer), if $EXP-TIME \neq NEXP-TIME$. Can the condition for "yes" be strengthened to $P\neq NP$? Can "yes" be proven?

Q2: Does the class of (fully) time-constuctible functions changes if we allow only 2-tape Turing machines in the definition?
Q3: What are the "provable" reasons for believing that all nice functions are fully time-constructible?

The paper
Kojiro Kobayashi: On Proving Time Constructibility of Functions. Theor. Comput. Sci. 35: 215-225 (1985)
partially answers Q3. The partial summary and upgrade of it is in this answer. I take Q3 as answered.
Historically, the notion of real-time countable function was used instead of (fully) time-constructible. See this question for more.

In the last few days I thought a lot about (fully) time-constructible functions and I will present what I found out by answering Q1 and Q3. Q2 seems too hard.

Q3:

Kobayashi in his article (the reference is in the question) proved that a function $f:\mathbb{N}\rightarrow\mathbb{N}$, for which there exists an $\epsilon>0$ s.t. $f(n)\geq (1+\epsilon)n$, is fully time constructible iff it is computable in $O(f(n))$ time. (note that it is irrelevant whether the input or output is in unary/binary since we can transform between these two representations in linear time). This makes the following functions fully time-constructible: $2^n$, $2^{2^n}$, $n!$, $n\lfloor \log n \rfloor$, all polynomials $p$ over $\mathbb{N}$ s.t. $p(n)\geq (1+\epsilon)n$ ... Kobayashi also proved fully time-constructibility for some functions that grow slower than $(1+\epsilon)n$, like $n+\lfloor\lfloor\log n\rfloor^q\rfloor$ for $q\in\mathbb{Q}^+$ ...

To continue with examples of fully time-constructible functions, one can prove that if $f_1$ and $f_2$ are fully time-constructible, then $f_1+f_2$, $f_1f_2$, $f_1^{f_2}$ and $f_1\circ f_2$ are also fully time-constructible (the later follows directly from Theorem 3.1 in Kobayashi). This altogether convince me that many nice functions are indeed fully time-constructible.

It is surprising that Kobayashi did not see a way to prove fully time-constructibility of the (nice) function $\lfloor n\log n\rfloor$ (and neither do I).

Let us also comment the definition from Wikipedia article: A function $f$ is time-constructible, if there exists a Turing machine $M$ which, given a string $1^n$, outputs $f(n)$ in $O(f(n))$ time.  We see that this definition is equivallent to our definition of fully time-constructibility for functions $f(n)\geq (1+\epsilon)n$.

Q1:

This question has a really interesting answer. I claim that if all time-constructible functions are fully time-constructible, then $EXP-TIME=NEXP-TIME$. To prove that, let us take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k-1}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Now define the function
$$f(n)=\left\{\begin{array}{ll}
  8n+2  & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
  8n+1 & \mbox{else}
 \end{array}
\right.$$

I claim that $f$ is time-construcible. Consider the following deterministic Turing machine $T$:

on input $w$ of length $n$ it computes $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ in $O(n)$ time
then it simulates $M$ on these bits, where the bits of $w$ determine which (formerly nondeterminisic) choices to take.
accept iff $\left(M\textrm{ accepts using choices given by }w\right)$.

Note that the length of $w$ ($=n$) is enough that it determines all nondeterministic choices, since $M$ on input $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ makes at most $n$ steps.

We can make  $T$ run in at most $8n+1$ steps. Now the following Turing machine proves that $f$ is time-constructible:

on input $w$ of length $n$ run $T$ and count steps in parallel so that exacly $8n$ steps are done.
if $T$ rejected or would reject in the next step, go to a halting state in the next step. Else, make one more step and then go to a halting state.

Now suppose that $f$ is fully time-constructible. We will prove that this leads to $EXP-TIME=NEXP-TIME$.

The following algorithm solves $L$:

on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.
compute $f(n)$ in time $f(n)$ and check whether it is divisible by 2.

This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$.


#P-Completeness of the Hosoya Index The description from Wikipedia mentions that it is #P-Complete to compute, but there are methods.  What is a layman's explanation to this?

A matching $M$ is called perfect for a graph $G$ when all vertices of a graph are matched in $M$.

Computing the number of perfect matchings is a well-known #P-complete problem and shown to be equivalent to computing the permanent of the biadjacency matrix of the graph. Now note that each perfect matching, by removing edges produces $2^{n}-1$ different matchings (consider each subset of edges, which is a smaller matching, we do not consider the empty set). Also, each perfect matching prohibits exactly $\binom{n}{k}$ matchings of size $k$ from being maximal but non-perfect, since they are subsets of this perfect matching. Given those kinds of restrictions, one can certainly upper bound the number of perfect matchings given the number of matchings and perhaps it is also to use additional information to do a precise calculation.

Perhaps you should take a look at the paper "Two-dimensional monomer-dimer systems are computationally intractable" (reference 5 in the wikipedia article). It seems to rely on the fact that counting matchings (all of them, see the comments) remains #P-complete for planar graphs. Interestingly enough, counting perfect matchings for planar graphs in in $P$, i.e. can be computed in polynomial time (in a deterministic way).


Complexity of two perfect matchings with minimum shared edges? Perfect Matching problem is polynomial time solvable in general graphs.
Given undirected simple graph,

  Is the problem of finding two perfect matching with minimum shared edges between them efficiently solvable?

Shared edge is an edge that occurs in both perfect matchings.

Consider a 3-regular graph $G = (V,E)$.

If there is an edge colouring of $G$ with 3 colours, then you have a partition of $E$ in 3 disjoint perfect matchings. In particular, you can find 2 disjoint perfect matchings.

Conversely, if you can find two disjoint perfect matchings $M_1$ and $M_2$, you can also find a third disjoint perfect matching $M_3 = E \setminus (M_1 \cup M_2)$. The partition $\{M_1, M_2, M_3\}$ of $E$ is an edge colouring of $G$ with 3 colours.

Deciding if a 3-regular graph has an edge colouring with 3 colours is NP-hard (Holyer 1981). Hence it is also NP-hard to decide if there are two disjoint perfect matchings (i.e., to decide if the minimum number of shared edges is 0).


Advice for a mathematician trying to present a paper at a CS conference? I am a mathematician who works primarily in the spectral theory of self-adjoint and unitary operators. Some of my research is of relevance in quantum walks, and I have one paper in particular that I would like to present in the Quantum Information Processing conference this January in Seattle.

The culture of the theoretical CS community seems very different from the math community. I even had to look up what it meant to  "present a paper" at a conference, since we never use that language in math conferences!

I was wondering if I could get some advice on presenting my paper for consideration in this conference. Along with an arXiv link to my paper I am supposed to give them a 1-3 page extended abstract, which I suppose is a way to convince them my paper is relevant for the conference. What is normally expected in such a document?

For instance, to what extent should I talk about the mathematical machinery? Would the organizers care about the (very difficult and technical) details of the proof, or should I just state an algorithm, assert that it works and explain why it is relevant to computer science?

First and foremost, stay on time.

Usually, at conferences you are supposed to talk for a very limited amount of time, e.g. 25 minutes including 5 for questions. In such slot you will not be able to go deep into the technical details.

You should have a more "marketing" approach to presenting a paper. You have to convince the attendants about:

what your main results are
why your results are important
why later on one should spend some time to actually read your paper

Try to be simple and direct. Most attendees will also have spent part of their mental energy on previous presentations. Chances are they will forget about your paper very soon (there are too many to remember for a human mind!). Your goal is to make them to remember something about your paper.

Leave the proofs out. You can briefly mention the proof technique if relevant, though ("by reduction to problem XYZ").
Provide the definitions and statements -- if they are very technical, you can be a bit vague ("under some regularity conditions..."). Clarity trumps precision here. Provide some background for people not in the field, but do not waste time in reviewing basic definitions. Here it is important to know what the audience is familiar with, which depends on the venue. E.g. in a TCS conference, everyone knows what a non-deterministic Turing machine is.

Write and use a few (computer) slides -- you can't waste time writing on a blackboard, and most venues will expect you to have a computer presentation ready. Bring your laptop to the presentation. For a 25 minutes talk, use around 20 slides. Beforehand, make a pretend presentation in your office, and use a timer to check you can do it on time. Optionally, you can take some notes about what to say on each slide, and use these notes during the talk.

Sum up the main points in the last slide to help people remember your talk.

Expect at least a question at the end. Sometimes a question can be not very relevant since the audience may not have grasped everything. Politely answer that anyway.

The goal of the 3-pages short abstract is similar: to convince people that your results are interesting, and that they should read the full version. Try to summarize the main points, trying to convey the general idea even if the space does not allow a proper discussion. Avoid the technical parts which are not needed to assess your results.


Consequences of $SAT \in BQP$ As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far:

Quantum computers are not known to solve NP-complete problems in polynomial time.
"Quantum magic won't be enough" (Bennett et al. 1997): if you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\sqrt{2^n}$ steps to find the correct one (using Grover's algorithm)
If a quantum polynomial time algorithm for a NP-complete problem is ever found, it must exploit the problem structure in some way (otherwise bullett 2 would be contradicted).

I've some (basic) questions that no one seems to have asked so far on this site (maybe because they are basic). Suppose someone finds a bounded error quantum polynomial time algorithm for $SAT$ (or any other NP-complete problem), thus placing $SAT$ in $BQP$, and implying $NP \subseteq BQP$.

  Questions

  Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?
  A result like that would seem to suggest that quantum computers had an inherently superior power than classical computers. Which would be the consequences of a result like that on physics? Would it emanate some light on any open problem in physics? Would physics be changed after a similar result? Would the law of physics as we know them be affected?
  The possibility (or not) to exploit the problem structure in a general enough (i.e. specific-instance independent) manner seems to be the very core of the P = NP question. Now if a bounded error polynomial time quantum algorithm for $SAT$ is found, and it must exploit the problem structure, wouldn't its structure-exploitation-strategy  be usable also in the classical scenario? Is there any evidence indicating that such a structure-exploitation may be possible for quantum computers, while remaining impossible for classical ones?

I'm not going to try to answer the first question, as someone like Scott Aaronson, Peter Shor or John Watrous can no doubt give you a far more comprehensive answer on that front.

As regards question 2, it is important to note that quantum computers are in fact more powerful than classical computers in many instances:

There is a rather generic polynomial speed-up gained by quantum computers over classical computers in quite a number of problems. From a complexity point of view, this is perhaps somewhat less interesting than an exponential speed-up, but is something that we can actually prove.
Quantum communication complexity can often vary dramatically from classical communications complexity for the same problem. Again, this is something that can be proven (see for example the Mermin-GHZ game).
Quantum queries to oracles are very often far more powerful than classical queries to the same oracle (see for example the Deutsch-Josza algorithm).

With this is mind, it is already known that quantum computers are fundamentally more powerful than classical computers. I think I would be correct in saying that the majority of physicists who work on such things would already assume that it is not possible to find a classical algorithm to efficiently simulate every quantum system, and so while a result showing that NP was contained in BQP would certainly be surprising, it would not be particularly likely to provide a breakthrough in the understanding of any particular physical phenomenon. Rather it would provide somewhat stronger evidence that quantum physics is hard to simulate.

There is no fundamental physics that is dependent on the computational complexity of simulating it, so finding an efficient quantum algorithm for an NP-complete problem would not have fundamental consequences for the correctness of our current understanding of how the universe functions (though I am inclined to agree with Scott Aaronson's suggestion that it is interesting to see if you could have physical laws emerge from computational assumptions).

It is extremely tempting to say that this would have consequences for adiabatic evolution of quantum systems (and I guess you might get an answer or two suggesting that), etc., but this would be incorrect, as they are governed by a specific physical process, and so showing that it is in principle possible to solve SAT in polynomial time on a quantum computer, wouldn't say anything about their specific evolution.

As regards your last question, we already have examples where problem structure is exploited to yield a polynomial quantum algorithm, but which do not lead to such a classical algorithm (factoring for example). So, as far as our current understanding goes, a problem with a structure exploitable to yield a polynomial time quantum algorithm does not imply that the structure is exploitable to yield a classical polynomial time algorithm.


Can generalized twenty questions be solved by a greedy algorithm? The game of twenty questions can be generalized in the following way.

Let $\Omega$ be a finite set and $\mathcal Q$ a collection of subsets of $\Omega$, called the questions. A point $x\in\Omega$ is chosen unknown to the player, who then has the ability to iteratively choose a set $Q\in\mathcal Q$ and be told whether or not $x\in Q$. The player's goal is to determine $x$.
In order for the game to be solvable, $\mathcal Q$ is assumed to have the property that every $x\in\Omega$ can be realized as the intersection of some collection of elements of $\mathcal Q$ or their complements.

What we want is a strategy to solve this game with optimal worst-case running time.
At any point in the game, we can assign to each question a pair of integers - the number of possibilities that will remain depending on whether the answer is yes or no. Assign to each question a score which is the larger of these two integers, and always pick the question with minimal score. This is the "greedy" strategy.
Does the greedy strategy always have optimal worst-case running time?

No. There's a huge literature on the topic, called combinatorial search theory, you can read more about these types of questions there.
The simplest example that I could think of is the following.

Suppose that you want to find an edge of a graph, and you can ask whether a given vertex is incident to the hidden edge, or not.
Now take the following bipartite graph.
It contains a perfect matching on $100+100$ vertices.
Moreover, it also contains $10$ degree $10$ vertices that are connected to $10$ different vertices each, all on the same side.
So one side of the graph has $100$ vertices, all degree $2$, the other $110$, of which $100$ have degree $1$, the other $10$ degree $10$.

In this case, the greedy algorithm would first query the degree $10$ vertices, and then the rest, taking about $110$ steps.
If instead it started with querying the $100$ vertices of degree $2$, it would be done in $101$ steps.


State of research on SHA-1 Collision Attacks SHA-1 security has been discussed since an algorithm for finding collisions was  first published at CRYPTO 2004 and has been subsequently improved.

Wikipedia lists a couple of references, however it seems the latest research published (and later withdrawn) on this subject was in 2009 (Cameron McDonald, Philip Hawkes and Josef Pieprzyk "Differential Path for SHA-1 with complexity O(2^52)").

Since then, has any significant progress been made on reducing the effort for a hash collision attack on SHA-1?

A link to specific research accompanied with a short summary would be appreciated.

SHA-1 was SHattered by Stevens et al. They demonstrated that collisions in SHA-1 are practical. They give the first instance of a collision for SHA-1.

It is an identical-prefix collision attack that enabled the attacker to forge two distinct PDF documents that have the same SHA-1 hash value. I.e. They extended a given prefix $p$ with two distinct near-collision block pairs for any suffix $s$ that collides.

$$\operatorname{SHA-1}(p \mathbin\Vert m_0 \mathbin\Vert m_1 \mathbin\Vert s) = \operatorname{SHA-1}(p \mathbin\Vert m'_0 \mathbin\Vert m'_1 \mathbin\Vert s)$$ for any suffix $s$, where $(m_0, m_1) \neq (m'_0, m'_1)$

The computational requirement is estimated to $2^{63.1}$

  The first first-block near collision was found after spending about 3583 core years that had produced 180 711 partial solutions up to step 61. A second near collision block was then later computed; it required an additional 2987 core years and 148 975 partial solutions.1


Papers on using resource states to implement QFT efficiently I recently stumbled onto the idea of using a pre-existing re-usable phase gradient to implement the QFT, instead of having to keep re-applying exponentially precise phase gates. I'm looking for papers on this general idea (or improvements thereof).

I don't even know the technical name for this technique, so even that information would be useful.

An example QFT circuit showing the phasing-by-subtraction that I'm talking about (and the equivalent circuit in Quirk, where numbers have opposite endian-ness so lots of reversing is required):

Note that the above isn't quite as optimized as what I have in mind. In particular, when you break the subtractions down into H/CX/T gates you find that they start by undoing work the last subtraction ended with. This lets you save half of the T gates.

Here is a 2018 paper that uses phase gradient states and adders to optimize the T-count of the approximate QFT: "Approximate Quantum Fourier Transform with O(nlog(n)) T gates" by Nam et al.

(The careful reader may notice that the question precedes the paper by two years! That's because the question actually led to the paper, though indirectly. I mentioned the phase gradient operation as an application of efficient adders in this paper, Nam et al saw that, independently realized it would useful for the approximate QFT, and here we are full circle. Oh, and of course Kitaev scooped everyone by over ten years. He mentions the adding-into-phase-gradient technique in a textbook from 2002 [page 133].)


Patience Sort+ ping pong merge implementation A recent paper out of Microsoft Research describes a new, faster implementation of the patience sort algorithm.  A key part of the implementation is an improved merging strategy dubbed the "ping-pong" merge.  I am confused as to why this merge strategy uses two arrays to perform the merging, instead of just using a single array and always performing a "blind merge" as described in the paper.  It seems that always performing blind merges, and thus only using a single array to perform the merge, would cut down memory usage with no change in runtime.

I hope I understood correctly how the ping-pong merge worked. If so here is why it uses two arrays:

A typical merge operations takes two runs in an array and merges them in another arra; then, it copies the results back into the original array. When you have more than 2 runs to merge, you merge them pairwise into an array, then copy everything back to the original array, and repeat until there are no runs left.
The ping-pong merge merges runs pairwise into an array, then instead of just copying them back in the original array, it merges the resulting runs pairwise from the temporary array into another array, then to the first temporary array, then to the second one, etc... The goal is to avoid copying everything back to the original array after each series of pairwise merges.

Now, I guess that your question is actually "why does the ping-pong merge operate back and forth between two temporary arrays instead of merging runs pairwise in a single temporary array, then back to the original array, then back to the temporary array, etc...?"

Honestly, I only have one tentative explanation, and it's not really satisfying: I tend to implement algorithms in C++, and if I wrote the ping_pong_merge algorithm, it could take any pair of random-access iterators, which means that it could handle std::deque (a list of fixed-size arrays) as well as regular arrays. While std::deque has $O(1)$ element access, it is actually slower than std::vector in practice, so using two temporary arrays would ensure that the ping-pong merge only occurs between collections whose random-access is the fastest. This could be a memory vs. performance kind of problem.


Boolean functions with exponential size OBDD representation in all orders except one order? Are there boolean functions with exponential size OBDD representation in all orders except one order?

...exponential size in all orders except very few orders?

The exceptional orders should be polysize.

If there is an variable ordering $\pi$ such that the OBDD size for $f$ with this ordering is $O(poly(n))$, then a lot of OBDDs with a similar variable ordering has a size of $O(poly(n))$.

To see this you can swap neighboring variables in $\pi$, i.e. for $\pi = (x_{\pi(1)}, \ldots, x_{\pi(n)})$ you construct $\pi' = (x_{\pi(1)}, \ldots, x_{\pi(i)}, x_{\pi(i-1)}, x_{\pi(i+1)}, \ldots, x_{pi(n)})$ for some $i$. The OBDD size for $f$ with variable ordering $\pi'$ is also polynomial because you can store the value of $x_{\pi(i)}$ by doubling the $x_{\pi(i)}$ nodes in the $\pi$-OBDD for $f$. Then you have the information of $x_{\pi(i)}$ and $x_{\pi(i-1)}$ at this nodes and you can use the $\pi$-OBDD to go on.

That means if you swap $O(\log n)$ variables you also have a polynomial size OBDD.


Minimal elements of a monotonic predicate over the powerset $2^{|n|}$ Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking for an algorithm to find all the minimal elements of $P$, i.e., the $x \in 2^{|n|}$ such that $P(x)$ but $\forall y \subset x$, $\neg P(y)$. Since the width of $2^{|n|}$ is $n \choose n/2$, there could be exponentially many minimal elements, and therefore the running time of such an algorithm could be exponential in general. However, could there exist an algorithm for this task which is polynomial in the size of the output?

[Context: A more general question was asked but there was no attempt in the answers to evaluate the complexity of the algorithm in the size of the output. If I assume that there is only one minimal element, for instance, then I can perform a binary search following this answer and find it. However, if I want to continue finding more minimal elements, I need to maintain the current information I have about $P$ in a way which would make it tractable to continue the search without wasting time on what is already known. Is it possible to do this and find all the minimal elements in polynomial time in the size of the output?]

Ideally, I would like to understand if this can be done with general DAGs, but I already don't know how to answer the question for $2^{|n|}$.

Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries".

It seems that the existence of a polynomial time algorithm is still open. Schmulevich et al. prove that "Almost all monotone Boolean functions are polynomially learnable using membership queries". If we also require that the $t$th minterm be generated in time polynomial in $n$ and $t$, then the problem is equivalent to monotone dualization, as shown by Bioch and Ibaraki. Here is a survey addressing monotone dualization.


Fractional but not integer multi-commodity minimum cost flow I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar question but it considers an undirected graph or to be precise I don't catch Andreas Björklund's last comment.

Can anyone help? Thank you in advance!

You can use the example for an undirected edge with unit capacities, but replace each undirected edge from A to B with a set of directed edges that look like this.

Each edge has a unit capacity. And if you have $x$ units of flow from A to B and $y$ units of flow from B to A, you can route it as long as $x+y \leq 1$.

This is the gadget referred to in Andreas Björklund's comment.


What is the recommended software for drawing data structures such as graphs and trees? When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint.  What is the standard for drawing data structures?

The MO thread Per links to is pretty good, and this thread on tex.SE is also handy. The main tools that I've used:

TIkz/PGF
Ipe
Inkscape/Illustrator

I know that Mac folks swear by Omnigraffle, but I have zero experience with it myself. The main criteria for me are:

Generating PDF
Integrating LaTeX (with source styles for bonus points)
Being able to do color/shading etc easily. (Ipe 7 fails on that count)


How small can extension complexity be? In this article on extension complexity of regular polygons https://arxiv.org/pdf/1505.08031.pdf it is mentioned that extension complexity of $n$ regular polygons should be $\theta(\log n)$. This is an exponential gap.

Can the gap be more than exponential for some non-trivial classes of polytopes such as $n$ inequalities being replaced by projection of $o(\log n)$ inequalities? What are the best known examples?

If the lower bound is $\alpha\log_2 n-\beta$ what are the sharpest tradeoffs and bounds on $\alpha$ and $\beta$?

I think that the gap is at most exponential, and this follows from a simple duality argument. (My original answer used the upper bound theorem: thanks to Emil Jeřábek for pointing out that this is completely unnecessary.)

Let $K$ be a polytope with $m$ facets in $d$-dimensional space ($d \le m-1$), whose orthogonal projection on some subspace $W$ of dimension $k$ is the polytope $L$ with $n$ facets. Without loss of generality, we can assume that $K$ and $L$ contain the origin $0$. Let $K^\circ = \{y: \langle y, x \rangle \le 1 \ \ \forall x \in K\}$ be the polar (dual) polytope to $K$. The vertices of $K^\circ$ are exactly the normal vectors to the facets of $K$, so $K^\circ$ has $m$ vertices. Then
$$L = \{x: \langle y, x \rangle \le 1 \ \ \forall y \in K^\circ \cap W\},$$
and the vertices of $K^\circ \cap W$ are exactly the normals to the $n$ facets of $L$. (In other words, $L^\circ = K^\circ \cap W$.) Every $(d-k)$-dimensional face of $K^\circ$, when intersected with $W$, gives at most one vertex of $K^\circ \cap W$, so, $n \le f_{d-k}(K^\circ)$, where the right hand side is the number of $(d-k)$-dimensional faces of $K^\circ$. Since any face of $K^\circ$ is the convex hull of the set of vertices it contains, so it is uniquely determined by them, we have $f_{d-k}(K^\circ) \le 2^m$. So, an upper bound is $n \le 2^{m}$, i.e. the extension complexity of a polytope with $n$ facets is at least $\lceil\log_2(n)\rceil$.


Validity of exponentiation in a polynomial time reduction I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.

In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-completeness results of path computation under several additive/multiplicative constraints. The first problem is the following :

Given a directed graph $G=(V,A)$ and two weight metrics $w_1$ and $w_2$ over the edges, define, for a path $P$, $w_i(P)=\sum_{a\in P}w_i(a)$ ($i=1,2$). Given two nodes $s$ and $t$, the problem is to find a path $P$ from $s$ to $t$ s.t. $w_i(P)\leq W_i$, where the $W_i$ are given positive numbers (example: Delay constraint and cost in a network).

The authors prove that this problem is $\mathsf{NP}$-complete by providing a polynomial reduction from PARTITION.

Then they present the same problem except that the metrics are multiplicative, i.e., $w'_i(P)=\prod_{a\in P}w'_i(a)$. In order to prove the multiplicative version is $\mathsf{NP}$-complete, they provide a "polynomial" reduction from the additive version just by putting $w'_i(a)=e^{w_i(a)}$ and $W'_i=e^{W_i}$.

I am very puzzled by this reduction. Since $W'_i$ and $w'_i(a)$ are part of the input (in binary, I guess), then the $|w'_i(a)|$ and $|W'_i|$ are not polynomial in $|w_i(a)|$ and $|W_i|$. Thus the reduction is not polynomial.

Am I missing something trivial or is there a flaw in the proof? My doubt is about the validity of the proof, even if the result is clearly true.

Paper reference : Zheng Wang, Jon Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications. IEEE Journal on Selected Areas in Communications 14(7): 1228-1234 (1996).

The proof as presented in the paper is not conclusive.

However, the stated result itself is correct. It can easily be derived by slightly changing the reduction and by using SUBSET PRODUCT instead of SUBSET SUM.

A useful link for the SUBSET PRODUCT problem:
https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete


Function input to output size relationship. What is it? Any notable research on it? I'm working on a problem and I've come to a point where I need to define the input/output complexity of an algorithm. I don't remember ever studying this systematically like I did time complexity or space complexity, so what are some notable papers that deal with this problem?

Note: I'm calling it input/output complexity, but I have no idea what the actual name of this is, that would be helpful to know too! Incase it's unclear I am calling the relationship between a functions input and it's output, "Input/Output Complexity"

Examples:

F({1,2,3,4}) = {1,2} //where the relationship is n/2
F(some 20 byte input) = 2bytes of header + 10bytes of output //the relationship is 2+n/2
F(2 byte header + 10byte data) = 6 bytes output // n3/5 - 2

A more concrete example would finding be the average and best input/output complexity of a compression algorithm

Defining this is out of scope of my paper so I am hoping to find a definition/solution to reference.

I think it's improper to call this measure 'complexity'. A more apt name would be 'input to output size relation'.

Note that, strictly speaking, this is a property of the problem you are solving, not of the particular algorithm you use to solve the problem.

In the case of the compression problem, if you mean lossless compression of arbitrary binary data, then the average compression ratio is never less than 1 (and it's typically strictly greater than 1).


Integer multiplication when one integer is fixed $n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of multiplication function $f_n(x)=a_nx$ where $x\in\{0,1,\dots,2^n-1\}$?
One is allowed to pre-process integers $a_n$ as appropriate.
Upper Bound: We already have $n^{1+\epsilon}$ complexity algorithms by $\mathsf{FFT}$ and Karatsuba.
The query here is whether $\epsilon=0$ by anything cleverer?
Conjecture: $\exists c>0,n_0>0$ such that at every $n\in\mathbb Z_{>n_0}$ the number of constants $a_n$ where $\epsilon=0$ is supported is $>2^{cn}$.

While it won't always be the most efficient algorithm, this question has a very close relationship with addition chains; any algorithm for computing $A$ quickly by addition chains translates into an algorithm for computing $f(B) = AB$ by repeated addition (each addition, of course, being an $O(n)$ operation).  Contrariwise, a quick algorithm for computing $AB$ for any $B$ leads to a quick algorithm for computing $A$, but of course this algorithm doesn't necessarily have to have the form of an addition chain; still, that seems like an excellent place to start.  Have a look at http://en.wikipedia.org/wiki/Addition_chain or check out vol. 2 of The Art Of Computer Programming for more details.


Processor failures in distributed computing that are not crash or Byzantine There are two main types of processor failures in distributed computing models:

(1) Crash failures: a processor stops, and never starts again.
(2) Byzantine failures: processors behave adversarially, maliciously.

My question is:

  What are some other types of processor failures that have been studied, that do not reduce to crash or Byzantine failures?

Also, a more specific question:

  Has a model been studied where, with some probability, a process is on at time step $t$, and otherwise off?  So each process is winking on and off, as it were.

I am most interested in how these failures relate to consensus and other distributed agreement problems.

Thank you.

Copied from the comments on the question as per-request.

I have taken theory of distributed computing with Michel Raynal and he described a third model, where messages can be dropped randomly. In that model a message can fail silently to be delivered, but that doesn't necessarily mean that the node has failed. It is about link failures rather than node failures "fair lossy channel model", you can read more about it here : Quiescent Uniform Reliable Broadcast as an Introductory Survey to Failure Detector Oracles - Michel Raynal (ftp.irisa.fr/techreports/2000/PI-1356.ps.gz)


Does Rabin/Yao exist (at least in a form that can be cited)? In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation".  This is for the result that the bounded-error communication complexity of the equality function EQ$_N$ (whether two integers in the range $0$ to $N-1$ are equal) is $O(\log\log N)$.

Andrew Chi-Chih Yao, Some Complexity Questions Related to Distributed Computing (Preliminary Report), STOC 1979, pp. 209–213.  doi:10.1145/800135.804414

Alexander Razborov's introductory survey on communication complexity proves this result and states "the following beautiful construction [is] usually attributed to Rabin and Yao".  The idea is to consider the bit strings as coefficients of a predetermined polynomial $P(x)$; Alice then picks a random integer $q$ from 0 to $p-1$ for some predetermined prime $p \in [3n,6n]$, where $n = \lceil \log N\rceil$, and sends $(q, P(q) \mod p)$ to Bob.

Alexander Razborov, Communication Complexity, chapter 8 of "An Invitation to Mathematics", pp. 97–117, Springer, 2011.  (preprint)

Did the Rabin/Yao paper ever get to be at least a personal communication/draft/sketch in someone else's paper, or is this one of those indications of the "golden era" where giants roamed the earth and didn't always touch ground when stepping from breakthrough to breakthrough?

After more than two years, I have to assume the answer is "no".  (Posting this stub answer so the question can be marked as answered.)


Reducing 3-XOR-SAT to HORN-SAT In this question - XOR-SAT to Horn-SAT reduction, two algorithms are described for reducing any XOR-SAT formula to a HORN-SAT formula.

My question is: say I limit the clauses of an XOR-SAT formula to exactly three variables per clause, is there a specific HORN-SAT formula that is equisatisfiable with each clause? If so, why not just replace all of the XOR clauses using that formula and instead go through the algorithms described in the question above?

As an example of what I mean, it is possible to reduce any 3SAT clause to an equisatisfiable XSAT clause as described here: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Exactly-1_3-satisfiability. Is the same possible for 3-XOR-SAT and HORN-SAT?

The question is not very clear, as equisatisfiability of individual clauses does not imply equisatisfiability of the whole formulas.

However, if you mean a construction where each XOR clause is replaced by a set of of Horn clauses—possibly using new variables—so that the satisfying assignments of the original clause are exactly the projections of the satisfying assignments of the new set of clauses, this is impossible. In other words, this would make the XOR clause pp-definable from a set of Horn clauses, but all Boolean relations pp-definable from Horn clauses have the binary conjunction operation as a polymorphism, whereas conjunction is not a polymorphism of any XOR clause in more than two variables.


What is the fastest known simulation of BPP using Las Vegas algorithms? $\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes.

$\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the probability of algorithm returning an incorrect answer is bounded, i.e. the error probability is at most $\frac{1}{3}$ (for both YES and NO instances).

On the other hand,
$\mathsf{ZPP}$ algorithms can be viewed as those probabilistic algorithms
which never return an incorrect answer, whenever they return an answer it is correct.
However their running-time is not bounded by a polynomial, they run in expected polynomial.

Let $\mathsf{ZPTime}(f)$ be the class of language decided by probabilistic algorithms with zero error probability and expected running-time $f$. These are also referred to as Las Vegas algorithms and $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$.

My question is what is best know simulation of $\mathsf{BPP}$ algorithms using Las Vegas algorithms? Can we simulate them in subexponential expected time? Is there any known improvement over the trivial brute-force simulation which takes exponential time?

More formally, do we know if
$\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ or $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ for some $\epsilon>0$?

First, observe that if $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ for some constant $c$, then $\mathsf{BPP} \neq \mathsf{NEXP}$. (Proof by nondeterministic time hierarchy.) So proving such an inclusion would be significant, not just because it's an improved simulation but also would yield the first progress on randomized time lower bounds in decades.

Next, consider the class $\mathsf{PromiseBPP}$, for which the following problem is "$\mathsf{PromiseBPP}$-hard":

  Circuit Approximation Probability Problem (CAPP):  Given a circuit $C$, output the acceptance probability of $C$ to within a $1/6$ additive factor.

Results of Impagliazzo, Kabanets, and Wigderson 2002 imply that a $2^{n^{\varepsilon}}$ time zero-error algorithm for CAPP (where $n$ is the size of $C$) would imply $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. In STOC'10, I extended this to show: supposing for every $C$ with $k$ input bits and $n$ size, one can compute CAPP nondeterministically (so, zero-error suffices) in $2^{k-\omega(\log k)}\mathrm{poly}(n)$ time, then $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. That is, there are certainly problems computable with two-sided-error randomness, for which zero-error algorithms that even mildly beat exhaustive search would imply circuit lower bounds. I believe this should be interpreted as a possible method for proving lower bounds; your mileage may vary.

Notice that even proving $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ is also open, and proving that would also imply lower bounds: by Kabanets and Impagliazzo 2004, if polynomial identity testing (a $\mathsf{coRP}$ problem) is in $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ for all $\varepsilon > 0$, then we have lower bounds for either the Permanent or $\mathsf{NEXP}$. Recently (upcoming in STOC'13), I proved unconditionally that either $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ or $\mathsf{RTIME}[2^n]$ has $n^c$ size circuits, building on the "easy witness" method of Kabanets. This implies two things:

There is a $c$ such that for all $\varepsilon > 0$, $\mathsf{RP}$ is unconditionally in $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ -- this is about the best unconditional derandomization of $\mathsf{RP/BPP}$ in $\mathsf{ZPP}$ that we know so far.
To start getting interesting subexponential simulations of $\mathsf{BPP}$, you "only" have to assume $\mathsf{RTIME}[2^n]$ doesn't have fixed-polynomial-size circuits.


Heuristics for tsp without triangle inequality Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds.

Are there heuristics to solve the tsp that don't assume the triangle inequality and still perform well*?
If there aren't, why is that?

*i.e. don't run for a year for 100 cities and get relatively close to the optimum

I hope this partly answers your question: Most known heuristics like Greedy, Naerest Neighbor, Lin-Kerninhan etc.
perfrom quite well for (symmetric) TSP without triangle inequality.

You may check these heuristics with the Concorde TSP Solver
which is the best TSP solver I know so far.

In theory, there is no heuristic for TSP without triangle inequality that performs well
(like Christofides for metric TSP).
This is due to the well known fact that TSP cannot be approximated within any
polynomial time computable function unless P=NP.


clustering algorithm for non-dimensional data i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this dataset. i imagine that because the data has no dimensions, a cluster center might consist of several data points and a tolerance, and membership within the cluster might be determined by the average of the distance of a data point to every data point in the cluster center.

please forgive me if this question has a well known solution, i know very little about this kind of problem! my (very limited) research has only turned up clustering algorithms for dimensional data, but i apologize in advance if i've missed something obvious.

thank you!

If the distance function is a metric, then you can employ either $k$-center clustering (where the maximum radius of a ball is minimized) or $k$-median clustering (which minimizes the sum of distances to cluster centers). $k$-center clustering is easy: merely pick the $k$-farthest points, and you're guaranteed to get a 2-approximation via triangle inequality (this is an old result due to Gonzalez).

For $k$-median clustering, there's been a ton of work, too much to review here. Michael Shindler at UCLA has a nice survey of the main ideas.

Both these problems are NP-hard in general, and are hard to approximate to within an arbitrary factor. Note that if you drop the condition of being a metric, things get a lot worse in terms of approximability.

Another, more heuristic approach which might be ok for your application is to use a technique like MDS (multidimensional scaling) to embed your distance matrix in a Euclidean space, and then use one of many different Euclidean clustering methods (or even $k$-means clustering). If you are sure that your distance function is a metric, then you can do a slightly more intelligent embedding into Euclidean space and get a provable (albeit weak) guarantee on the quality of your answer.

Ultimately, as with most clustering problems, your final choice depends on the application, your data size, and so on.


Unification and Gaussian Elimination Does anyone knows of references that precisely spell out the connection between the unification algorithm and Gaussian elimination? I'm particularly interested in the relationship between triangular substitutions and LU decompositions.

Wayne Snyder and Jean Gallier mention this analogy in passing in their paper, Higher-Order Unification Revisited: Complete Sets of Transformations.

I don't consider this an answer. I'm abusing the answer box to pretty print a comment.
There is a strict sense in which Euclid's GCD algorithm, Gaussian elimination, Buchberger's algorithm and Knuth-Bendix form a strict sequence of generalisations and are all instances of what is called a completion algorithm. There is also a close relationship between these algorithms and resolution in logic. I do not know a good reference for this but I have seen the fact mentioned very often. These might help.

History and basic features of the critical-pair/completion procedure, Bruno Buchberger, 1987
Canonical Reduction Systems in Symbolic Mathematics, Franz Winkler. Springer Link

Let me know if you find better references.


How to become a Theoretical Computer Scientist I am a computer science graduate from India. I have worked in a reputed software company for 10 months only to discover that my area of interest is something else. So I resigned from there and I am presently preparing for GATE 2014 which is due in a few days. Now I have the following doubts in my mind :
 1. Is it sufficient and necessary to get into a reputed college in India through GATE ?
 2. Are there any alternatives to pursue a career in Theoretical CS ?
 3. How about foreign universities for this career path ?

Please provide me some career guidelines. Thanks in advance.

You asked three questions:

Q1 is really out of scope for this forum: it relates to GATE and how you gain admission to Indian grad schools.
Q2 I interpret as "do I need a graduate degree to study theoretical computer science". In general, of course the answer is "no", but the discipline of studying at the grad level (with the access to professors and other grad students) is hard to replace with a self-study unless you're supremely motivated.
Q3: of course you can apply to foreign universities for graduate studies: again, you might find it useful to peruse academia.stackexchange.com for a plethora of information on how to go about doing this.


Does the existence of PH-complete problems relativize? The Baker-Gill-Solovay result showed that the P = NP question does not relativize, in the sense that no relativizing proof (insensitive to the presence of an oracle) can possibly settle the P = NP question.

My question is:  Is there a similar result for the question, "Does there exist a PH-complete problem?"  An answer in the negative to this question would imply P != NP; an answer in the affirmative would be unlikely but interesting because it would mean that PH collapses to some level.

I'm not sure, but I suspect that a TQBF oracle would lead PH to be equal to PSPACE, and thus to have a complete problem.  In addition to being uncertain regarding this, I am curious as to whether or not there is an oracle relative to which PH provably does not have a complete problem.

-Philip

Yao showed, in 1985, that there exist oracles relative to which the Polynomial Hierarchy is infinite. Relative to such an oracle, there don't exist PH-complete problems.

Also, you are right that with a TQBF oracle, PH equals PSPACE. In fact, even P = PSPACE in the presence of a TQBF oracle.


Why isn’t information-probability relationship linear? I am completely new to information theory.
I was learning about information content but couldn’t make sense of why the relationship between information content and probability isn’t linear? And why it is sub-linear?
As the formula goes,
$$
I(E) = -\log p(E).
$$

So definition of self-information is chosen to be as follows (shamelessly copied from wiki page of "Information content" ) :

An event with probability 100% is perfectly unsurprising and yields no information.

The less probable an event is, the more surprising it is and the more information it yields.

If two independent events are measured separately, the total amount of information is the sum of the self-informations of the individual events.

Point 3 of the definition answers your question.
If $A$ and $B$ independent events and C is an event where both $A$ and $B$ take place then
$$P(C) = P(A \cap B) = P(A)\cdot P(B)$$
On the other hand information from $C$ is defined as follows:
$$I(C) = I(A)+I(B)$$
Let $f(\cdot)$ be the functional form of the information expression, formally $$I(E) = f(P(E))$$
Therefore,
$$f(P(C)) = f(P(A)) + f(P(B))$$
$$ = f(P(A).P(B))$$
Can you find an $f(x)$ which is of the form $k\cdot x$, such that the above properties are satisfied ? I think the answer is no.
But I would like to add that I don't recall very neat reasons for why it has to be only $k\log(x)$ as well. i.e why only $f(x) = k\log x $ satisfies $f(x\cdot y) = f(x)+f(y)$


Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH) In the wikipedia article on Time Complexity it is written that:

  The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, at most, three literals per clause and with n variables, cannot be solved in time $2^{o(n)}$. More precisely, the hypothesis is that there is some absolute constant $c>0$ such that 3SAT cannot be decided in time $2^{cn}$ by any deterministic Turing machine.

We have $2^{o(n)} = \bigcap_{c > 0} O(2^{cn})$.

Proof: For the inclusion $2^{o(n)} \subseteq \bigcap_{c > 0} O(2^{cn})$.
Let $f \in o(n)$, then we know that for each $c > 0$ we can find an $N_c$ such that for $n > N_c$ we have $f(n) < cn$, or $2^{f(n)} < 2^{cn}$ which gives this inclusion. For the inclusion $\bigcap_{c > 0} O(2^{cn}) \subseteq 2^{o(f)}$. Let be some function $g : \mathbb N \to \mathbb N \in \bigcap_{c > 0} O(2^{cn})$, i.e., for each $c > 0$ we have some $N_c$ such that for $n > N_c$ we have $g(n) < 2^{cn}$. Taking logarithms this gives $\log g(n) < cn$. So we have $\log g(n) \in o(n)$.

But ETH is about algorithms, so if we can find for each $c > 0$ some algorithm running in time $O(2^{cn})$, this does not imply that we have a single algorithm running in the intersection of those times, i.e., in $2^{o(n)}$ by the above. So there is still the possiblity that we cannot solve a problem in $2^{o(n)}$, but we can solve it by giving for each $c > 0$ some algorithm $A_c$ that solves it in $O(2^{cn})$. So claiming that something is not solvable in $2^{o(n)}$ is actually a stronger claim than saying we have a $c > 0$ such that the problem cannot be solved in $O(2^{cn})$.

But is there any example of such a problem, i.e. a problem such that for each $c > 0$ we have an algorithm (deterministic TM) running in time $O(2^{cn})$, but we cannot give an algorithm running in time $2^{o(n)}$?

Yes, an example is:
Accept $0^k 1^m$ iff $k>0$ and the $k$th Turing machine halts in less than $2^{m/k}$ steps on the empty input.  Other strings are rejected.  See question Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$? for the proof.

I expect that there is a relativization barrier against proving equivalence of ETH with its weakening using $2^{o(n)}$, and that there are oracles relative to which (note that this is not ETH) for every $ε>0$ every relativized NP-complete problem can be solved in time $O(2^{n^ε})$ but not in time $2^{n^{o(1)}}$.


Energy cost of adiabatic quantum computation I'm not sure whether this question is completely on-topic, since it is a physics-related question. But I'll ask anyway and apologize if I'm off-topic.

In Adiabatic Quantum Computation is Equivalent to Standard
Quantum Computation the autors mention a tradeoff between runtime and energy:

"Observe that we have chosen our definition of running time to be $T · \max_s \lVert H(s)\rVert$ and not T.
Notice that if the Hamiltonians are multiplied by some factor, this divides the bound of Equation
2, and hence T, by the same factor. Hence, if the running time is defined to be T one would be able
to achieve arbitrarily small running times, by multiplying the Hamiltonians by large factors. Our
definition, on the other hand, is invariant under a multiplication of the Hamiltonian by an overall
factor, and so takes into account the known physical trade-off between time and energy.5

5This trade-off between time and the norm of the Hamiltonian (namely, the energy), is manifested in Schrödinger’s
equation whose solution does not change if time is divided by some factor and at the same time the Hamiltonian is
multiplied by the same factor."

But if I understand correctly, adiabatic quantum computation is completely reversible: by inverting the direction of time the system evolves back from the final state to the initial state.

Moreover, any adiabatic quantum computation process can be implemented (with arbitrary precision) in the conventional quantum circuit model, where all the gates are unitary and thus reversible.

According to Landauer's principle, reversible computation could be, in principle, executed without any energy consumption.

So my question is, what exactly the time-energy tradeoff in the choice of Hamiltonians for adiabatic quantum computation means?

Basically, the computation is reversible, so you are not actually using energy. However, the rate at which a computation progresses is generally proportional to the energy gap within the system. In the case of adiabatic quantum computation, the rate at which you can transition between ground states of the initial and final system is determined by the energy gap between the ground state and the low lying excited levels of the system. Thus the energy gap in the Hamiltonian (the total energy operator) is what determines the rate of computation, and so scaling up the energy levels involved allows the computation to be performed more quickly, even though the process does not actually consume the energy.

You might be interested in looking at the Margolus-Levitin theorem, which gives limits for the rate of computation by imposing a lower bound on the time taken for a system to transition to an orthogonal state in terms of the energy gap present in the system. This applies more generally than simply to adiabatic quantum computing.

In general, you tend to get a linear trade-off between energy scale and time. One way to see where this comes from is simply to think about the case of a constant Hamiltonian. In that case, the time evolution operator is $e^{-iHt}$. Clearly multiplying $H$ by some constant $k$ and dividing $t$ by $k$ leads to the same operator, and hence the same evolution of the system. You can do this more generally, with a potentially time dependent Hamiltonian by looking at the Schroedinger equation: $i \hbar \frac{\partial}{\partial t} \mid \Psi \rangle = H \mid \Psi \rangle$. Replacing $H$ with $kH$ and $t$ with $\frac{t}{k}$ we obtain the same equation.


Complexity classes not closed under intersection and union Some of the better known complexity classes: PP, NP, P... are closed under intersection and union. What are some counter-examples? Is there a natural reason for the common complexity classes to be closed under these operations?

The class $AWPP$ is not known to be closed under union, though it is easy to show it is closed under intersection
For the class $A_0PP$ it's the other way around: it is closed under intersection, but not known to be closed under union.

These classes have nice machine model definitions, namely they are something akin to an abstract version of the quantum complexity classes $BQP$ and $QMA$, respectively. These classes, in turn, are the quantum analogues of $P$ and $NP$, respectively. Let me give the definition (The Zoo) of $AWPP$:

Definition$^{(\ast)}$ (AWPP) A language $L\subseteq \{0,1\}^\ast$ is in $AWPP$ when there is a Gap function $g\colon \{0,1\}^\ast\to \mathbb{Z}$ satisfying the following Soundness and Completeness properties for a polynomial $p(x)$ and a polynomial-time computable function $f(x)$:

Soundness If $x\not\in L$ then $0\leq g(x)\leq 2^{-p(x)}f(x)$
Completeness If $x\in L$ then $(1-2^{-p(x)})f(x)\leq g(x)\leq f(x)$

These soundness and completeness conditions are precisely what you get if you were to (1) trace through the definition of $BQP$ using only the Hadamard gate and classical gates and then (2) interpret the acceptance probabilities as "paths", and then (3) impose that there is a large gap in acceptance probabilities depending on whether $x\in L$ or not.

It is interesting that this is not known, because both $BQP$ and $QMA$ are known to be closed under intersection and union. As far as I know, there have been no publications exploring the closure properties of these classes; perhaps they are a bit niche, or perhaps I am simply ignorant.

Of course it is also unknown whether $AWPP$ and $A_0PP$ are closed under complement, because this would imply the other closures as well; the converse does not hold; they may be closed under union and intersection but not complement, like $NP$ probably is.

$^{(\ast)}$In this definition, the polynomial $p(x)$ can be replaced by a polynomial $p^\prime(n)$ which depends only on $n=|x|$ the length of the string; similarly the function $f(x)$ can also be replaced by such a polynomial $f^\prime(n)$. This may make certain things easier to prove.