Manu
  • Member for 11 years, 5 months
  • Last seen more than a month ago
Are runtime bounds in P decidable? (answer: no)
Accepted answer
87 votes

The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M'$ that works as follows: ...

View answer
Techniques for Reversing the Order of Quantifiers
25 votes

Impagliazzo's hard-core set lemma allows you to switch quantifiers in the context of computational-hardness assumptions. Here's the original paper. You can find tons of related papers and posts by ...

View answer
Applications of TCS to classical mathematics?
19 votes

Although I am biased, I think it's fair to say that various ideas from TCS have contributed to progress on the inverse conjecture for the Gowers norm, see e.g. the paper by Green and Tao.

View answer
$\overline{SAT} \in NTIME(subexp)$?
Accepted answer
17 votes

It is possible ;-) It would give new circuit lower bounds. Since you are making a pretty strong assumption this could follow from the seminal work by Impagliazzo, Kabanets, and Wigderson, I haven't ...

View answer
Simplest proof of NP-completeness
Accepted answer
17 votes

What about { (M,$1^t$) : M is a turing machine that, run on a blank tape, accepts within t steps} ? The proof of NP-completeness is a simple exercise from the definition.

View answer
Best known joint containments for/by NP and Parity-P?
Accepted answer
17 votes

By Valiant-Vazirani, NP is contained in BP dot Parity-P (which obviously contains Parity-P). Moreover, Toda showed that PH is in BP dot Parity-P which is in P^(#P) (which is in PSPACE). For lower ...

View answer
On fooling $AC^0$
Accepted answer
15 votes

1) What is meant by necessary is that one way to generate a $k$-wise independent distribution is to break the input in blocks of $k+1$ bits, and let the $(k+1)$th bit of each block be the parity of ...

View answer
What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
14 votes

The following seems to be new and relevant information: The paper [CKKL99] shows how to get 1/n close to a uniform permutation of n elements using a switching network of depth O(log n), and hence a ...

View answer
The Examiner's Problem (uniform generation of SAT decision instances/answers)
Accepted answer
12 votes

The question you are asking is equivalent to unary NP = unary P, which in turn is equivalent to NE = E, by padding. From the title, perhaps you meant to ask if it is possible to generate input/output ...

View answer
Algorithms from the Book.
12 votes

Avi Wigderson in Part II of these lectures gives the following examples of algorithmic gems, with pseudocode: Shortest path (Dijkstra's algorithm) Pattern matching (Knuth-Morris-Pratt's algorithm) ...

View answer
One-way functions with respect to various resource bounds
Accepted answer
11 votes

Regarding log-space: Several candidate one-way functions are computable in log-space or below (and are supposedly secure even against poly-time adversaries). You can find several pointers for ...

View answer
Algorithm to find shortest path from a set of nodes to another set of nodes?
Accepted answer
11 votes

Create a new node $s$ and connect it to every node in the first list. Create a new node $t$ and connect it to every node in the second list. Find a shortest path between $s$ and $t$.

View answer
Good seating arrangements for sequence of meals and tables of size k for a group of people
Accepted answer
11 votes

Here's a variant of the original answer (below) that gives the desired setting: tables of size 5, 45 people, and 10 meals, except that one meal has a few tables of size 4. Let $F$ be the field of ...

View answer
Small steps for better TCS conferences?
11 votes

Do not restrict the length of submissions. Instead, ask authors to make their points within X pages, and inform them of the length of camera-ready versions. While some recent PC have courageously done ...

View answer
Fooling arbitrary symmetric functions
Accepted answer
11 votes

Yes, a general solution to this problem has recently been given by Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman, see Pseudorandom Generators for Combinatorial Shapes. That paper ...

View answer
Pseudorandom generator for finite automata
10 votes

If $d$ is of the order of $n$ then you can write a constant-width branching program as a finite-state automaton, and logarithmic seed length is not known. But if $d$ is very small, say a constant, ...

View answer
Difference between theory and practice of security and cryptography?
8 votes

There is a significant gap even when it comes to basic primitives such as pseudorandom generators. Consider for example pseudorandom functions. In practice people use things like AES, which differ ...

View answer
Small steps for better TCS conferences?
8 votes

Include among important dates the date for special issue invitations. Otherwise, how long are authors supposed to wait for?

View answer
Testing for positivity instead of equality
7 votes

See The communication complexity of addition. As Grigory mentioned, there is a protocol with communication $O(\log n)$. This is due to Nisan and Safra. Their protocol either uses public randomness ...

View answer
What are the different notions of one-way functions?
Accepted answer
7 votes

Usually one-way functions are used for crypto, and so you want that no efficient adversary can invert the function. Identifying efficient adversaries with randomized polynomial-time, you get the ...

View answer
Major unsolved problems in theoretical computer science?
6 votes

Some open problems in complexity theory lower bounds, together with their relationships, are mapped here.

View answer
What hierarchies and/or hierarchy theorems do you know?
6 votes

The hierarchy for circuit size, see previous question.

View answer
Which complexity class does this number theory problem belong to?
5 votes

Added later: As noted in the comments, the NP upper bound is trivial if a, b, and c are positive, as was asked. Theorem 1.2 in this paper shows that deciding if a given diophantine equation in two ...

View answer
Additive combinatorics applications in algorithm design
5 votes

If you include testing in algorithm design, Samorodnitsky uses additive combinatorics to show that linear transformations are efficiently testable [here].

View answer
Viola's Reduction of 3XOR to listing triangles
4 votes

[Copying here the answer from here] In this paper, Corollary 1, we show that if you solve 3XOR in close to linear time then you can list $t$ triangles in a graph with $m$ edges in time $m\cdot t^{1/...

View answer
Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?
4 votes

If I understand correctly you are asking about the relationship between the degree necessary for exact representation and the degree necessary for approximate representation. The seminal paper by ...

View answer
Size hierachy for uniform circuits
4 votes

Regarding your last question: The paper Size-Depth Trade-offs for Threshold Circuits shows that the parity function requires depth-$d$ threshold circuits with $\ge n^{1+\epsilon(d)}$ wires, which is ...

View answer
Publishing short and simple results
2 votes

You could try a good journal first, see what reviews you get, and then decide. Journals sometimes make decisions that program committees are unwilling to make (and vice versa). Some journals even ...

View answer
Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?
1 votes

For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value.

View answer
Small steps for better TCS conferences?
-1 votes

If a submission is (essentially) a resubmission of a previosuly-rejected paper, the authors should copy and paste previous reviews (in a text box on the submission server), together with a very brief ...

View answer