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

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

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.

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The hierarchy for circuit size, see previous question.

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

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

[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 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 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 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 1 votes For the Inner Product function that quantity is$2^{n/2}\$, which is the largest possible value.