Next

__
TR21-007
| 14th January 2021
__

Sai Sandeep#### Almost Optimal Inapproximability of Multidimensional Packing Problems

__
TR21-006
| 18th January 2021
__

Susanna de Rezende, Jakob NordstrÃ¶m, Marc Vinyals#### How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

__
TR21-005
| 13th January 2021
__

Anindya De, Elchanan Mossel, Joe Neeman#### Robust testing of low-dimensional functions

Next

Sai Sandeep

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>

Susanna de Rezende, Jakob NordstrÃ¶m, Marc Vinyals

We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large ... more >>>

Anindya De, Elchanan Mossel, Joe Neeman

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. ... more >>>

Next