All reports by Author Cyrus Rashtchian:

__
TR19-180
| 6th December 2019
__

Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi#### Covering Codes for Insertions and Deletions

Revisions: 1

__
TR16-093
| 4th June 2016
__

Cyrus Rashtchian#### Bounded Matrix Rigidity and John's Theorem

__
TR15-189
| 25th November 2015
__

Shay Moran, Cyrus Rashtchian#### Shattered Sets and the Hilbert Function

Revisions: 2

Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the ... more >>>

Cyrus Rashtchian

Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by ... more >>>

Shay Moran, Cyrus Rashtchian

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>>