user avatar
user avatar
user avatar
D.W.
  • Member for 11 years, 3 months
  • Last seen this week
18 votes
0 answers
1k views

Lower bounds on single-source shortest paths in directed graphs

14 votes
3 answers
1k views

Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

11 votes
1 answer
172 views

Detecting circuit that's similar in functionality and implementation

11 votes
1 answer
358 views

Evaluating symmetric polynomials

10 votes
1 answer
353 views

Evaluate boolean circuit on batch of similar inputs

9 votes
0 answers
289 views

Approximating a convex polyhedron, with fewer inequalities

8 votes
2 answers
503 views

Streaming algorithms suitable for undergrad course

7 votes
0 answers
119 views

Learning function with a few low-order Fourier coefficients, from uniformly random samples

7 votes
0 answers
203 views

Generalization of SAT, where we replace OR with another symmetric function

7 votes
1 answer
878 views

Discrete log in GL(2,p)

5 votes
1 answer
2k views

Implementation that solves minimum set cover

5 votes
0 answers
197 views

Exploring a DFA, with no feedback

5 votes
1 answer
119 views

Commitment schemes with verification in NC0

4 votes
1 answer
370 views

Approximate-#SAT solver

4 votes
0 answers
155 views

Find index set partition that has large projections

3 votes
3 answers
438 views

Pairwise comparison of bit vectors

3 votes
0 answers
87 views

Estimate smooth vector, from dot-product queries

3 votes
1 answer
158 views

Binary search on coin heads probability

2 votes
0 answers
196 views

Oracle for Hamming distance to a secret bitvector

2 votes
2 answers
300 views

Sketches, using ideal hash functions

2 votes
0 answers
99 views

Optimal additive basis for decomposing/partitioning an integer as a sum of two integers