Andrei Bulatov

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>

Vadim Lyubashevsky, Daniele Micciancio

The generalized knapsack problem is the following: given $m$ random

elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in

R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$

where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002),

it was proved that for appropriate choices of $R$ ...
more >>>

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis ThÃ©rien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):

Given a low-degree polynomial mapping

$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy

$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

Alexey Milovanov

This text is a development of a preprint of Ankit Gupta.

We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$ circuits with bounded top fanin.

This approach is similar to Kayal-Saraf approach for depth-$3$ circuits. Kayal and Saraf based their ...
more >>>