User Ryan Williams - Theoretical Computer Science Stack Exchange

Ryan Williams

Member for 13 years, 3 months
Last seen this week

Twitter
people.csail.mit.edu/rrw
Cambridge, MA, United States

159 Answers

Score Activity Newest

24 votes

Accepted

Is "Experimental Complexity Theory" being used to solve open problems?

answered Aug 24, 2010 at 21:30

24 votes

Accepted

Do all complexity classes have a leaf language characterization?

answered Aug 30, 2010 at 5:22

23 votes

Accepted

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

answered Nov 16, 2011 at 19:34

23 votes

(False?) proof for computability of a function?

answered Oct 6, 2010 at 22:17

23 votes

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

answered Oct 4, 2010 at 21:04

23 votes

When are two algorithms said to be "similar"?

answered Mar 6, 2012 at 7:18

22 votes

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

answered May 12, 2014 at 1:54

22 votes

Accepted

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

answered Jan 20, 2016 at 3:06

22 votes

Where and how did computers help prove a theorem?

answered Aug 19, 2010 at 3:29

21 votes

Open problems on the frontiers of TCS

answered Sep 13, 2010 at 17:33

21 votes

Accepted

Finding a 5-cycle in a sparse graph efficiently.

answered Dec 16, 2010 at 20:49

21 votes

Accepted

Paradigms for complexity analysis of algorithms

answered Jul 2, 2011 at 5:09

21 votes

What would be the consequences of PH=PSPACE?

answered Feb 22, 2014 at 9:14

21 votes

Complexity class associated with exhaustive search

answered Nov 21, 2012 at 19:31

20 votes

Accepted

Oblivious Turing Machine emulation lower bound

answered Mar 12, 2012 at 1:19

20 votes

Accepted

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

answered Mar 24, 2012 at 21:17

20 votes

How to compute powers of square matrices?

answered Apr 13, 2012 at 0:34

20 votes

Accepted

Hardness of approximation assuming NP != coNP

answered Oct 20, 2010 at 10:18

20 votes

Status of PP-completeness of MAJ3SAT

answered Jul 8, 2021 at 18:48

19 votes

What hierarchies and/or hierarchy theorems do you know?

answered Jul 10, 2011 at 22:03

19 votes

Problems outside of P that are not P-hard

answered Sep 1, 2011 at 9:19

19 votes

Optimal greedy algorithms for NP-hard problems

answered Sep 13, 2010 at 5:05

19 votes

Chernoff-type Inequality for pair-wise independent random variables

answered Sep 3, 2010 at 23:40

18 votes

Accepted

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

answered Sep 18, 2010 at 17:33

18 votes

Accepted

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

answered Sep 29, 2011 at 0:24

18 votes

Accepted

Computational Model in SETH

answered Dec 1, 2013 at 6:21

18 votes

Accepted

smallest circuit size using XOR gates

answered Aug 13, 2015 at 20:07

17 votes

Accepted

Potentially equal complexity classes without known contradictory relativizations

answered Nov 12, 2015 at 2:53

17 votes

Accepted

Additive combinatorics applications in algorithm design

answered Mar 12, 2015 at 0:33

17 votes

Accepted

Succinct Problems in $\mathsf{P}$

answered Mar 6, 2012 at 8:11

2