As of May 31, 2023, we have updated our Code of Conduct.
Theoretical Computer Science
argentpepper's user avatar
argentpepper's user avatar
argentpepper's user avatar
argentpepper
  • Member for 12 years, 2 months
  • Last seen more than a month ago
Profile Activity

15 Questions

Score Activity Newest Views
49 votes
4 answers
2k views

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

25 votes
1 answer
762 views

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

20 votes
0 answers
468 views

Interesting PCP characterization of classes smaller than P?

12 votes
1 answer
185 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
213 views

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

7 votes
0 answers
344 views

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

6 votes
1 answer
312 views

Approximation schemes for P-complete problems?

5 votes
0 answers
142 views

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

4 votes
0 answers
101 views

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

4 votes
0 answers
186 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
129 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$?

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.