Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of ... more >>>

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>

We show that NP-hardness of approximating Boolean unique games on small set expanders can be amplified to the full Unique Games Conjecture on small set expanders.
The latter conjecture is known to imply hardness results for problems like Balanced-Separator, Minimum-Linear-Rearrangement and Small-Set-Expansion that are not known under the Unique ... more >>>