User vzn

17

27

votes

3

answers

3k

views

Impact of Grothendieck's program on TCS

Nov 16 '14 at 21:06 Community♦ 1

9

21

votes

2

answers

3k

views

computing the minimal NFA for a DFA

ds.algorithms reference-request fl.formal-languages automata-theory optimization

Aug 26 at 2:17 Joshua Wise 131

3

15

votes

2

answers

4k

views

What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?

reference-request open-problem nt.number-theory halting-problem computability

Jul 14 '15 at 15:32 Community♦ 1

1

12

votes

1

answer

700

views

L/P/PSpace vs P/NP

cc.complexity-theory reference-request lower-bounds p-vs-np conditional-results

Aug 8 '15 at 20:58 Community♦ 1

3

11

votes

2

answers

778

views

What's the correlation between treewidth and instance hardness for random 3-SAT?

graph-algorithms sat treewidth random-k-sat hard-instances

Oct 22 '14 at 18:59 daniello 3,081

2

11

votes

0

answers

519

views

Has there been any result which does not have any Natural Proofs?

cc.complexity-theory reference-request circuit-complexity barriers natural-proofs

Jun 6 '13 at 4:46 Jeffε 22.6k

2

11

votes

1

answer

608

views

What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

reference-request quantum-computing application-of-theory

Jun 24 '12 at 4:52 Community♦ 1

1

10

votes

1

answer

238

views

Is it decidable whether the output length of a transducer is bounded by the input length?

ds.algorithms reference-request automata-theory regular-language dfa

Oct 17 '15 at 17:22 Michaël Cadilhac 3,776

2

10

votes

2

answers

269

views

Matrix vector multiplication algorithm using minimal number of additions

cc.complexity-theory reference-request circuit-complexity matrices arithmetic-circuits

Sep 26 '15 at 12:42 Community♦ 1

3

10

votes

2

answers

826

views

Implications of Riemann Hypothesis variants in TCS

cc.complexity-theory algebraic-complexity arithmetic-circuits

Nov 30 '14 at 10:11 Juho 3,150

4

9

votes

2

answers

960

views

Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

cc.complexity-theory oracles p-vs-np relativization

Mar 23 '14 at 10:23 Community♦ 1

5

9

votes

2

answers

833

views

Is adiabatic quantum computing as powerful as the circuit model?

cc.complexity-theory reference-request complexity-classes quantum-computing quantum-information

Nov 7 '13 at 10:41 Niel de Beaudrap 8,709

4

8

votes

1

answer

285

views

Two DFA intersection emptiness connections to SETH & L vs P

reference-request complexity-classes p-vs-np exp-time-algorithms fine-grained

Nov 6 '15 at 22:15 Community♦ 1

2

8

votes

1

answer

585

views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

reference-request co.combinatorics soft-question big-picture

Feb 21 '14 at 19:57 Sasho Nikolov 17.8k

2

8

votes

1

answer

468

views

Are there applications of modular graph decomposition in TCS/complexity theory?

reference-request graph-theory graph-algorithms application-of-theory cc.complexity-theory

Dec 15 '12 at 8:07 Community♦ 1

3

8

votes

2

answers

1k

views

(0,1)-vector XOR problem

cc.complexity-theory reference-request circuit-complexity lower-bounds

Feb 26 '12 at 20:23 Community♦ 1

1

7

votes

2

answers

382

views

possible bridge between group growth theory and complexity theory?

cc.complexity-theory reference-request complexity-classes big-picture gr.group-theory

Mar 14 '17 at 5:41 Community♦ 1

4

7

votes

2

answers

1k

views

Automated theorem proving via unsupervised approaches

reference-request lo.logic proof-complexity automated-theorem-proving

Oct 19 '14 at 15:04 Community♦ 1

1

7

votes

0

answers

345

views

Examples of non-CSLs not created through diagonalization

reference-request fl.formal-languages automata-theory big-picture

Oct 6 '12 at 19:22 Bill the Lizard 123

1

6

votes

2

answers

254

views

FSM transducer sequential composition decidability

reference-request automata-theory regular-language dfa decidability

Nov 1 '15 at 17:37 Community♦ 1

3

6

votes

1

answer

163

views

Inverse of transducer compositions

ds.algorithms reference-request automata-theory

Mar 4 '14 at 23:11 Community♦ 1

2

6

votes

1

answer

267

views

any connection between binary/integer multiplication and matrix multiplication?

cc.complexity-theory reference-request boolean-functions matrices

Oct 30 '13 at 18:56 usul 6,744

5

6

votes

0

answers

885

views

k-CNF ←→ k-DNF conversion to minimize errors

cc.complexity-theory reference-request circuit-complexity approximation boolean-formulas

Apr 13 '13 at 19:23 Community♦ 1

2

5

votes

0

answers

280

views

Sketch of Razborov's paper “On the method of approximations”

cc.complexity-theory circuit-complexity lower-bounds big-picture circuits

Jun 30 '17 at 7:30 Community♦ 1

2

5

votes

0

answers

117

views

extracting/ exploiting similarity of SAT instances by solver

reference-request sat machine-learning application-of-theory automated-theorem-proving

Jul 25 '14 at 16:54 vzn 10.8k

3

5

votes

1

answer

264

views

any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

reference-request graph-theory big-picture application-of-theory

Jul 11 '14 at 17:53 Community♦ 1

3

5

votes

4

answers

400

views

What is some important work in fractals?

reference-request fractals

Mar 11 '12 at 8:54 Community♦ 1

2

4

votes

1

answer

395

views

Analogies between VNP and NP

cc.complexity-theory reference-request big-picture p-vs-np arithmetic-circuits

May 2 '15 at 12:39 Mohammad Al-Turkistany 20.2k

4

votes

1

answer

263

views

minimal finite automata given in-words and out-words

reference-request optimization machine-learning regular-language nondeterminism

Dec 29 '14 at 20:36 Mateus de Oliveira Oliveira 3,001

2

4

votes

2

answers

360

views

TCS oriented refs/survey on group theoretic word problem

reference-request soft-question big-picture application-of-theory gr.group-theory

Apr 12 '14 at 3:31 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

60 Questions

Impact of Grothendieck's program on TCS

computing the minimal NFA for a DFA

What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?

L/P/PSpace vs P/NP

What's the correlation between treewidth and instance hardness for random 3-SAT?

Has there been any result which does not have any Natural Proofs?

What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

Is it decidable whether the output length of a transducer is bounded by the input length?

Matrix vector multiplication algorithm using minimal number of additions

Implications of Riemann Hypothesis variants in TCS

Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

Is adiabatic quantum computing as powerful as the circuit model?

Two DFA intersection emptiness connections to SETH & L vs P

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

Are there applications of modular graph decomposition in TCS/complexity theory?

(0,1)-vector XOR problem

possible bridge between group growth theory and complexity theory?

Automated theorem proving via unsupervised approaches

Examples of non-CSLs not created through diagonalization

FSM transducer sequential composition decidability

Inverse of transducer compositions

any connection between binary/integer multiplication and matrix multiplication?

k-CNF ←→ k-DNF conversion to minimize errors

Sketch of Razborov's paper “On the method of approximations”

extracting/ exploiting similarity of SAT instances by solver

any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

What is some important work in fractals?

Analogies between VNP and NP

minimal finite automata given in-words and out-words

TCS oriented refs/survey on group theoretic word problem