User vzn

27 votes

3 answers

3k views

Impact of Grothendieck's program on TCS

asked Nov 14, 2014 at 18:58

21 votes

2 answers

3k views

computing the minimal NFA for a DFA

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

asked Mar 23, 2012 at 17:44

16 votes

2 answers

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

asked Jun 2, 2012 at 4:44

12 votes

1 answer

863 views

L/P/PSpace vs P/NP

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

asked Aug 7, 2015 at 22:11

11 votes

1 answer

644 views

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

reference-request quantum-computing application-of-theory

asked Feb 24, 2012 at 17:31

11 votes

0 answers

528 views

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

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

asked May 31, 2013 at 15:42

11 votes

2 answers

866 views

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

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

asked Aug 9, 2013 at 15:16

10 votes

2 answers

279 views

Matrix vector multiplication algorithm using minimal number of additions

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

asked Sep 25, 2015 at 5:59

10 votes

1 answer

251 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

asked Oct 16, 2015 at 15:12

10 votes

2 answers

849 views

Implications of Riemann Hypothesis variants in TCS

cc.complexity-theory algebraic-complexity arithmetic-circuits

asked Nov 29, 2014 at 15:52

9 votes

2 answers

1k views

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

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

asked Mar 21, 2014 at 16:32

9 votes

2 answers

847 views

Is adiabatic quantum computing as powerful as the circuit model?

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

asked Mar 22, 2013 at 16:02

8 votes

1 answer

595 views

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

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

asked Feb 18, 2014 at 19:47

8 votes

2 answers

1k views

(0,1)-vector XOR problem

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

asked Feb 26, 2012 at 17:40

8 votes

2 answers

1k views

Automated theorem proving via unsupervised approaches

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

asked Jun 22, 2012 at 16:12

8 votes

1 answer

482 views

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

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

asked Dec 14, 2012 at 19:58

8 votes

1 answer

307 views

Two DFA intersection emptiness connections to SETH & L vs P

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

asked Nov 6, 2015 at 16:54

7 votes

2 answers

395 views

possible bridge between group growth theory and complexity theory?

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

asked Feb 21, 2015 at 21:32

7 votes

0 answers

361 views

Examples of non-CSLs not created through diagonalization

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

asked Apr 28, 2012 at 15:03

6 votes

1 answer

172 views

Inverse of transducer compositions

ds.algorithms reference-request automata-theory

asked Jan 8, 2014 at 23:00

6 votes

1 answer

292 views

any connection between binary/integer multiplication and matrix multiplication?

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

asked Oct 30, 2013 at 17:38

6 votes

0 answers

976 views

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

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

asked Apr 12, 2013 at 15:22

6 votes

2 answers

262 views

FSM transducer sequential composition decidability

reference-request automata-theory regular-language dfa decidability

asked Oct 23, 2015 at 15:17

5 votes

1 answer

302 views

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

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

asked Jul 11, 2014 at 15:12

5 votes

0 answers

119 views

extracting/ exploiting similarity of SAT instances by solver

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

asked Jul 25, 2014 at 16:54

5 votes

0 answers

288 views

Sketch of Razborov's paper "On the method of approximations"

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

asked Nov 22, 2013 at 18:41

5 votes

0 answers

292 views

Are there applications of experimental mathematics in TCS?

cc.complexity-theory application-of-theory automated-theorem-proving experimental

asked Dec 4, 2012 at 2:42

5 votes

4 answers

407 views

What is some important work in fractals?

reference-request fractals

asked Mar 10, 2012 at 0:49

4 votes

2 answers

518 views

P/poly vs NP separation based on circuit trees instead of DAGs

cc.complexity-theory graph-theory lower-bounds p-vs-np circuits

asked Nov 1, 2013 at 21:50

4 votes

3 answers

598 views

How to minimize a FSM transducer?

reference-request automata-theory regular-language dfa minimization

asked Sep 8, 2013 at 14:20

Stack Exchange Network

current community

your communities

more stack exchange communities

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 is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

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

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

Matrix vector multiplication algorithm using minimal number of additions

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

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?

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

(0,1)-vector XOR problem

Automated theorem proving via unsupervised approaches

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

Two DFA intersection emptiness connections to SETH & L vs P

possible bridge between group growth theory and complexity theory?

Examples of non-CSLs not created through diagonalization

Inverse of transducer compositions

any connection between binary/integer multiplication and matrix multiplication?

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

FSM transducer sequential composition decidability

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

extracting/ exploiting similarity of SAT instances by solver

Sketch of Razborov's paper "On the method of approximations"

Are there applications of experimental mathematics in TCS?

What is some important work in fractals?

P/poly vs NP separation based on circuit trees instead of DAGs

How to minimize a FSM transducer?