Yuval Filmus
  • Member for 11 years, 5 months
  • Last seen this week
Is $AC^0/poly \cap NP$ contained in $P$?
Accepted answer
32 votes

Here's a simplification of Ryan's answer. Suppose that $\Lambda \in NE \setminus E$. Define the language $L = \{x : |x| \in \Lambda\}$. The assumption $\Lambda \in NE \setminus E$ translates to $L \in ...

View answer
Representing OR with polynomials
30 votes

Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just ...

View answer
Reasons for which a graph may be not $k$ colorable?
Accepted answer
29 votes

You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least $k$ has a subgraph which has a "reason" for requiring $k$ colors. The reason in question is a proof ...

View answer
The cozy neighborhoods of "P" and of "NP-hard"
20 votes

Russell Impagliazzo's proof of Ladner's theorem furnishes an example for 3. For completeness' sake, below I copy the definition of the algorithmic task $X$ and sketch the proof that it is on "both ...

View answer
Graph theoretic restriction to Proofs in Proof Complexity Theory
19 votes

The most natural restriction on the proof DAG is that it be a tree – that is, any "lemma" (intermediate conclusion) is not used more than once. This property is called being "tree-like". General ...

View answer
Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?
Accepted answer
19 votes

No. Consider the following function on $\{0,1\}^n$: $$ f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}). $$ Clearly this function is hard for AC0. On ...

View answer
A special class of languages: “circular” languages. Is it known?
Accepted answer
19 votes

In the first part, we show an exponential algorithm for deciding circularity. In the second part, we show that this the problem is coNP-hard. In the third part, we show that every circular language is ...

View answer
Who introduced the complexity class AC?
Accepted answer
18 votes

I believe that the notation AC first appears in Cook's "A Taxonomy of Problems with Fast Parallel Algorithms" from 1985. On page 11 (page 12 of the journal) we read: To state a more general form of ...

View answer
What is worst case complexity of number field sieve?
Accepted answer
16 votes

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's ...

View answer
The Cost of an Equivalence Query for DFA
Accepted answer
16 votes

According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does not generate all ...

View answer
Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"
Accepted answer
14 votes

There are two loanable copies at The National Library of Israel. Here is a scanned copy.

View answer
Was bombe machine turing complete?
Accepted answer
14 votes

No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in ...

View answer
Anti-chromatic number
Accepted answer
14 votes

Your problem is equivalent to maximum matching. In an optimal coloring, each color class is connected. Choosing one edge from each color class, we get a matching. This shows that the maximum matching ...

View answer
finding smallest k elements in array in O(k)
14 votes

Assume for simplicity that $n = 2^m$. Use the linear time selection algorithm to find the elements at positions $2^{m-1},2^{m-2},2^{m-3},\ldots,1$; this takes linear time. Given $k$, find $t$ such ...

View answer
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Accepted answer
14 votes

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 "...

View answer
Power of randomness vs. power of indefinite computation
Accepted answer
13 votes

Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects ...

View answer
questions on implications Babais quasi P time graph isomorphism result
Accepted answer
13 votes

Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two ...

View answer
Sensitivity-Block sensitivity conjecture - Implications
13 votes

Here is what Scott Aaronson has to say on the subject: What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity ...

View answer
Applications of $p$-adic numbers in CS
13 votes

De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers ...

View answer
Smallest known formula for the determinant
Accepted answer
13 votes

One way is described in Berkowitz, On computing the determinant in small parallel time using a small number of processors (see also Soltys, Berkowitz's algorithm and clow sequences). Another way is ...

View answer
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
13 votes

Not exactly what you asked for, but a situation "in the wild" in which a log factor appears in the denominator is the paper "Pebbles and Branching Programs for Tree Evaluation" by Stephen Cook, Pierre ...

View answer
Why does randomness have stronger effect on reductions than on algorithms?
13 votes

In the oracle world, it is easy to give examples where randomness gives us much more power. Consider, for example, the problem of finding a zero of a balanced Boolean function. A randomized algorithm ...

View answer
The computational complexity of matrix multiplication
13 votes

Classical work of Coppersmith shows that for some $\alpha > 0$, one can multiply an $n \times n^\alpha$ matrix with an $n^\alpha \times n$ matrix in $\tilde{O}(n^2)$ arithmetic operations. This is ...

View answer
Polynomial-time algorithms with huge exponent/constant
13 votes

The solution of Annihilation Games (Fraenkel and Yesha) has complexity $O(n^6)$.

View answer
Results in Theoretical CS independent of ZFC
13 votes

It depends on your definition of "Computer Science". Take the example below - does it count? A coding of the integers is a uniquely decodable binary code of $\mathbb{N}$. If the length of the ...

View answer
Do there exists polynomial size CFG that describe this finite language?
13 votes

Chomsky normal form A CFG is in CNF (Chomsky normal form) if the only productions are of the form $A \rightarrow a$ and $A \rightarrow BC$; a grammar can be brought to CNF with only quadratic blowup....

View answer
Post Correspondence Problem variant
13 votes

Edit: This solves an earlier version, in which we have to decide whether there is an equality of the form $\alpha_{i_1} \cdots \alpha_{i_K} = \beta_{j_1} \cdots \beta_{j_{K'}}$. The new version ...

View answer
Johnson and Lindenstrauss lemma for hamming space
12 votes

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, ...

View answer
Examples of Computer-Found Optimal Strategies in Games
12 votes

The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; ...

View answer
Bigger picture behind the choice of matrices in the Strassen algorithm
12 votes

There is some sort of explanation in the book Algebraic Complexity Theory by Bürgisser, Clausen and Shokrollahi (p. 11-12). The idea is to start with two bases $A_0,A_1,A_2,A_3$ and $B_0,B_1,B_2,B_3$ ...

View answer
1
2 3 4 5 6