Skip to main content
Gamow's user avatar
Gamow's user avatar
Gamow's user avatar
Gamow
  • Member for 9 years, 3 months
  • Last seen more than 2 years ago
27 votes
Accepted

Number of words of length n in a context-free language

25 votes
Accepted

How "hard" is it to maximize a polynomial function subject to linear constraints?

22 votes

Algorithm for finding a 3-cycle cover

20 votes
Accepted

Is there a counterexample to this work?

17 votes
Accepted

Counterexample to max-flow algorithms with irrational weights?

13 votes
Accepted

Complexity of counting matchings in a bipartite graph

13 votes

Why do TCS papers have author names in alphabetical order of their surnames?

11 votes
Accepted

What is the complexity of vertex cover on k-partite graphs?

11 votes
Accepted

Does Max Planar 3-SAT admit a PTAS?

10 votes
Accepted

Is the maximum independent set in cubic planar graphs NP-complete?

9 votes

How to efficiently find a loop between two nodes in a directed graph?

9 votes
Accepted

Lower bound on pebbling numbers

9 votes
Accepted

Computing topological sort while keeping edges "short"

9 votes
Accepted

Validity of exponentiation in a polynomial time reduction

8 votes
Accepted

Median finding with "green forests"?

8 votes

Definition of near-linear algorithm

8 votes
Accepted

Is there any relationship of hardness between the two problems?

8 votes
Accepted

Finding a positive point for a collection of polynomials

8 votes
Accepted

NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

8 votes

"Relatives" of the shortest path problem

7 votes
Accepted

Are there common names for the subtiers of PTIME?

7 votes
Accepted

How can I find the PhD thesis of C.A. Ellis?

7 votes

Best $\Pi_k \text{SAT}$ running time?

7 votes

Complexity of checking if two words have an interleaving in a language

7 votes
Accepted

Partition into triangles in a 3-partite graphe

7 votes
Accepted

Parameterized complexity of Exact Cover

6 votes

Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

6 votes

Does k-PATH admit a constant approximation?

6 votes

Finding the sparsest solution to a system of linear equations

6 votes

For a specific unbounded Turing machine, is its Halting problem undecidable?