Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ARTUR RIAZANOV:
All reports by Author Artur Riazanov:

TR24-117 | 12th June 2024
Ludmila Glinskih, Artur Riazanov

Partial Minimum Branching Program Size Problem is ETH-hard

We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching programs, such as read-$k$ branching programs and OBDDs.

Combining these results with our recent result (Glinskih ... more >>>


TR23-181 | 20th November 2023
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov

Hardness Condensation by Restriction

Revisions: 1

Can every $n$-bit boolean function with deterministic query complexity $k\ll n$ be restricted to $O(k)$ variables such that the query complexity remains $\Omega(k)$? That is, can query complexity be condensed via restriction? We study such hardness condensation questions in both query and communication complexity, proving two main results.

$\bullet~$ $\mathbf{Negative}$: ... more >>>


TR23-071 | 8th May 2023
Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

Sampling and Certifying Symmetric Functions

A circuit $\mathcal{C}$ samples a distribution $\mathbf{X}$ with an error $\epsilon$ if the statistical distance between the output of $\mathcal{C}$ on the uniform input and $\mathbf{X}$ is $\epsilon$. We study the hardness of sampling a uniform distribution over the set of $n$-bit strings of Hamming weight $k$ denoted by $\mathbf{U}^n_k$ ... more >>>


TR23-049 | 17th April 2023
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

Top-Down Lower Bounds for Depth-Four Circuits

Revisions: 1

We present a top-down lower-bound method for depth-$4$ boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-$4$ circuits of size exponential in $n^{1/3}$. Our proof is an application of robust sunflowers and block unpredictability.

more >>>

TR23-016 | 22nd February 2023
Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Proving Unsatisfiability with Hitting Formulas

Hitting formulas have been studied in many different contexts at least since [Iwama 1989]. A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. [Peitl and Szeider 2022] conjectured that the family of unsatisfiable hitting formulas should contain the hardest ... more >>>


TR22-046 | 4th April 2022
Dmitry Itsykson, Artur Riazanov

Automating OBDD proofs is NP-hard

We prove that the proof system OBDD(and, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of Atserias and Muller [FOCS 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with a multi-output indexing gadget from resolution ... more >>>


TR20-184 | 10th December 2020
Dmitry Itsykson, Artur Riazanov

Proof complexity of natural formulas via communication arguments

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>


TR20-073 | 5th May 2020
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

Lower Bounds on OBDD Proofs with Several Orders

This paper is motivated by seeking lower bounds on OBDD($\land$, weakening, reordering) refutations, namely OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1-NBP($\land$) refutations based on read-once nondeterministic branching programs. These generalize OBDD($\land$, reordering) refutations. There are polynomial size 1-NBP($\land$) refutations of the pigeonhole principle, hence ... more >>>


TR19-178 | 5th December 2019
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

We show that the size of any regular resolution refutation of Tseitin formula $T(G,c)$ based on a graph $G$ is at least $2^{\Omega(tw(G)/\log n)}$, where $n$ is the number of vertices in $G$ and $tw(G)$ is the treewidth of $G$. For constant degree graphs there is known upper bound $2^{O(tw(G))}$ ... more >>>


TR19-069 | 6th May 2019
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

Bounded-depth Frege complexity of Tseitin formulas for all graphs

Revisions: 1

We prove that there is a constant $K$ such that \emph{Tseitin} formulas for an undirected graph $G$ requires proofs of
size $2^{\mathrm{tw}(G)^{\Omega(1/d)}}$ in depth-$d$ Frege systems for $d<\frac{K \log n}{\log \log n}$, where $\tw(G)$ is the treewidth of $G$. This extends H{\aa}stad recent lower bound for the grid graph ... more >>>




ISSN 1433-8092 | Imprint