Joshua Grochow's user avatar
Joshua Grochow's user avatar
Joshua Grochow's user avatar
Joshua Grochow
  • Member for 12 years, 1 month
  • Last seen this week
5 votes
Accepted

Is there a definitive reference for Turing machines with multiple oracle tapes?

4 votes
Accepted

Is any computational complexity question solved by injury priority method except Post problem?

9 votes

Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

10 votes
Accepted

Are there survey papers in theoretical computer science?

7 votes
Accepted

Are there 'poision-pill' research questions in TCS?

1 vote
Accepted

Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)

3 votes

Do there exists reversible gate sets of intermediate growth?

2 votes

Applications of association schemes to complexity theory and other TCS

10 votes
Accepted

Generating Graphs with Trivial Automorphisms

2 votes

Complexity of Polynomial Division

4 votes
Accepted

Is Permanent $+$-reducible?

6 votes
Accepted

FOCS virtual fee $600

8 votes
Accepted

Randomized algorithms not based on Schwartz-Zippel

4 votes

Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?

6 votes

similar matrices

19 votes
Accepted

Natural candidates for the hierarchy inside NPI

12 votes
Accepted

Is it right to ask a TCS researcher about the real life application of the problem she/he is working on?

3 votes

complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

3 votes

Relationship between Random Graph Theory and TCS

3 votes
Accepted

Recursive generic oracles

6 votes
Accepted

Proving not NP-complete by non-existence of gadget

3 votes
Accepted

Questions about P vs NP and geometric complexity theory

4 votes

Examples of collapsing hierarchies

5 votes
Accepted

Is $GCT$ necessarily a negative result program?

2 votes
Accepted

Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$?

22 votes

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

5 votes

What do we know about provably correct programs?

4 votes

What is the meaning of 'uniform' in Blum's paper "On the Size of Machines"

13 votes

Is Descriptive Complexity dead?

8 votes
Accepted

Is solving the following system of boolean equations NP-hard?

1
2 3 4 5
13