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

8 votes

Accepted

Relation between ACC^0 and DTIME

answered Oct 31 at 16:21

11 votes

Accepted

Law of the Excluded Middle in complexity theory

answered Sep 12 at 2:18

8 votes

Accepted

Complexity of permanent verification

answered Jul 3 at 15:46

13 votes

What is the general consensus on the NL vs P question?

answered Jun 9 at 17:00

12 votes

SC^2 algorithms for st-connectivity

answered Sep 25, 2010 at 20:05

28 votes

Accepted

NTIME(n^k) ≠ DTIME(n^k) ?

answered Sep 8, 2010 at 17:41

5 votes

Classes between PH and PSPACE

answered Sep 17, 2022 at 3:24

8 votes

Accepted

Randomized communication complexity of or-of-equalities

answered Aug 11, 2022 at 14:57

7 votes

Accepted

Quadratic lower bound

answered Jun 30, 2022 at 20:55

11 votes

Lower-bounds under SETH

answered Jun 7, 2022 at 0:38

1 vote

Growth rate of Knapsack Solutions

answered Apr 22, 2022 at 14:18

5 votes

Circuit uniformities more restrictive than $DLOGTIME$

answered Jan 18, 2022 at 19:04

20 votes

Status of PP-completeness of MAJ3SAT

answered Jul 8, 2021 at 18:48

3 votes

Accepted

Finding output with unique witness in matrix multiplication

answered May 17, 2021 at 16:46

1 vote

Name of this graph partitioning problem? (related to coloring)

answered Feb 28, 2021 at 21:26

7 votes

Are there analogous works to PPSZ algorithm for #P?

answered Feb 19, 2021 at 14:31

8 votes

Accepted

It is known that $L \subsetneq PH$?

answered Feb 19, 2021 at 14:16

31 votes

Accepted

Lower bounds on #SAT?

answered Sep 7, 2010 at 16:36

2 votes

Accepted

Comparing SAT to MCSP reduction class separations and faster SAT class separations?

answered Feb 12, 2021 at 14:27

7 votes

$⊕P$-completeness of $⊕2SAT$

answered Jan 27, 2021 at 22:53

6 votes

Accepted

Quantum complexity of TQBF

answered Jan 27, 2021 at 2:40

3 votes

Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings

answered Jan 1, 2021 at 21:43

11 votes

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

answered Nov 9, 2020 at 1:48

6 votes

Most general setting for fine-grained exponential-time complexity classes?

answered Jul 2, 2020 at 22:26

8 votes

Accepted

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

answered May 3, 2020 at 23:24

11 votes

Accepted

Complexity class of efficient streaming algorithms

answered Apr 24, 2020 at 22:38

11 votes

Accepted

If NP in BPP then NP equals RP

answered Dec 22, 2019 at 20:40

14 votes

Accepted

Complexity of k-clique for hypergraphs

answered Aug 12, 2015 at 7:12

10 votes

Bootstrapping results that really bootstrap

answered Jul 9, 2019 at 6:01

16 votes

Accepted

An obstruction like ETH

answered Apr 29, 2019 at 20:37

1