Network profile

Covvar

Reputation

495

495
480
465

Apr
Jul
Oct
Jan

Next privilege

500 Rep.

Access review queues

Badges

2

7

Newest

Yearling

Next badge

0/1

Impact

0 posts edited

0 helpful flags

53 votes cast

17 Questions

Votes Activity Newest Views

1

5

votes

1

answer

465

views

$UCYCLE$ is in $L$

algorithms complexity-theory space-complexity

Apr 12 at 11:36 Community♦ 1

1

5

votes

1

answer

649

views

Why is CVAL a P-Complete problem?

complexity-theory reductions space-complexity

Jul 11 '17 at 10:41 Covvar 495

1

3

votes

1

answer

988

views

Prove that $BPP^{BPP} = BPP$

complexity-theory

Jun 2 '17 at 1:56 tc1729 136

3

votes

1

answer

177

views

Prove that $NP^{NP\cap co-NP} = NP$

time-complexity complexity-classes

May 28 '17 at 13:45 Yuval Filmus 241k

2

votes

2

answers

875

views

reducing $CLIQUE$ from decision to search problem

algorithms time-complexity polynomial-time clique

Oct 19 at 13:01 Flowi 1

2

votes

1

answer

31

views

Why $\operatorname{gap-A}[1.5a, 1.5b + 1/4]$ has an efficient solution?

complexity-theory approximation

Sep 18 '17 at 11:06 Yuval Filmus 241k

1

2

votes

3

answers

474

views

Why do we need Gibbs sampling (and MCMC)?

algorithms randomness sampling markov-chains

Aug 12 '17 at 22:22 eyeApps LLC 146

1

2

votes

1

answer

79

views

What problems are believed to have an efficient algorithm?

algorithms efficiency research

Jul 22 '17 at 12:54 Lieuwe Vinkhuijzen 4,047

2

votes

1

answer

421

views

proving $IP^\star = NP$

complexity-theory probabilistic-algorithms interactive-proof-systems

Jul 13 '17 at 15:56 Yuval Filmus 241k

1

2

votes

1

answer

239

views

detecting a cycle in an undirected graph problem is in $RL$ complexity class

complexity-theory graphs randomized-algorithms

May 27 '17 at 15:23 Yuval Filmus 241k

1

vote

1

answer

38

views

$C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?

complexity-theory

Sep 18 '17 at 13:52 Yuval Filmus 241k

1

vote

1

answer

40

views

Why is the language $NP-hard$?

complexity-theory reductions np-hard

Sep 10 '17 at 13:23 Yuval Filmus 241k

1

1

vote

1

answer

70

views

Showing a problem is $P$-complete

complexity-theory reductions

Jul 19 '17 at 19:54 Ariel 11.9k

1

vote

1

answer

62

views

if $L\in BPP$ then $NP\subseteq BPP$

complexity-theory

Jul 19 '17 at 12:24 Yuval Filmus 241k

1

vote

1

answer

182

views

$P\ne BPP$ implies $P\ne NP$

complexity-theory

Jul 18 '17 at 13:06 Ariel 11.9k

1

vote

1

answer

45

views

Randomized algorithm for 2kCNF satisfiability problem

algorithms satisfiability randomized-algorithms random-walks

Jun 5 '17 at 11:35 Yuval Filmus 241k

0

votes

1

answer

119

views

If we can simulate $NP$-machines why isn't it trivial that $NP=coNP$?

complexity-theory

Jul 13 '17 at 10:26 Ariel 11.9k

Computer Science Stack Exchange works best with JavaScript enabled