Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Dmitry Sokolov:

TR19-001 | 5th January 2019
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

On OBDD-based algorithms and proof systems that dynamically change order of variables

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>

TR18-163 | 18th September 2018
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

Adventures in Monotone Complexity and TFNP

$\mathbf{Separations:}$ We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite ... more >>>

TR18-041 | 26th February 2018
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Reordering Rule Makes OBDD Proof Systems Stronger

Atserias, Kolaitis, and Vardi [AKV04] showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD($\land$, weakening), simulates CP* (Cutting Planes with unary coefficients). We show that OBDD($\land$, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring ... more >>>

TR17-175 | 13th November 2017
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

Monotone Circuit Lower Bounds from Resolution

For any unsatisfiable CNF formula $F$ that is hard to refute in the Resolution proof system, we show that a gadget-composed version of $F$ is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with $F$ has large ... more >>>

TR16-202 | 19th December 2016
Dmitry Sokolov

Dag-like Communication and Its Applications

Revisions: 1

In 1990 Karchmer and Widgerson considered the following communication problem $Bit$: Alice and Bob know a function $f: \{0, 1\}^n \to \{0, 1\}$, Alice receives a point $x \in f^{-1}(1)$, Bob receives $y \in f^{-1}(0)$, and their goal is to find a position $i$ such that $x_i \neq y_i$. Karchmer ... more >>>

TR15-174 | 18th October 2015
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Complexity of distributions and average-case hardness

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider ... more >>>

TR14-178 | 5th December 2014
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Heuristic time hierarchies via hierarchies for sampling distributions

We give a new simple proof of the time hierarchy theorem for heuristic BPP originally proved by Fortnow and Santhanam [FS04] and then simplified and improved by Pervyshev [P07]. In the proof we use a hierarchy theorem for sampling distributions recently proved by Watson [W13]. As a byproduct we get ... more >>>

TR14-093 | 22nd July 2014
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Resolution complexity of perfect mathcing principles for sparse graphs

The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is ... more >>>

TR14-050 | 21st March 2014
Edward Hirsch, Dmitry Sokolov

On the probabilistic closure of the loose unambiguous hierarchy

Revisions: 1

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>>

TR12-141 | 22nd October 2012
Dmitry Itsykson, Dmitry Sokolov

Lower bounds for myopic DPLL algorithms with a cut heuristic

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>>

ISSN 1433-8092 | Imprint