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

9 votes

Accepted

Space alternating hierarchy

answered Aug 24, 2010 at 23:53

9 votes

Lower bounds on Gaussian complexity

answered Aug 18, 2010 at 21:36

8 votes

What tools do you use to write papers?

answered Oct 18, 2010 at 6:31

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

8 votes

Quantified Boolean Formulas with logarithmic alternations

answered Feb 24, 2017 at 23:21

8 votes

Accepted

How powerful is $ACC^0$ circuit class in average case?

answered Jan 3, 2017 at 4:12

8 votes

Large classes which contain LOGSPACE for which strict inclusions are unknown

answered Aug 28, 2014 at 22:32

8 votes

Accepted

Randomized communication complexity of or-of-equalities

answered Aug 11, 2022 at 14:57

8 votes

Accepted

It is known that $L \subsetneq PH$?

answered Feb 19, 2021 at 14:16

8 votes

Accepted

Relation between ACC^0 and DTIME

answered Oct 31 at 16:21

8 votes

Accepted

Complexity of permanent verification

answered Jul 3 at 15:46

7 votes

Are there analogous works to PPSZ algorithm for #P?

answered Feb 19, 2021 at 14:31

7 votes

Accepted

Quadratic lower bound

answered Jun 30, 2022 at 20:55

7 votes

Accepted

Pseudorandom generators indistinguishable by uniform deterministic adversaries

answered Oct 30, 2014 at 17:26

7 votes

Accepted

Boolean Circuit in a Black Box?

answered May 17, 2012 at 5:53

7 votes

Pairwise comparison of bit vectors

answered Jan 21, 2017 at 17:04

7 votes

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

answered Jan 27, 2021 at 22:53

7 votes

Accepted

Applications of MCTS/UCT

answered Feb 27, 2011 at 5:06

7 votes

Is this problem mappable to 3SAT or is it weaker than 3SAT?

answered Sep 10, 2010 at 18:31

7 votes

Accepted

Circuit complexity and statistical tests

answered Sep 20, 2010 at 16:29

6 votes

Accepted

Quantum complexity of TQBF

answered Jan 27, 2021 at 2:40

6 votes

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

answered Jul 2, 2020 at 22:26

6 votes

Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

answered Aug 8, 2016 at 11:21

6 votes

Accepted

What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

answered Aug 11, 2015 at 17:37

6 votes

Funny TCS-related papers etc?

answered Feb 29, 2012 at 2:10

6 votes

Exponential gap on neural network layers

answered Apr 17, 2014 at 2:55

5 votes

Accepted

Is parametrized maximum independent clauses problem in FPT?

answered Sep 4, 2010 at 16:58

5 votes

Accepted

Is there such a thing as control logic complexity classes?

answered Nov 27, 2010 at 20:58

5 votes

Classes between PH and PSPACE

answered Sep 17, 2022 at 3:24

5 votes

Circuit uniformities more restrictive than $DLOGTIME$

answered Jan 18, 2022 at 19:04

5