Network profile

sd234

Reputation

551

551
531
511

2018
2019
2020
2021

Top tag

approximation-algorithms

Next privilege

1,000 Rep.

See votes

Badges

2

8

Newest

Yearling

Next badge

0/1

Impact

0 posts edited

0 helpful flags

4 votes cast

7 Questions

Votes Activity Newest Views

1

9

votes

3

answers

902

views

Planted Clique in G(n,p), varying p

cc.complexity-theory approximation-algorithms approximation-hardness

May 1 '15 at 1:40 vzn 10.8k

1

6

votes

2

answers

471

views

Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

cc.complexity-theory counting-complexity

Jun 25 '16 at 22:26 Manos Orfanoudakis 1

1

6

votes

2

answers

625

views

Variants of Densest Subgraph Problems

graph-theory graph-algorithms approximation-algorithms approximation-hardness

Dec 27 '13 at 18:35 Sebastian Siebertz 1,106

6

votes

1

answer

406

views

In a random perfect matching of a regular bipartite graph, are all edges equally probable?

graph-theory co.combinatorics graph-algorithms randomness matching

Apr 30 '12 at 1:24 Kaveh 21k

1

4

votes

1

answer

191

views

Polynomial-time distinguishability threshold of planted clique

cc.complexity-theory ds.algorithms graph-algorithms approximation-algorithms clique

Mar 20 '14 at 0:29 Lev Reyzin♦ 11.5k

1

3

votes

1

answer

282

views

What is this matrix column-selection problem, and how hard is it to approximate?

approximation-algorithms linear-algebra matrices max-cut

Feb 8 '13 at 5:57 sd234 551

3

3

votes

1

answer

223

views

Agnostic Learning of K-Juntas over “small” distribution

reference-request machine-learning lg.learning boolean-functions

May 19 '12 at 1:38 Aaron Roth 9,690

Theoretical Computer Science Stack Exchange works best with JavaScript enabled