Ryan Williams

Cambridge, MA, United States

http://csail.mit.edu/~rrw/

algorithms/complexity extremist

top accounts reputation activity subscriptions

What papers should everyone read?

big-list soft-question asked Sep 12, 2010 at 0:43

cstheory.stackexchange.com

113 votes

Solid applications of category theory in TCS?

pl.programming-languages lo.logic ct.category-theory asked Sep 4, 2010 at 9:20

cstheory.stackexchange.com

70 votes

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

cc.complexity-theory lo.logic pl.programming-languages big-picture set-theory asked Oct 4, 2010 at 21:38

cstheory.stackexchange.com

42 votes

A fixed-depth characterization of $TC^0$? $NC^1$?

cc.complexity-theory circuit-complexity upper-bounds asked Oct 21, 2010 at 1:18

cstheory.stackexchange.com

30 votes

Is there an oracle such that SAT is not infinitely often in sub-exponential time?

cc.complexity-theory sat oracles asked Feb 23, 2015 at 22:59

cstheory.stackexchange.com

21 votes

Satisfiability of general Boolean formulas with at most two occurrences per variable

computer-science np algorithms lo.logic computational-complexity asked Dec 21, 2009 at 22:29

mathoverflow.net

9 votes

A generalization of Boolean matrix multiplication for order-3 tensors

linear-algebra graph-theory co.combinatorics tensor hypergraph asked Jan 23, 2010 at 21:32

mathoverflow.net

8 votes

Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$

circuit-complexity oracles alternation asked Oct 1, 2016 at 6:07

cstheory.stackexchange.com

Top Answers

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

cstheory.stackexchange.com

Can a mathematical definition be wrong?

mathoverflow.net

What papers should everyone read?

cstheory.stackexchange.com

Too old for advanced mathematics?

mathoverflow.net

How do you get a "Physical Intuition" for results in TCS?

cstheory.stackexchange.com

What are the best current lower bounds on 3SAT?

cstheory.stackexchange.com

Inspirational talk for final year high school pupils

cstheory.stackexchange.com

Problems that can be used to show polynomial-time hardness results

cstheory.stackexchange.com

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

cstheory.stackexchange.com

Matrix multiplication in $O(n^2 \log n)$

cstheory.stackexchange.com

Is $AC^0/poly \cap NP$ contained in $P$?

cstheory.stackexchange.com

Space complexity of Coppersmith–Winograd algorithm

cstheory.stackexchange.com

Is there any justification to believe that $NL\neq L$?

cstheory.stackexchange.com

Lower bounds on #SAT?

cstheory.stackexchange.com

True Bit Complexity of matrix multiplication is $O(n^{4})$

cstheory.stackexchange.com

Super-polynomial time approximation algorithms for MAX 3SAT

cstheory.stackexchange.com

All pairs shortest path in undirected and unweighted graphs

math.stackexchange.com

Is there any book on the philosophical implications of Theoretical Computer Science?

cstheory.stackexchange.com

Examples of the price of abstraction?

cstheory.stackexchange.com

How many tautologies are there?

cstheory.stackexchange.com

Super-linear time complexity lower bounds for any natural problem in NP?

mathoverflow.net

Semantic vs. Syntactic Complexity Classes

cstheory.stackexchange.com

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

cstheory.stackexchange.com

NC = P consequences?

cstheory.stackexchange.com

What is $\mathsf{NP}$ restricted to linear size witnesses?

cstheory.stackexchange.com

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

cstheory.stackexchange.com

What is the big version of NC?

cstheory.stackexchange.com

Finding a cycle of fixed length

mathoverflow.net

Is there a complexity theory analogue of Rice's theorem in computability theory?

cstheory.stackexchange.com

Toy examples for barriers to $P \ne NP$

cstheory.stackexchange.com