All reports by Author Shir Peleg:

__
TR23-074
| 14th May 2023
__

Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta#### Radical Sylvester-Gallai Theorem for Tuples of Quadratics

__
TR22-125
| 9th September 2022
__

Shir Peleg, Amir Shpilka, Ben Lee Volk#### Tensor Reconstruction Beyond Constant Rank

__
TR21-091
| 29th June 2021
__

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma#### Expander Random Walks: The General Case and Limitations

__
TR21-077
| 6th June 2021
__

Shir Peleg, Amir Shpilka, Ben Lee Volk#### Lower Bounds on Stabilizer Rank

Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta

We prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Han65, Shp20]. Hansen's theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen's theorem to the setting of quadratic forms ... more >>>

Shir Peleg, Amir Shpilka, Ben Lee Volk

We give reconstruction algorithms for subclasses of depth-$3$ arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:

1. ... more >>>

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, ... more >>>

Shir Peleg, Amir Shpilka, Ben Lee Volk

The stabilizer rank of a quantum state $\psi$ is the minimal $r$ such that $\left| \psi \right \rangle = \sum_{j=1}^r c_j \left|\varphi_j \right\rangle$ for $c_j \in \mathbb{C}$ and stabilizer states $\varphi_j$. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the ... more >>>