vzn
  • Member for 10 years
  • Last seen more than a month ago
2 answers
4 votes
364 views
2 bookmarks
TCS oriented refs/survey on group theoretic word problem
2 answers
4 votes
506 views
1 bookmarks
P/poly vs NP separation based on circuit trees instead of DAGs
3 answers
4 votes
580 views
3 bookmarks
How to minimize a FSM transducer?
1 answers
3 votes
222 views
2 bookmarks
Finding self-similar homomorphisms of a FSM transducer
2 answers
3 votes
245 views
computing maximal bit density over a FSM
0 answers
3 votes
125 views
2 bookmarks
minimal languages that "cover" grammar productions
1 answers
3 votes
1k views
1 bookmarks
What NP-complete problems are most similar to integer factoring?
2 answers
3 votes
444 views
1 bookmarks
Factoring Cartesian bitwise join of bit vectors
0 answers
2 votes
170 views
2 bookmarks
proving speedup phenomenon does not apply to any open complexity class separations
4 answers
2 votes
884 views
3 bookmarks
Turing-complete computation models on graphs
1 answers
2 votes
550 views
1 bookmarks
techniques or examples of analyzing a series of graphs
1 answers
1 votes
574 views
2 bookmarks
equivalent way(s) of expressing P=?NP problem in linear programming?
0 answers
1 votes
72 views
complexity of factoring multivariate polynomials over Fn
2 answers
1 votes
217 views
1 bookmarks
research on systematically attacking multiple instances of undecidable problems
0 answers
1 votes
341 views
intuition that VP=?VNP is (not?) connected to P=?NP
0 answers
1 votes
132 views
1 bookmarks
looking for notable applications of ASP (Answer Set Programming) in TCS
1 answers
1 votes
721 views
1 bookmarks
finding "hubs" in a graph
1 answers
1 votes
367 views
2 bookmarks
Questions about computing matrix rigidity
1 answers
1 votes
322 views
3 bookmarks
in SAT resolution proofs, are all DAGs possible?
1 answers
0 votes
326 views
1 bookmarks
is determining an unknown CFL from intersection of two CFLs decidable?
2 answers
0 votes
177 views
iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation
2 answers
0 votes
632 views
1 bookmarks
largest language class for which inclusion is decidable
1 answers
-2 votes
239 views
questions on implications Babais quasi P time graph isomorphism result
1 answers
-2 votes
122 views
what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?
1 answers
-3 votes
171 views
1 bookmarks
computing with gates on polar coordinates, functionally complete wrt boolean functions?
1 answers
-4 votes
467 views
1 bookmarks
"tree-like" vs "DAG-like" resolution
1 answers
-5 votes
342 views
2 bookmarks
Attacking TSP via small nonintersecting circuits
1 answers
-5 votes
1k views
1 bookmarks
why is a Turing machine defined as a 5-tuple?
1 answers
-5 votes
320 views
1 bookmarks
whats the difference between nondeterminism and parallelism?
2 answers
-9 votes
678 views
Is every "nontrivial" algorithm Turing-complete?
1
2