User vzn

-2 votes

1 answer

242 views

questions on implications Babais quasi P time graph isomorphism result

asked Jan 27, 2017 at 22:22

8 votes

1 answer

304 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

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

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

277 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

12 votes

1 answer

856 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

-2 votes

1 answer

124 views

what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?

reference-request big-picture application-of-theory p-vs-np ar.hardware-architecture

asked Jul 31, 2015 at 15:35

4 votes

1 answer

420 views

Analogies between VNP and NP

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

asked May 1, 2015 at 15:05

1 vote

0 answers

72 views

complexity of factoring multivariate polynomials over Fn

cc.complexity-theory reference-request polynomials

asked Apr 20, 2015 at 1:40

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

3 votes

2 answers

245 views

computing maximal bit density over a FSM

reference-request co.combinatorics automata-theory regular-language upper-bounds

asked Jan 9, 2015 at 16:22

4 votes

1 answer

297 views

minimal finite automata given in-words and out-words

reference-request optimization machine-learning regular-language nondeterminism

asked Dec 26, 2014 at 23:54

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

27 votes

3 answers

3k views

Impact of Grothendieck's program on TCS

big-picture ct.category-theory ho.history-overview

asked Nov 14, 2014 at 18:58

1 vote

0 answers

355 views

intuition that VP=?VNP is (not?) connected to P=?NP

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

asked Nov 7, 2014 at 16:18

2 votes

0 answers

172 views

proving speedup phenomenon does not apply to any open complexity class separations

cc.complexity-theory reference-request complexity-classes time-complexity big-picture

asked Aug 15, 2014 at 16:10

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

3 votes

0 answers

125 views

minimal languages that "cover" grammar productions

reference-request big-picture application-of-theory grammars minimization

asked Jul 18, 2014 at 15:11

5 votes

1 answer

300 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

4 votes

2 answers

364 views

TCS oriented refs/survey on group theoretic word problem

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

asked Apr 11, 2014 at 15:47

0 votes

1 answer

330 views

is determining an unknown CFL from intersection of two CFLs decidable?

reference-request computability automata-theory context-free

asked Apr 5, 2014 at 14:45

3 votes

4 answers

923 views

Turing-complete computation models on graphs

reference-request graph-theory graph-algorithms computability

asked Mar 28, 2014 at 15:03

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

1 vote

1 answer

575 views

equivalent way(s) of expressing P=?NP problem in linear programming?

lower-bounds linear-programming p-vs-np barriers simplex

asked Mar 7, 2014 at 16:31

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

1 vote

0 answers

134 views

looking for notable applications of ASP (Answer Set Programming) in TCS

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

asked Jan 31, 2014 at 22:00

-4 votes

1 answer

483 views

"tree-like" vs "DAG-like" resolution

reference-request graph-theory circuit-complexity big-picture resolution

asked Jan 24, 2014 at 19:11

6 votes

1 answer

171 views

Inverse of transducer compositions

ds.algorithms reference-request automata-theory

asked Jan 8, 2014 at 23:00

1 vote

1 answer

813 views

finding "hubs" in a graph

reference-request graph-theory optimization application-of-theory

asked Dec 24, 2013 at 2:38

5 votes

0 answers

287 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

Stack Exchange Network

current community

your communities

more stack exchange communities

60 Questions

questions on implications Babais quasi P time graph isomorphism result

Two DFA intersection emptiness connections to SETH & L vs P

FSM transducer sequential composition decidability

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

L/P/PSpace vs P/NP

what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?

Analogies between VNP and NP

complexity of factoring multivariate polynomials over Fn

possible bridge between group growth theory and complexity theory?

computing maximal bit density over a FSM

minimal finite automata given in-words and out-words

Implications of Riemann Hypothesis variants in TCS

Impact of Grothendieck's program on TCS

intuition that VP=?VNP is (not?) connected to P=?NP

proving speedup phenomenon does not apply to any open complexity class separations

extracting/ exploiting similarity of SAT instances by solver

minimal languages that "cover" grammar productions

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

TCS oriented refs/survey on group theoretic word problem

is determining an unknown CFL from intersection of two CFLs decidable?

Turing-complete computation models on graphs

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

equivalent way(s) of expressing P=?NP problem in linear programming?

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

looking for notable applications of ASP (Answer Set Programming) in TCS

"tree-like" vs "DAG-like" resolution

Inverse of transducer compositions

finding "hubs" in a graph

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