User vzn

-2

votes

1

answer

235

views

questions on implications Babais quasi P time graph isomorphism result

Jan 27 '17 at 23:43 Community♦ 1

4

8

votes

1

answer

288

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

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

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

1

12

votes

1

answer

710

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

-2

votes

1

answer

113

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

Aug 2 '15 at 9:35 Community♦ 1

2

4

votes

1

answer

396

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.3k

1

vote

0

answers

72

views

complexity of factoring multivariate polynomials over Fn

cc.complexity-theory reference-request polynomials

Apr 20 '15 at 1:40 vzn 10.8k

1

7

votes

2

answers

387

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

3

votes

2

answers

244

views

computing maximal bit density over a FSM

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

Jan 10 '15 at 7:10 Francisco Mota 633

4

votes

1

answer

270

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

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

17

27

votes

3

answers

3k

views

Impact of Grothendieck's program on TCS

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

Nov 16 '14 at 21:06 Community♦ 1

1

vote

0

answers

328

views

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

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

Nov 7 '14 at 16:18 Community♦ 1

2

votes

0

answers

169

views

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

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

Aug 15 '14 at 16:10 vzn 10.8k

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

2

3

votes

0

answers

119

views

minimal languages that “cover” grammar productions

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

Jul 18 '14 at 15:11 Community♦ 1

3

5

votes

1

answer

273

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

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

1

0

votes

1

answer

292

views

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

reference-request computability automata-theory context-free

Apr 5 '14 at 14:56 Community♦ 1

3

1

vote

4

answers

816

views

Turing-complete computation models on graphs

reference-request graph-theory graph-algorithms computability

Apr 3 '14 at 20:52 Niel de Beaudrap 8,729

4

9

votes

2

answers

965

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

2

1

vote

1

answer

548

views

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

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

Apr 20 '17 at 8:53 Rahul Savani 1,703

2

8

votes

1

answer

586

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.9k

1

vote

0

answers

129

views

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

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

Jan 31 '14 at 23:37 Community♦ 1

1

-4

votes

1

answer

445

views

“tree-like” vs “DAG-like” resolution

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

Jan 24 '14 at 21:13 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

1

vote

1

answer

575

views

finding “hubs” in a graph

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

Dec 26 '13 at 0:08 Bangye 844

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

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”