user avatar
user avatar
user avatar
argentpepper
  • Member for 11 years, 4 months
  • Last seen this week
49 votes
4 answers
2k views

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

25 votes
1 answer
731 views

What is $\mathsf{NP}$ restricted to linear size witnesses?

20 votes
0 answers
453 views

Interesting PCP characterization of classes smaller than P?

12 votes
1 answer
183 views

What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

10 votes
1 answer
1k views

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

10 votes
1 answer
212 views

Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?

7 votes
0 answers
338 views

Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?

6 votes
1 answer
304 views

Approximation schemes for P-complete problems?

5 votes
0 answers
140 views

What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

4 votes
0 answers
100 views

What is the query and randomness complexity for very efficient PCPs?

4 votes
0 answers
185 views

Complexity of computing logarithm of a prime power

4 votes
1 answer
190 views

What do you call the join of two optimization problems?

3 votes
0 answers
126 views

What is the problem of finding a largest subset of smallest Kolmogorov complexity?

3 votes
0 answers
144 views

Looking for an "additive" binary graph operation that preserves subgraphs of high degree

1 vote
0 answers
226 views

Is $\mathsf{NP}$ in $\mathsf{NNC}^1$?