Vsevolod Oparin

SODA Conference 2017 Conference Paper

Algorithmic and Hardness Results for the Hub Labeling Problem

• Haris Angelidakis
• Yury Makarychev
• Vsevolod Oparin

MFCS Conference 2016 Conference Paper

Computational and Proof Complexity of Partial String Avoidability

• Dmitry Itsykson
• Alexander Okhotin
• Vsevolod Oparin

The partial string avoidability problem, also known as partial word avoidability, is stated as follows: given a finite set of strings with possible ``holes'' (undefined symbols), determine whether there exists any two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in PSPACE, and this paper establishes its PSPACE-completeness. Next, string avoidability over the binary alphabet is interpreted as a version of conjunctive normal form (CNF) satisfiability problem (SAT), with each clause having infinitely many shifted variants. Non-satisfiability of these formulas can be proved using variants of classical propositional proof systems, augmented with derivation rules for shifting constraints (such as clauses, inequalities, polynomials, etc). Two results on their proof complexity are established. First, there is a particular formula that has a short refutation in Resolution with shift, but requires classical proofs of exponential size (Resolution, Cutting Plane, Polynomial Calculus, etc.). At the same time, exponential lower bounds for shifted versions of classical proof systems are established.

SAT Conference 2016 Conference Paper

Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle

• Vsevolod Oparin

Abstract The usual DPLL algorithm uses splittings (branchings) on single Boolean variables. We consider an extension to allow splitting on linear combinations mod 2, which yields a search tree called a linear splitting tree. We prove that the pigeonhole principle has linear splitting trees of size \(2^{O(n)}\). This is near-optimal since Itsykson and Sokolov [ 1 ] proved a \(2^{\varOmega (n)}\) lower bound. It improves on the size \(2^{\varTheta (n \log n)}\) for splitting on single variables; thus the pigeonhole principle has a gap between linear splitting and the usual splitting on single variables. This is of particular interest since the pigeonhole principle is not based on linear constraints. We further prove that the perfect matching principle has splitting trees of size \(2^{O(n)}\).