Skip to main content
The 2024 Developer Survey results are live! See the results
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams
  • Member for 13 years, 11 months
  • Last seen this week
24 votes
Accepted

Do all complexity classes have a leaf language characterization?

24 votes
Accepted

Hierarchy for BPP vs derandomization

23 votes
Accepted

What are the consequences of $L = \oplus L$?

23 votes

(False?) proof for computability of a function?

23 votes

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

23 votes

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

23 votes

When are two algorithms said to be "similar"?

22 votes

What would be the consequences of $\mathsf{PH=PSPACE}$?

22 votes
Accepted

How is the MA version of SETH proven to be false?

22 votes

Where and how did computers help prove a theorem?

21 votes

Open problems on the frontiers of TCS

21 votes
Accepted

Finding a 5-cycle in a sparse graph efficiently.

21 votes
Accepted

Paradigms for complexity analysis of algorithms

21 votes
Accepted

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

21 votes

Complexity class associated with exhaustive search

20 votes

How to compute powers of square matrices?

20 votes
Accepted

Oblivious Turing Machine emulation lower bound

20 votes

What hierarchies and/or hierarchy theorems do you know?

20 votes
Accepted

Hardness of approximation assuming NP != coNP

20 votes

Status of PP-completeness of MAJ3SAT

19 votes

Problems outside of P that are not P-hard

19 votes

Optimal greedy algorithms for NP-hard problems

19 votes

Chernoff-type Inequality for pair-wise independent random variables

18 votes
Accepted

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

18 votes
Accepted

Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem

18 votes
Accepted

Computational Model in SETH

18 votes
Accepted

smallest circuit size using XOR gates

17 votes
Accepted

Potentially equal complexity classes without known contradictory relativizations

17 votes
Accepted

Additive combinatorics applications in algorithm design

17 votes
Accepted

Succinct Problems in $\mathsf{P}$