User Dana Moshkovitz - Theoretical Computer Science Stack Exchange

Dana Moshkovitz

Member for 13 years, 6 months
Last seen more than 8 years ago

people.csail.mit.edu/dmoshkov
Cambridge, MA

16 Questions

Score Activity Newest Views

29 votes

1 answer

1k views

Finding a biased coin using a few coin tosses

asked Jun 22, 2015 at 21:29

15 votes

2 answers

1k views

Which randomized algorithms have exponentially small error probability?

asked Jun 11, 2015 at 0:56

6 votes

1 answer

273 views

Split find-min data structure that finds several small elements?

asked May 24, 2015 at 14:46

41 votes

7 answers

5k views

When does randomization speed up algorithms and it "shouldn't"?

asked Apr 19, 2015 at 20:02

8 votes

0 answers

314 views

Are there sparsifiers that approximate vertices rather than edges?

asked Mar 29, 2015 at 23:15

11 votes

2 answers

690 views

Fun with inverse Ackermann

asked Mar 21, 2015 at 18:35

4 votes

0 answers

97 views

Thresholds for overlapping sets

asked Mar 18, 2015 at 18:10

25 votes

1 answer

822 views

Regularity Lemma for Sparse Graphs

asked Dec 22, 2012 at 22:20

17 votes

1 answer

856 views

Who introduced the complexity class AC?

asked Sep 19, 2012 at 1:19

16 votes

0 answers

371 views

Looking for an operator on polynomials

asked Mar 28, 2012 at 15:17

23 votes

3 answers

893 views

From Extractors to Pseudorandom Generators?

asked Sep 10, 2011 at 18:52

22 votes

1 answer

342 views

Belief propagation for approximate real 3LIN?

asked Jul 9, 2011 at 18:29

41 votes

12 answers

3k views

Gröbner bases in TCS?

asked May 12, 2011 at 1:13

39 votes

3 answers

2k views

Why are mod_m gates interesting?

asked Nov 9, 2010 at 12:46

61 votes

14 answers

4k views

Information Theory used to prove neat combinatorial statements?

asked Nov 3, 2010 at 1:43

27 votes

2 answers

2k views

Why are Ramanujan graphs named after Ramanujan?

asked Oct 19, 2010 at 20:28