Skip to main content
Yaroslav Bulatov's user avatar
Yaroslav Bulatov's user avatar
Yaroslav Bulatov's user avatar
Yaroslav Bulatov
  • Member for 13 years, 10 months
  • Last seen more than a month ago
2 votes
0 answers
72 views

Summing over weighted paths optimally

6 votes
1 answer
364 views

Complexity of optimal elimination for a planar tensor network

3 votes
2 answers
158 views

Parameterized complexity of tree/branch decomposition

2 votes
0 answers
97 views

How typical are odd-H-minor free graphs?

2 votes
0 answers
101 views

Inverting a sum of easy to invert linear terms?

5 votes
1 answer
374 views

When is it hard to invert a sparse matrix?

3 votes
0 answers
33 views

references for optimal computation under memory constraint?

8 votes
2 answers
1k views

SDP relaxation of independent set

13 votes
4 answers
5k views

LP relaxation of independent set

29 votes
6 answers
2k views

Which SAT problems are easy?

11 votes
1 answer
414 views

Making SAT solvers competitive with specialized algorithms

5 votes
0 answers
142 views

Sampling small separators

2 votes
1 answer
177 views

Data-structure for functions of independent sets

4 votes
0 answers
247 views

Ising Model and Eulerian Subgraphs

12 votes
1 answer
332 views

Typical hardness of tree decomposition?

6 votes
0 answers
219 views

Decomposition based on approximate separators in graph

23 votes
8 answers
3k views

graphs from real-life problems

10 votes
3 answers
1k views

Tree decomposition for planar graphs

6 votes
1 answer
229 views

Ensemble of tree decompositions for all-pairs problem

5 votes
1 answer
395 views

Solving "all-marginals" problem for independent sets on grid

21 votes
4 answers
983 views

Examples of hardness phase transitions

15 votes
1 answer
463 views

Graph decompositions for combining "local" functions of vertex labelings

31 votes
5 answers
1k views

what is easy for minor-excluded graphs?

9 votes
2 answers
655 views

Chernoff-type inequality for random variable with 3 outcomes

6 votes
2 answers
838 views

When is Ising partition function easy to compute?

4 votes
2 answers
261 views

Complexity of linearized Ising model at 0

4 votes
0 answers
231 views

Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?

27 votes
3 answers
994 views

When is relaxed counting hard?

8 votes
2 answers
356 views

complexity of fitting models to data