# Computer Science and Discrete Mathematics (CSDM)

## Crossing the logarithmic barrier for dynamic boolean data structure lower bounds

This paper proves the first super-logarithmic lower bounds on the cell-probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

## Lifting theorems in communication complexity and applications

Communication complexity studies the minimal amount of information two parties need to exchange to compute a joint function of their inputs. Results, especially lower bounds in this basic model found applications in many other areas of computer science.

## Rigorous RG: a provably efficient and possibly practical algorithm for simulating 1D quantum systems

## Bounds on roots of polynomials (and applications)

## Efficient empirical revenue maximization in single-parameter auction environments

## Computing a categorical Gromov-Witten invariant

## Noncommutative probability for computer scientists

## In pursuit of obfuscation

## A time-space lower bound for a large class of learning problems

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. As a special case, this gives a new proof for the time-space lower bound for parity learning [R16].