18,098 reputation
569131
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 11 months
seen 16 hours ago

algorithms/complexity extremist


Feb
9
comment An oracle relative to which EXP(NP) = BPP
Yes, there are oracles making them equal and oracles making them different, if I recall. Lance Fortnow knows the reference... I can try to look it up myself, but if you do a search on sciencedirect for it, you're likely to see it.
Jan
17
comment Graph with minimum number of edges having given sets of nodes as its paths
Why not just make a clique over all the nodes? That will support any set of paths you want
Jan
15
comment Deciding emptiness of intersection of regular languages in subquadratic time
So for example (based on Michael's comment), the strong exponential time hypothesis implies that the exponent should be 2. I think this could also proved to follow from the exponential time hypothesis...
Jan
7
awarded  Enlightened
Jan
7
awarded  Nice Answer
Nov
23
awarded  Good Answer
Nov
17
revised $NP$-complete problem with quasi-polynomial bound on the number of solutions
added 140 characters in body
Nov
15
comment Practically Good Algorithms of a Very Low Computational Complexity Class
Here's an optimization example... maybe. MAX-LIN: given a large (inconsistent) system of linear equations over GF(2), find a solution that maximizes the number of equations satisfied. This problem cannot be approximated with a factor larger than 1/2 unless P=NP, hence even approximately solving is very difficult. Nevertheless, it seems a 1/2-approximation (which is apparently the best possible) can be computed in TC0: a random assignment works, so we can choose poly(n) assignments (hard-coded) and evaluate the linear system on each one, outputting the best. Maybe I'm missing your point.
Nov
15
answered $NP$-complete problem with quasi-polynomial bound on the number of solutions
Nov
1
awarded  Good Answer
Oct
30
answered Pseudorandom generators indistinguishable by uniform deterministic adversaries
Oct
27
awarded  Nice Answer
Oct
26
comment Natural NP-complete problems with “large” witnesses
Actually, the witness size for Graph Isomorphism and Hamiltonian Path could be seen as sublinear in the input (given that the input is the $n \times n$ adjacency matrix of the graph).
Sep
30
awarded  Explainer
Sep
24
awarded  Autobiographer
Aug
30
comment Finding similar vectors in subquadratic time
Do you work for twitter?blog.twitter.com/2014/all-pairs-similarity-via-dimsum Seriously, even detecting if there is an edge in this graph (I.e. that it's not an independent set of vertices) is going to be very hard to do faster than $O(n^2)$ for an arbitrary similarity function.
Aug
29
comment Large classes which contain LOGSPACE for which strict inclusions are unknown
Yeah, I know about that one too, and other references as well. But I kept to a summary answer that wouldn't take more than 10 minutes to write.
Aug
28
answered Large classes which contain LOGSPACE for which strict inclusions are unknown
Aug
23
awarded  Nice Answer
Aug
22
answered MAX 1 in 2 SAT Algorithm