Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR16-093 | 4th June 2016
Cyrus Rashtchian

Bounded Matrix Rigidity and John's Theorem

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 >>>

TR15-189 | 25th November 2015
Shay Moran, Cyrus Rashtchian

Shattered Sets and the Hilbert Function

Revisions: 2

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 >>>

ISSN 1433-8092 | Imprint