user avatar
user avatar
user avatar
vzn
  • Member for 10 years, 5 months
  • Last seen more than 1 year ago
27 votes
3 answers
3k views

Impact of Grothendieck's program on TCS

21 votes
2 answers
3k views

computing the minimal NFA for a DFA

16 votes
2 answers
5k views

What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

12 votes
1 answer
863 views

L/P/PSpace vs P/NP

11 votes
1 answer
644 views

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

11 votes
0 answers
528 views

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

11 votes
2 answers
866 views

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

10 votes
2 answers
279 views

Matrix vector multiplication algorithm using minimal number of additions

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
849 views

Implications of Riemann Hypothesis variants in TCS

9 votes
2 answers
1k views

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

9 votes
2 answers
847 views

Is adiabatic quantum computing as powerful as the circuit model?

8 votes
1 answer
595 views

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

8 votes
2 answers
1k views

(0,1)-vector XOR problem

8 votes
2 answers
1k views

Automated theorem proving via unsupervised approaches

8 votes
1 answer
482 views

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

8 votes
1 answer
307 views

Two DFA intersection emptiness connections to SETH & L vs P

7 votes
2 answers
395 views

possible bridge between group growth theory and complexity theory?

7 votes
0 answers
361 views

Examples of non-CSLs not created through diagonalization

6 votes
1 answer
172 views

Inverse of transducer compositions

6 votes
1 answer
292 views

any connection between binary/integer multiplication and matrix multiplication?

6 votes
0 answers
976 views

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

6 votes
2 answers
262 views

FSM transducer sequential composition decidability

5 votes
1 answer
302 views

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

5 votes
0 answers
119 views

extracting/ exploiting similarity of SAT instances by solver

5 votes
0 answers
288 views

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

5 votes
0 answers
292 views

Are there applications of experimental mathematics in TCS?

5 votes
4 answers
407 views

What is some important work in fractals?

4 votes
2 answers
518 views

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

4 votes
3 answers
598 views

How to minimize a FSM transducer?