Ryan Williams

13,707 reputation

355103

bio	website	stanford.edu/~rrwill
	location	California
	age
visits	member for	2 years, 9 months
	seen	yesterday
stats	profile views	3,074

algorithms/complexity extremist

	13,707 reputation	bio	website	stanford.edu/~rrwill	visits	member for	2 years, 9 months
355103 badges		location	California		seen	yesterday

summary answers questions tags badges favorites bounties reputation activity

486 Actions

suggestions reviews revisions comments badges posts accepts all

Feb 25	awarded	Enlightened
Feb 25	awarded	Nice Answer
Feb 21	comment	Assignment problem with sum replaced by max It's also called the bottleneck assignment problem
Jan 14	comment	Are quasi-polynomial sized circuits for 3-SAT trivial? @ZiruiWang: Look up $BPP \subset P/poly$. Suppose the data structure answers queries correctly with probability $3/4$. Take $100n$ copies of the data structure of size $2^{O(\log^2 n)}$ each seeded with different strings of random bits. Take the majority answer of all the copies. This is a quasipolynomial time randomized algorithm with error less than $1/2^n$. This can be converted to a quasipolynomial size circuit by hardcoding an appropriate seed.
Jan 10	awarded	Announcer
Jan 10	awarded	Enlightened
Jan 10	awarded	Nice Answer
Jan 7	comment	Are quasi-polynomial sized circuits for 3-SAT trivial? How can the algorithm not be randomized, yet you can run it repeatedly to reduce error? I think that you would probably have to give at least a few more details, in order to understand your question.
Jan 7	comment	Best Upper Bounds on SAT Yet another update: in FOCS 2011, Timon Hertli (arxiv.org/abs/1103.2165) proved that the PPSZ algorithm solves every 3SAT instance in $1.308^n$ time.
Jan 7	answered	Are quasi-polynomial sized circuits for 3-SAT trivial?
Dec 19	awarded	Good Answer
Dec 15	awarded	Enlightened
Dec 15	awarded	Good Answer
Dec 9	revised	Super-polynomial time approximation algorithms for MAX 3SAT added 416 characters in body
Dec 9	awarded	Nice Answer
Dec 8	answered	Super-polynomial time approximation algorithms for MAX 3SAT
Dec 3	comment	Consequences of sub-exponential proofs/algorithms for SAT Sorry Artem, my answer wouldn't be much cooler than yours... I guess one thing to add would be that ETH is false implies new superlinear circuit lower bounds (same paper).
Dec 3	comment	Number of binary gates needed to compute AND and OR of n input bits simultaneously Note in Sasha's question, all 2-bit Boolean functions can be used to construct the circuit.
Dec 2	comment	SERF-reducibility and subexponential algorithms Just a note: there are some other conditions that need to be assumed for their proof to work. For one, $f$ must be efficiently computable. Secondly, there must be a single uniform algorithm $A$ which achieves $2^{\delta f(k)}$ for each $\delta$ (think of $\delta$ as another input to $A$). It is entirely possible that without these conditions, a problem can satisfy (1) but not (2).
Nov 30	comment	Number of binary gates needed to compute AND and OR of n input bits simultaneously @Sasha, have you tried applying SAT solvers to small examples (like $n=4$), as in some of your earlier papers?