Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko
  • Member for 13 years, 6 months
  • Last seen more than a week ago
  • Kiev, Ukraine
10 votes

Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?

7 votes
Accepted

Is this a known combinatorial optimization/scheduling problem?

9 votes

Problems Between P and NPC

31 votes

Conjectures implying Four Color Theorem

11 votes
Accepted

Graph planar drawing, with each edge's length is known

6 votes
Accepted

Examples of #P problems which are in FP ?

13 votes

Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory

22 votes
Accepted

Collatz Conjecture & Grammars / Automata

4 votes

Is there any known work on generating random uniformly distributed DAGs given a set of path existence/absence constraints?

7 votes

Relation between fixed parameter and approximation algorithm

15 votes

What are the recent TCS books whose drafts are available online?

8 votes
Accepted

Poly-time approximation scheme for problems with pseudo-polynomial time algorithms

6 votes

How do you call a subsequence of consecutive elements ?

13 votes
Accepted

Examples of hard instances for Goemans and Williamson algorithm

15 votes
Accepted

What is the tradeoff between population size and the number of generations in genetic algorithms

10 votes
Accepted

Problems that are NP-complete under randomized or P/poly reductions.

18 votes

What are the recent TCS books whose drafts are available online?

15 votes
Accepted

Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

4 votes

Ways for a mathematician to stay informed of current research in complexity theory

9 votes

What Lecture Notes Should Everyone Read?

8 votes

Problems Between P and NPC

23 votes
Accepted

Ways for a mathematician to stay informed of current research in complexity theory

7 votes
Accepted

NP-Hardness of a special case of orthogonal packing problem

13 votes

What Books Should Everyone Read?

2 votes

Resources to learn about the P vs. NP problem

5 votes

Hardness jumps in computational complexity?

8 votes

Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

10 votes

What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?

18 votes

Parameterized complexity from P to NP-hard and back again

22 votes

Funny TCS-related papers etc?