All reports by Author Alexander Smal:

__
TR24-037
| 26th February 2024
__

Yaroslav Alekseev, Yuval Filmus, Alexander Smal#### Lifting dichotomies

Revisions: 2

__
TR23-016
| 22nd February 2023
__

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals#### Proving Unsatisfiability with Hitting Formulas

Revisions: 1

__
TR22-016
| 15th February 2022
__

Artur Ignatiev, Ivan Mihajlin, Alexander Smal#### Super-cubic lower bound for generalized Karchmer-Wigderson games

Revisions: 1

__
TR20-117
| 4th August 2020
__

Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov#### New bounds on the half-duplex communication complexity

Revisions: 3

__
TR20-116
| 1st August 2020
__

Ivan Mihajlin, Alexander Smal#### Toward better depth lower bounds: the XOR-KRW conjecture

Revisions: 2

__
TR18-089
| 27th April 2018
__

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal#### Half-duplex communication complexity

Revisions: 6

__
TR17-191
| 15th December 2017
__

Alexander Smal, Navid Talebanfard#### Prediction from Partial Information and Hindsight, an Alternative Proof

Revisions: 2

__
TR16-022
| 22nd February 2016
__

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki#### Circuit size lower bounds and #SAT upper bounds through a general framework

Revisions: 2

__
TR11-091
| 20th May 2011
__

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal#### Optimal heuristic algorithms for the image of an injective function

__
TR10-193
| 5th December 2010
__

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal#### On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $A$ for some function $f$, we compose $f$ with a carefully chosen gadget function $g$ and get essentially the same lower bound on a complexity measure $B$ for the ... more >>>

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

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 >>>

Artur Ignatiev, Ivan Mihajlin, Alexander Smal

In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for some explicit function $f: \{0,1\}^n\to \{0,1\}^{\log n}$. Lower bounds for original Karchmer-Wigderson games correspond to De Morgan formula lower bounds, thus the best known size lower bound is cubic. ... more >>>

Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov

In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... more >>>

Ivan Mihajlin, Alexander Smal

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower ... more >>>

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other ... more >>>

Alexander Smal, Navid Talebanfard

Let $X$ be a random variable distributed over $n$-bit strings with $H(X) \ge n - k$, where $k \ll n$. Using subadditivity we know that a random coordinate looks random. Meir and Wigderson [TR17-149] showed a random coordinate looks random to an adversary who is allowed to query around $n/k$ ... more >>>

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>>

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>>

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) ... more >>>