Theoretical Computer Science

21

votes

0

answers

248

views

more on PH in PP?

1h ago Noam 3,662

12

votes

1

answer

207

views

A category of NP-complete problems?

cc.complexity-theory np-hardness ct.category-theory

3h ago wren ng thornton 219

0

votes

0

answers

15

views

Survey Article on the Theory of Recursive Functions?

reference-request computability

3h ago Suresh Venkat♦ 5,851

3

votes

3

answers

133

views

Field extensions in CS

big-list algebra fields

4h ago arnab 2,405

2

votes

1

answer

36

views

Are variables in RHS of Chomsky Normal Form productions distinct?

automata-theory fl.formal-languages grammars

7h ago Shiva Kintali 1,995

3

votes

1

answer

58

views

Dominations under oracles which is closed under complement?

cc.complexity-theory complexity-classes oracle

7h ago John Watrous 921

3

votes

2

answers

109

views

Is there such a thing as control logic complexity classes?

cc.complexity-theory complexity-classes

12h ago Ryan Williams♦ 4,279

2

votes

1

answer

172

views

An Interactive Proof of God's Number?

proofs puzzles interactive-proofs

14h ago Kaveh 2,513

0

votes

0

answers

107

views

Very interested about property testing, but how long it will go

reference-request machine-learning lg.learning property-testing

14h ago Kaveh 2,513

-1

votes

1

answer

116

views

Reduction Algorithms

cc.complexity-theory np-hardness reductions

14h ago Kaveh 2,513

-1

votes

0

answers

70

views

np completeness [closed]

cc.complexity-theory np-hardness

14h ago Kaveh 2,513

8

votes

0

answers

105

views

Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

cc.complexity-theory lower-bounds circuit-complexity boolean-functions fourier

14h ago Kaveh 2,513

1

vote

1

answer

153

views

Matrix multiplication in $O(n^2 \log n)$

ds.algorithms linear-algebra matrix-product

15h ago Ryan Williams♦ 4,279

4

votes

2

answers

90

views

Communication lower bounds for partial boolean functions

cc.complexity-theory lower-bounds communication-complexity boolean-functions

20h ago Joshua Brody 101

4

votes

5

answers

344

views

Do many-one reductions and Turing reductions define the same class NPC

cc.complexity-theory np-hardness reductions

21h ago Peter Shor 1,883

18

votes

3

answers

461

views

Is $PH \subseteq PP$?

cc.complexity-theory counting-complexity

1d ago Huck Bennett 144

4

votes

2

answers

106

views

Graph classes in which CLIQUE is known to be NP-hard?

reference-request np-hardness clique

1d ago David Eppstein 3,598

-1

votes

0

answers

101

views

Is there a known alogrithm for the following problem

puzzles

1d ago MyM 6

0

votes

0

answers

36

views

Is anyone actively researching distributed prediction models?

reference-request dc.distributed-comp

1d ago Suresh Venkat♦ 5,851

2

votes

1

answer

83

views

NP-Complete Hard-on-Average Problems

cc.complexity-theory np-hardness cr.crypto-security

1d ago Boaz Barak 1,536

5

votes

4

answers

351

views

Is this game solvable?

gt.game-theory

1d ago whuber 221

0

votes

0

answers

34

views

Is the Selflet system used for any active research?

dc.distributed-comp

1d ago blueberryfields 101

7

votes

2

answers

127

views

Is the backup problem NP-complete?

cc.complexity-theory np-hardness graph-algorithms

1d ago Shiva Kintali 1,995

2

votes

0

answers

130

views

Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions? [closed]

cc.complexity-theory open-problem reductions

1d ago Peter Shor 1,883

17

votes

10

answers

793

views

What Books Should Everyone Read?

soft-question big-list

1d ago Sadeq Dousti 4,748

4

votes

3

answers

118

views

Tree decomposition for planar graphs

graph-theory graph-algorithms treewidth

1d ago Jason Morton 131

8

votes

1

answer

129

views

PCP Theorem - Alphabet Reduction Step

cc.complexity-theory pcp

1d ago Boaz Barak 1,536

0

votes

1

answer

135

views

Subexponential hardness assumption

cc.complexity-theory cr.crypto-security

1d ago Sadeq Dousti 4,748

3

votes

2

answers

123

views

Counting length-k increasing subsequences in a permutation

ds.algorithms permutations

1d ago Anthony Labarre 430

6

votes

1

answer

112

views

Number of mincuts of a graph without using Karger's algorithm

graph-theory co.combinatorics max-flow-min-cut

2d ago Suresh Venkat♦ 5,851

8

votes

11

answers

1

kviews

Are there any counterintuitive results in theoretical computer science?

big-list

2d ago Akash Kumar 184

12

votes

1

answer

224

views

Completeness and Context-Sensitive Languages.

np-hardness fl.formal-languages

2d ago Hermann Gruber 146

5

votes

1

answer

143

views

Status of Cerny Conjecture?

fl.formal-languages automata

2d ago Hermann Gruber 146

4

votes

1

answer

94

views

What is the optimal data structure for a tree of maps.

ds.data-structures tree hash-function

2d ago Jelani Nelson 151

0

votes

1

answer

92

views

What's the difference between an invariant and an “inductive” invariant?

pl.programming-lang program-verification

2d ago Jukka Suomela 2,413

13

votes

5

answers

381

views

Proving lower bounds by proving upper bounds

cc.complexity-theory lower-bounds

2d ago turkistany 1,882

9

votes

5

answers

236

views

NEXP-complete problems

cc.complexity-theory complexity-classes big-list nexp

2d ago Marcus Ritt 66

8

votes

2

answers

123

views

Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?

reference-request fl.formal-languages parsing brzozwoski-derivatives

2d ago Mikhail Glushenkov 71

5

votes

1

answer

114

views

Efficient Algorithm for bilinear pairing on ECC

computability cr.crypto-security

nov 25 at 4:59 PulpSpy 36

15

votes

1

answer

210

views

$BQP$ vs $QMA$?

cc.complexity-theory complexity-classes quantum-computing

nov 24 at 22:30 Scott Aaronson 2,408

6

votes

2

answers

137

views

Taxonomy of notable regular expression automata

automata-theory fl.formal-languages regular-expressions

nov 24 at 22:04 Hermann Gruber 146

18

votes

3

answers

390

views

Hardness of approximation - additive error

cc.complexity-theory complexity-classes np-hardness approximation-hardness

nov 24 at 14:31 Tsuyoshi Ito 3,208

5

votes

1

answer

77

views

What is the initialization time of a link-cut tree?

ds.algorithms ds.data-structures time-complexity tree dynamic

nov 24 at 13:58 blackkettle 268

111

votes

73

answers

31

kviews

Algorithms from the Book.

ds.algorithms big-list ds.data-structures

nov 24 at 7:23 Kaveh 2,513

1

vote

1

answer

77

views

Kernighan–Lin algorithm and multiple gain functions

graph-theory graph-algorithms

nov 24 at 0:49 Marcus Ritt 66

49

votes

13

answers

3

kviews

Advice on good research practices

soft-question research-practice advice-request

nov 23 at 23:12 Alessandro Cosentino 267

11

votes

0

answers

155

views

Oracle relative to which MA does not have a complete problem?

cc.complexity-theory reference-request complexity-classes randomness relativization

nov 23 at 21:44 Dai Le 341

15

votes

3

answers

345

views

Can we quantify the “degree of quantumness” in a quantum algorithm ?

quantum-computing big-picture entanglement

nov 23 at 21:33 Alessandro Cosentino 267

Top Questions

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.

Welcome New User!

Recent Tags

Recent Badges