Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Sofya Raskhodnikova:

TR17-111 | 2nd June 2017
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube

A Boolean function $f:\{0,1\}^d \to \{0,1\}$ is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadaptive, one-sided error unateness tester must make $\Omega(\frac{d}{\log d})$ queries. This result improves upon the $\Omega(\frac{d}{\log^2 d})$ lower bound for the same class of ... more >>>

TR17-103 | 12th June 2017
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

Parameterized Property Testing of Functions

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us ... more >>>

TR17-049 | 14th March 2017
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

We study the problem of testing unateness of functions $f:\{0,1\}^d \to \mathbb{R}.$ We give a $O(\frac{d}{\epsilon} \cdot \log\frac{d}{\epsilon})$-query nonadaptive tester and a $O(\frac{d}{\epsilon})$-query adaptive tester and show that both testers are optimal for a fixed distance parameter $\epsilon$. Previously known unateness testers worked only for Boolean functions, and their query ... 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 >>>

TR12-076 | 12th June 2012
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

Testing Lipschitz Functions on Hypergrid Domains

A function $f(x_1, ... , x_d)$, where each input is an integer from 1 to $n$ and output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small ... more >>>

TR12-075 | 12th June 2012
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

Limitations of Local Filters of Lipschitz and Monotone Functions

We study local filters for two properties of functions $f:\B^d\to \mathbb{R}$: the Lipschitz property and monotonicity. A local filter with additive error $a$ is a randomized algorithm that is given black-box access to a function $f$ and a query point $x$ in the domain of $f$. Its output is a ... more >>>

TR11-057 | 15th April 2011
Madhav Jha, Sofya Raskhodnikova

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

Revisions: 2

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>

TR09-046 | 9th May 2009
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Transitive-Closure Spanners of the Hypercube and the Hypergrid

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

TR06-089 | 16th July 2006
Sofya Raskhodnikova, Adam Smith

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

We show that in the bounded degree model for graph property testing,
adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>

TR05-125 | 2nd November 2005
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

TR03-006 | 23rd January 2003
Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

3CNF Properties are Hard to Test

For a boolean formula \phi on n variables, the associated property
P_\phi is the collection of n-bit strings that satisfy \phi. We prove
that there are 3CNF properties that require a linear number of queries,
even for adaptive tests. This contrasts with 2CNF properties
that are testable with O(\sqrt{n}) ... more >>>

TR99-017 | 4th June 1999
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Improved Testing Algorithms for Monotonicity.

Revisions: 1

We present improved algorithms for testing monotonicity of functions.
Namely, given the ability to query an unknown function $f$, where
$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a
monotone $f$, and rejects $f$ with high probability if it is $\e$-far
from being monotone (i.e., every ... more >>>

ISSN 1433-8092 | Imprint