Skip to main content
Share Your Experience: Take the 2024 Developer Survey
vzn's user avatar
vzn's user avatar
vzn's user avatar
vzn
  • Member for 12 years, 4 months
  • Last seen more than 3 years ago
28 votes
3 answers
4k views

Impact of Grothendieck's program on TCS

23 votes
2 answers
4k views

computing the minimal NFA for a DFA

19 votes
2 answers
6k views

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

13 votes
2 answers
937 views

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

12 votes
1 answer
770 views

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

12 votes
1 answer
985 views

L/P/PSpace vs P/NP

11 votes
0 answers
542 views

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

10 votes
2 answers
312 views

Matrix vector multiplication algorithm using minimal number of additions

10 votes
1 answer
265 views

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

9 votes
2 answers
889 views

Implications of Riemann Hypothesis variants in TCS

9 votes
2 answers
863 views

Is adiabatic quantum computing as powerful as the circuit model?

9 votes
2 answers
2k views

(0,1)-vector XOR problem

9 votes
2 answers
1k views

Automated theorem proving via unsupervised approaches

8 votes
1 answer
498 views

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

8 votes
1 answer
604 views

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

8 votes
2 answers
1k views

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

8 votes
1 answer
328 views

Two DFA intersection emptiness connections to SETH & L vs P

7 votes
2 answers
411 views

possible bridge between group growth theory and complexity theory?

7 votes
0 answers
374 views

Examples of non-CSLs not created through diagonalization

6 votes
1 answer
194 views

Inverse of transducer compositions

6 votes
1 answer
308 views

any connection between binary/integer multiplication and matrix multiplication?

6 votes
0 answers
1k views

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

6 votes
2 answers
278 views

FSM transducer sequential composition decidability

5 votes
1 answer
366 views

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

5 votes
0 answers
121 views

extracting/ exploiting similarity of SAT instances by solver

5 votes
0 answers
293 views

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

5 votes
0 answers
306 views

Are there applications of experimental mathematics in TCS?

5 votes
4 answers
412 views

What is some important work in fractals?

4 votes
2 answers
555 views

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

4 votes
3 answers
719 views

How to minimize a FSM transducer?