Most Popular
1500 questions
15
votes
1 answer
$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…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
15
votes
5 answers
History of recursion
Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?
Srinivas Reddy Thatiparthy
- 261
- 2
- 7
15
votes
1 answer
Any polynomial which is hard to count but easy to decide?
Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate
polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial
$f(x_1,\ldots,x_n)$, the circuit
computes $f$ if $F(a)=f(a)$…
Stasys
- 6,765
- 29
- 54
15
votes
1 answer
Does ${\bf AC^0PAD} = {\bf PPAD}$?
What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem?
Recently giving faster algorithms for Circuit satisfiability for small…
domotorp
- 13,931
- 37
- 93
15
votes
2 answers
Does XOR automata (NXA) for finite languages benefit from cycles?
A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA case).
It is easy to see that for a finite regular…
R B
- 9,448
- 5
- 34
- 74
15
votes
3 answers
Complexity of edge coloring in planar graphs
3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable".
What is the complexity of 3-edge coloring of cubic planar graphs?
Also, It is conjectured that…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
15
votes
1 answer
Graph decompositions for combining "local" functions of vertex labelings
Suppose we want to find
$$\sum_x \prod_{ij \in E} f(x_i,x_j)$$
or
$$\max_x \prod_{ij \in E} f(x_i,x_j)$$
Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a graph $G=\{V,E\}$ and $f$ is an arbitrary…
Yaroslav Bulatov
- 4,701
- 1
- 25
- 39
15
votes
1 answer
A course for learning algebraic complexity
I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.
Is there a set of lecture notes, books, papers and surveys for students who have read standard textbook about theory like Sipser's book or the…
shen
- 211
- 1
- 4
15
votes
0 answers
Mixing properties of random walks on graphs
I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.
One of the main ideas of the paper is that random walks on graphs can be used to find sets with small isoperimetric ratio. The principle seems to be…
Paul Siegel
- 259
- 1
- 7
15
votes
6 answers
Is there a formal proof that quantum computing is or will be faster than classical computing?
Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?
Alex Moore-Niemi
- 261
- 2
- 6
15
votes
1 answer
Chernoff bound for weighted sums
Consider $X = \sum_i \lambda_i Y_i^2$, where $\lambda_i$ > 0 and $Y_i$ is distributed as a standard normal. What kind of concentration bounds can one prove on $X$, as a function of the (fixed) coefficients $\lambda_i$?
If all the $\lambda_i$ are…
Thomas
- 445
- 2
- 7
15
votes
1 answer
Random monotone function
In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the following sentences:
Here the issue is not…
Kaveh
- 21,577
- 8
- 82
- 183
15
votes
3 answers
Good text on introduction to circuit complexity
I would like to ask suggestions for good texts which introduce circuit complexity. Any pointers to recent advances and open problems in this field would also be helpful.
shrm
- 253
- 1
- 6
15
votes
1 answer
Homotopy type theory and Gödel's incompleteness theorems
Kurt Gödel's incompleteness theorems establish the "inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic".
Homotopy Type Theory provides an alternative foundation for mathematics, a univalent foundation…
hawkeye
- 2,581
- 1
- 18
- 34
15
votes
1 answer
Does PSPACE-completeness imply approximation hardness?
It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it?
Is this "tight"? (i.e., are there PSPACE-complete problems whose optimization problem admits…
R B
- 9,448
- 5
- 34
- 74