All reports by Author Alexander Smal:

__
TR18-089
| 27th April 2018
__

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

Revisions: 2

__
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

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