Skip to main content
argentpepper's user avatar
argentpepper's user avatar
argentpepper's user avatar
argentpepper
  • Member for 13 years, 3 months
  • Last seen more than 1 year ago
49 votes
4 answers
2k views

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

25 votes
1 answer
800 views

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

20 votes
0 answers
486 views

Interesting PCP characterization of classes smaller than P?

12 votes
1 answer
187 views

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

11 votes
1 answer
1k views

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

10 votes
1 answer
216 views

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

7 votes
0 answers
348 views

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

6 votes
1 answer
313 views

Approximation schemes for P-complete problems?

5 votes
0 answers
149 views

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

4 votes
0 answers
104 views

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

4 votes
0 answers
187 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
130 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
227 views

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