Profile Activity

Covvar

Meta user

Network profile

Reputation

295

Top tag

complexity-theory

Next privilege

300 Rep.

Create new tags

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

429

views

Why is CVAL a P-Complete problem?

Jul 11 '17 at 10:41 Covvar 295

votes

answer

167

views

$UCYCLE$ is in $L$

algorithms complexity-theory space-complexity

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

votes

answer

110

views

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

time-complexity complexity-classes

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

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

votes

answers

409

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,752

votes

answer

223

views

proving $IP^\star = NP$

complexity-theory probabilistic-algorithms interactive-proof-systems

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

votes

answer

517

views

Prove that $BPP^{BPP} = BPP$

complexity-theory

Jun 2 '17 at 1:56 tc1729 136

votes

answer

218

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

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

vote

answer

522

views

reducing $CLIQUE$ from decision to search problem

algorithms time-complexity polynomial-time clique

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

vote

answer

views

Why is the language $NP-hard$?

complexity-theory reductions np-hard

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

vote

answer

views

Showing a problem is $P$-complete

complexity-theory reductions

Jul 19 '17 at 19:54 Ariel 10.8k

vote

answer

views

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

complexity-theory

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

vote

answer

164

views

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

complexity-theory

Jul 18 '17 at 13:06 Ariel 10.8k

vote

answer

views

Randomized algorithm for 2kCNF satisfiability problem

algorithms satisfiability randomized-algorithms random-walks

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

votes

answer

views

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

complexity-theory

Jul 13 '17 at 10:26 Ariel 10.8k

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$?