Profile Activity

Covvar

Meta user

Network profile

Reputation

465

Top tag

complexity-theory

Next privilege

500 Rep.

Access review queues

Badges

Newest

Yearling

Next badge

0/1

Impact

0 posts edited

0 helpful flags

53 votes cast

Summary Answers Questions Tags Badges Favorites Bounties Reputation All actions

17 Questions

Views Newest Activity Votes

votes

answer

506

views

Why is CVAL a P-Complete problem?

Jul 11 '17 at 10:41 Covvar 465

votes

answer

269

views

$UCYCLE$ is in $L$

algorithms complexity-theory space-complexity

Sep 12 '17 at 14:18 Yuval Filmus 217k

votes

answer

119

views

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

time-complexity complexity-classes

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

votes

answer

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 217k

votes

answers

438

views

Why do we need Gibbs sampling (and MCMC)?

algorithms randomness sampling markov-chains

Aug 12 '17 at 22:22 eyeApps LLC 146

votes

answer

views

What problems are believed to have an efficient algorithm?

algorithms efficiency research

Jul 22 '17 at 12:54 Lieuwe Vinkhuijzen 3,922

votes

answer

290

views

proving $IP^\star = NP$

complexity-theory probabilistic-algorithms interactive-proof-systems

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

votes

answer

710

views

Prove that $BPP^{BPP} = BPP$

complexity-theory

Jun 2 '17 at 1:56 tc1729 136

votes

answer

228

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 217k

vote

answer

views

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

complexity-theory

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

vote

answer

633

views

reducing $CLIQUE$ from decision to search problem

algorithms time-complexity polynomial-time clique

Sep 16 '17 at 14:17 Yuval Filmus 217k

vote

answer

views

Why is the language $NP-hard$?

complexity-theory reductions np-hard

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

vote

answer

views

Showing a problem is $P$-complete

complexity-theory reductions

Jul 19 '17 at 19:54 Ariel 11k

vote

answer

views

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

complexity-theory

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

vote

answer

172

views

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

complexity-theory

Jul 18 '17 at 13:06 Ariel 11k

vote

answer

views

Randomized algorithm for 2kCNF satisfiability problem

algorithms satisfiability randomized-algorithms random-walks

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

votes

answer

108

views

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

complexity-theory

Jul 13 '17 at 10:26 Ariel 11k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

17 Questions

Why is CVAL a P-Complete problem?

$UCYCLE$ is in $L$

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

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

Why do we need Gibbs sampling (and MCMC)?

What problems are believed to have an efficient algorithm?

proving $IP^\star = NP$

Prove that $BPP^{BPP} = BPP$

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

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

reducing $CLIQUE$ from decision to search problem

Why is the language $NP-hard$?

Showing a problem is $P$-complete

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

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

Randomized algorithm for 2kCNF satisfiability problem

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