17,988 reputation
569130
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 9 months
seen yesterday

algorithms/complexity extremist


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
Aug
17
awarded  Yearling
Aug
3
reviewed Close What can we say about all cycles in graphs (connected undirected graph)