8
A full proof (based on superconcentrators) can be found in chapter 24 "The pebble game" of the book
Uwe Schöning and Randall Pruim:
Gems of Theoretical Computer Science
Springer, 1998
ISBN 978-3-642-64352-1
https://link.springer.com/book/10.1007%2F978-3-642-60322-8
5
Two answers that I learnt while writing a blog post about this question
No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. As Ron points out, this extends to computational complexity under plausible assumptions.
Maybe: Nash equilibrium is arguably the flagship problem of "Christos ...
5
Not sure whether I am missing something, but...
The Omega(n/log n) lower bound is from:
[PTC77] Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. Mathematical Systems Theory, 10:239–251, 1977.
There is a strengthening of this to a non-deterministic version of the pebble game (so-called black-white pebbling) in:
...
2
From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper.
Bonfante, ...
2
In regards to (2), conditional super-linear lower bounds are known. A recent preprint by Afshani, Freksen, Kamma, and Larsen proves an $\Omega(n \log n)$ lower bound for the size of Boolean circuits computing integer multiplication, assuming a certain conjecture on network coding in undirected graphs. (See also this blog post and a follow-up post.)
From the ...
2
Theorem: The special case of 1-in-3-SAT where each variable
appears an even number of times is NP-hard.
Proof: Consider an instance $I$ of 1-in-3-SAT, and let $a_1,\ldots,a_n$
be an enumeration of the variables in $I$.
Assume that variables $a_1,\ldots,a_m$ occur an odd number of times,
whereas $a_{m+1},\ldots,a_n$ occur an even number of times.
...
2
I will attempt to elaborate a bit on why CHKPRR shows that $\mathsf{PPAD}$ is plausibly hard for quantum computers.
At a high level, CHKPRR builds a distribution over end-of-line instances where finding a solution requires to either:
break the soundness of the proof system obtained by applying the Fiat-Shamir heuristic to the famous sumcheck protocol, or
...
1
In the approximation algorithms side, there is an $(2-2/\Delta)$-approximation algorithm by Hochbaum where $\Delta$ is the maximum degree of the graph. This translates to a 1.33-approximation algorithm for cubic graphs. It seems like there hasn't been any improvement over this.
1
Actually, injective reductions are useful in cryptography.
Suppose you have a ZK proof system for an NP relation R over the language L.
If you want to build a ZK proof for another NP relation R' over a language L', you have to find two functions f and g with the following properties:
1. x belongs to L' iff f(x) belongs to L,
2. If (x,w) belongs to R' then (...
Only top voted, non community-wiki answers of a minimum length are eligible
