Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active Hot Week Month

0

votes

0

answers

73

views

Computational complexity of Private Computation

cc.complexity-theory cr.crypto-security

asked Jan 10 at 15:53 Michele Amoretti 190

9

votes

2

answers

755

views

Randomized algorithms not based on Schwartz-Zippel

cc.complexity-theory randomized-algorithms derandomization

modified Jan 4 at 13:05 Emil Jeřábek 14.1k

4

votes

0

answers

289

views

Computational Complexity of cycle double cover

cc.complexity-theory graph-theory graph-algorithms np-hardness

modified Jan 2 at 14:54 domotorp 13.5k

9

votes

1

answer

615

views

Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?

cc.complexity-theory fl.formal-languages automata-theory context-free logspace

modified Dec 31 '21 at 22:07 CommunityBot 1

23

votes

4

answers

1k

views

Monotone arithmetic circuits

cc.complexity-theory circuit-complexity boolean-functions monotone arithmetic-circuits

modified Dec 16 '21 at 10:32 Stasys 6,555

25

votes

1

answer

1k

views

Why is HAMILTONIAN CYCLE so different from PERMANENT?

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits

modified Dec 16 '21 at 10:11 Stasys 6,555

15

votes

1

answer

744

views

Is Dynamic Programming never weaker than Greedy?

cc.complexity-theory circuit-complexity lower-bounds dynamic-programming

modified Dec 16 '21 at 10:06 Stasys 6,555

23

votes

1

answer

2k

views

Tardos Function Counterexample to Blum's $P\neq NP$ Claim

cc.complexity-theory np-hardness complexity-classes

modified Dec 16 '21 at 10:01 Stasys 6,555

0

votes

0

answers

34

views

Query in the proof of greedy manipulation theorem (of a voting scheme)

cc.complexity-theory gt.game-theory

modified Dec 15 '21 at 8:30 Akash Agrawal 51

12

votes

2

answers

2k

views

Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

cc.complexity-theory complexity-classes counting-complexity open-problem oracles

modified Dec 14 '21 at 16:40 Casey Lacey Hadley 1

2

votes

1

answer

184

views

Minimum cut with size bounds $k\leq |S| \leq |V|-k$

cc.complexity-theory max-flow-min-cut max-cut

modified Dec 13 '21 at 17:07 CommunityBot 1

9

votes

2

answers

2k

views

Reducing #SAT to #MONOTONE-2SAT

cc.complexity-theory ds.algorithms complexity-classes sat

modified Dec 12 '21 at 17:27 daniel pehoushek 95

4

votes

1

answer

214

views

Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?

cc.complexity-theory computability

answered Dec 11 '21 at 8:13 Joshua Grochow 35k

1

vote

0

answers

48

views

Natural problems believed to be in EQP but not BPP

cc.complexity-theory

asked Dec 11 '21 at 7:14 Demi 476

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled