research
∙
02/19/2019
Fourier and Circulant Matrices are Not Rigid
The concept of matrix rigidity was first introduced by Valiant in [Val77...
share
research
∙
11/07/2018
Static Data Structure Lower Bounds Imply Rigidity
We show that static data structure lower bounds in the group (linear) mo...
research
∙
09/27/2018
Spanoids - an abstraction of spanning structures, and a barrier for LCCs
We introduce a simple logical inference structure we call a spanoid (gen...
research
∙
06/14/2018
A Sauer-Shelah-Perles Lemma for Sumsets
We show that any family of subsets A⊆ 2^[n] satisfies A≤ O(n^d/2), wher...
research
∙
08/04/2017