2022 Developer Survey is open! Take survey.
user avatar
user avatar
user avatar
vzn
  • Member for 10 years, 4 months
  • Last seen more than 1 year ago
-2 votes
1 answer
242 views

questions on implications Babais quasi P time graph isomorphism result

8 votes
1 answer
304 views

Two DFA intersection emptiness connections to SETH & L vs P

6 votes
2 answers
262 views

FSM transducer sequential composition decidability

10 votes
1 answer
251 views

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

10 votes
2 answers
277 views

Matrix vector multiplication algorithm using minimal number of additions

12 votes
1 answer
856 views

L/P/PSpace vs P/NP

-2 votes
1 answer
124 views

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

4 votes
1 answer
420 views

Analogies between VNP and NP

1 vote
0 answers
72 views

complexity of factoring multivariate polynomials over Fn

7 votes
2 answers
395 views

possible bridge between group growth theory and complexity theory?

3 votes
2 answers
245 views

computing maximal bit density over a FSM

4 votes
1 answer
297 views

minimal finite automata given in-words and out-words

10 votes
2 answers
849 views

Implications of Riemann Hypothesis variants in TCS

27 votes
3 answers
3k views

Impact of Grothendieck's program on TCS

1 vote
0 answers
355 views

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

2 votes
0 answers
172 views

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

5 votes
0 answers
119 views

extracting/ exploiting similarity of SAT instances by solver

3 votes
0 answers
125 views

minimal languages that "cover" grammar productions

5 votes
1 answer
300 views

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

4 votes
2 answers
364 views

TCS oriented refs/survey on group theoretic word problem

0 votes
1 answer
330 views

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

3 votes
4 answers
923 views

Turing-complete computation models on graphs

9 votes
2 answers
1k views

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

1 vote
1 answer
575 views

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

8 votes
1 answer
595 views

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

1 vote
0 answers
134 views

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

-4 votes
1 answer
483 views

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

6 votes
1 answer
171 views

Inverse of transducer compositions

1 vote
1 answer
813 views

finding "hubs" in a graph

5 votes
0 answers
287 views

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