Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Grigory Yaroslavtsev:

TR16-174 | 7th November 2016
Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

Linear Sketching over $\mathbb F_2$

Revisions: 5 , Comments: 2

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high ... more >>>

TR15-031 | 2nd March 2015
Marco Molinaro, David Woodruff, Grigory Yaroslavtsev

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity

Revisions: 1

We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes ... more >>>

TR13-036 | 13th March 2013
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

Lower Bounds for Testing Properties of Functions on Hypergrid Domains

Revisions: 1

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.
Our lower bounds also apply to the more restricted setting ... more >>>

ISSN 1433-8092 | Imprint