Sofya Raskhodnikova

SODA Conference 2025 Conference Paper

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions

• Jane Lange
• Ephraim Linder
• Sofya Raskhodnikova
• Arsen Vasilyan

We study local filters for the Lipschitz property of real-valued functions f: V → [0, r ], where the Lipschitz property is defined with respect to an arbitrary undirected graph G = ( V, E ). We give nearly optimal local Lipschitz filters both with respect to ℓ 1 -distance and ℓ 0 -distance. Previous work only considered unbounded- range functions over [ n ] d. Jha and Raskhodnikova (SICOMP ‘13) gave an algorithm for such functions with lookup complexity exponential in d, which Awasthi et al. (ACM Trans. Comput. Theory) showed was necessary in this setting. We demonstrate that important applications of local Lipschitz filters can be accomplished with filters for functions whose range is bounded in [0, r ]. For functions f: [ n ] d → [0, r ], we achieve running time ( d r log n ) O (log r ) for the ℓ 1 -respecting filter and d O(r) polylog n for the ℓ 0 -respecting filter, thus circumventing the lower bound. Our local filters provide a novel Lipschitz extension that can be implemented locally. Furthermore, we show that our algorithms are nearly optimal in terms of the dependence on r for the domain {0, 1} d, an important special case of the domain [ n ] d. In addition, our lower bound resolves an open question of Awasthi et al. , removing one of the conditions necessary for their lower bound for general range. We prove our lower bound via a reduction from distribution-free Lipschitz testing and a new technique for proving hardness for adaptive algorithms. Finally, we provide two applications of our local filters to real-valued functions, with no restrictions on the range. In the first application, we use them in conjunction with the Laplace mechanism for differential privacy and noisy binary search to provide mechanisms for privately releasing outputs of black-box functions, even in the presence of malicious clients. In particular, our differentially private mechanism for arbitrary real-valued functions runs in time 2 polylog min( r, nd ) and, for honest clients, has accuracy comparable to the Laplace mechanism for Lipschitz functions, up to a factor of O (log min( r, nd )). In the second application, we use our local filters to obtain the first nontrivial tolerant tester for the Lipschitz property. Our tester works for functions of the form f: {0, 1} d → ℝ, makes queries, and has tolerance ratio 2. 01. Our applications demonstrate that local filters for bounded-range functions can be applied to construct efficient algorithms for arbitrary real-valued functions.

STOC Conference 2025 Conference Paper

Privately Evaluating Untrusted Black-Box Functions

• Ephraim Linder
• Sofya Raskhodnikova
• Adam Smith 0006
• Thomas Steinke 0002

We provide tools for sharing sensitive data in situations when the data curator does not know in advance what questions an (untrusted) analyst might want to ask about the data. The analyst can specify a program that they want the curator to run on the dataset. We model the program as a black-box function f . We study differentially private algorithms, called privacy wrappers , that, given black-box access to a real-valued function f and a sensitive dataset x , output an accurate approximation to f ( x ). The dataset x is modeled as a finite subset of a possibly infinite set U , in which each entry x represents data of one individual. A privacy wrapper calls f on the dataset x and on some subsets of x and returns either an approximation to f ( x ) or a nonresponse symbol ⊥. The wrapper may also use additional information (that is, parameters) provided by the analyst, but differential privacy is required for all values of these parameters. Correct setting of these parameters will ensure better accuracy of the privacy wrapper. The bottleneck in the running time of our privacy wrappers is the number of calls to f , which we refer to as queries . Our goal is to design privacy wrappers with high accuracy and small query complexity. We introduce a novel setting, called the automated sensitivity detection setting, where the analyst supplies only the black-box function f and the intended (finite) range of f . In contrast, in the previously considered setting, which we refer to as the claimed sensitivity bound setting, the analyst also supplies additional parameters that describe the sensitivity of f . We design privacy wrappers for both settings and show that our wrappers are nearly optimal in terms of accuracy, locality (i.e., the depth of the local neighborhood of the dataset x they explore), and query complexity. In the claimed sensitivity bound setting, we provide the first accuracy guarantees that have no dependence on the size of the universe U . We also re-interpret and analyze previous constructions in our framework, and use them as comparison points. In addition to addressing the black-box privacy problem, our private mechanisms provide feasibility results for differentially private release of general classes of functions.

NeurIPS Conference 2023 Conference Paper

Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation

• Palak Jain
• Iden Kalemaj
• Sofya Raskhodnikova
• Satchit Sivakumar
• Adam Smith

Privacy is a central challenge for systems that learn from sensitive data sets, especially when a system's outputs must be continuously updated to reflect changing data. We consider the achievable error for differentially private continual release of a basic statistic---the number of distinct items---in a stream where items may be both inserted and deleted (the turnstile model). With only insertions, existing algorithms have additive error just polylogarithmic in the length of the stream $T$. We uncover a much richer landscape in the turnstile model, even without considering memory restrictions. We show that every differentially private mechanism that handles insertions and deletions has worst-case additive error at least $T^{1/4}$ even under a relatively weak, event-level privacy definition. Then, we identify a parameter of the input stream, its maximum flippancy, that is low for natural data streams and for which we give tight parameterized error guarantees. Specifically, the maximum flippancy is the largest number of times that the contribution of a single item to the distinct elements count changes over the course of the stream. We present an item-level differentially private mechanism that, for all turnstile streams with maximum flippancy $w$, continually outputs the number of distinct elements with an $O(\sqrt{w} \cdot \mathsf{poly}\log T)$ additive error, without requiring prior knowledge of $w$. We prove that this is the best achievable error bound that depends only on $w$, for a large range of values of $w$. When $w$ is small, the error of our mechanism is similar to the polylogarithmic in $T$ error in the insertion-only setting, bypassing the hardness in the turnstile model.

ICML Conference 2023 Conference Paper

The Price of Differential Privacy under Continual Observation

• Palak Jain 0004
• Sofya Raskhodnikova
• Satchit Sivakumar
• Adam Smith 0006

We study the accuracy of differentially private mechanisms in the continual release model. A continual release mechanism receives a sensitive dataset as a stream of $T$ inputs and produces, after receiving each input, an output that is accurate for all the inputs received so far. We provide the first strong lower bounds on the error of continual release mechanisms. In particular, for two fundamental problems that are closely related to empirical risk minimization and widely studied and used in the standard (batch) model, we prove that the worst case error of every continual release algorithm is $\tilde \Omega(T^{1/3})$ times larger than that of the best batch algorithm. Previous work shows only a $\Omega(\log T)$ gap between the worst case error achievable in these two models. We also formulate a model that allows for adaptively selected inputs, thus capturing dependencies that arise in many applications of continual release. Even though, in general, both privacy and accuracy are harder to attain in this model, we show that our lower bounds are matched by the error of simple algorithms that work even for adaptively selected inputs.

FOCS Conference 2022 Conference Paper

Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs

• Laxman Dhulipala
• Quanquan C. Liu
• Sofya Raskhodnikova
• Jessica Shi 0001
• Julian Shun
• Shangdi Yu

Differentially private algorithms allow large-scale data analytics while preserving user privacy. Designing such algorithms for graph data is gaining importance with the growth of large networks that model various (sensitive) relationships between individuals. While there exists a rich history of important literature in this space, to the best of our knowledge, no results formalize a relationship between certain parallel and distributed graph algorithms and differentially private graph analysis. In this paper, we define locally adjustable graph algorithms and show that algorithms of this type can be transformed into differentially private algorithms. Our formalization is motivated by a set of results that we present in the central and local models of differential privacy for a number of problems, including k-core decomposition, low out-degree ordering, and densest subgraphs. First, we design an $\varepsilon$-edge differentially private (DP) algorithm that returns a subset of nodes that induce a subgraph of density at least $ \frac{D^{*}}{1+\eta}-O(\operatorname{poly}(\log n)/\varepsilon)$, where $D^{*}$ is the density of the densest subgraph in the input graph (for any constant $\eta\gt 0$). This algorithm achieves a two-fold improvement on the multiplicative approximation factor of the previously best-known private densest subgraph algorithms while maintaining a near-linear runtime. Then, we present an $\varepsilon$-locally edge differentially private (LEDP) algorithm for k-core decompositions. Our LEDP algorithm provides approximates the core numbers (for any constant $\eta\gt 0$) with $(2+\eta)$ multiplicative and $O(\operatorname{poly}(\log n)/\varepsilon)$ additive error. This is the first differentially private algorithm that outputs private k-core decomposition statistics. We also modify our algorithm to return a differentially private low out-degree ordering of the nodes, where orienting the edges from nodes earlier in the ordering to nodes later in the ordering results in out-degree at most $O(d+$ poly $(\log n)/\varepsilon$) (where d is the degeneracy of the graph). A small modification to the algorithm also yields a $\varepsilon$-LEDP algorithm for $(4+\eta, O(\operatorname{poly}(\log n)/\varepsilon))$ approximate densest subgraph (which returns both the set of nodes in the subgraph and its density). Our algorithm uses $O(\log^{2}n)$ rounds of communication between the curator and individual nodes.

NeurIPS Conference 2021 Conference Paper

Differentially Private Sampling from Distributions

• Sofya Raskhodnikova
• Satchit Sivakumar
• Adam Smith
• Marika Swanberg

We initiate an investigation of private sampling from distributions. Given a dataset with $n$ independent observations from an unknown distribution $P$, a sampling algorithm must output a single observation from a distribution that is close in total variation distance to $P$ while satisfying differential privacy. Sampling abstracts the goal of generating small amounts of realistic-looking data. We provide tight upper and lower bounds for the dataset size needed for this task for three natural families of distributions: arbitrary distributions on $\{1, \ldots, k\}$, arbitrary product distributions on $\{0, 1\}^d$, and product distributions on on $\{0, 1\}^d$ with bias in each coordinate bounded away from 0 and 1. We demonstrate that, in some parameter regimes, private sampling requires asymptotically fewer observations than learning a description of $P$ nonprivately; in other regimes, however, private sampling proves to be as difficult as private learning. Notably, for some classes of distributions, the overhead in the number of observations needed for private learning compared to non-private learning is completely captured by the number of observations needed for private sampling.

SODA Conference 2020 Conference Paper

Approximating the Distance to Monotonicity of Boolean Functions

• Ramesh Krishnan S. Pallavoor
• Sofya Raskhodnikova
• Erik Waingarten

We design a nonadaptive algorithm that, given a Boolean function f: {0, 1} n → {0, 1} which is α-far from monotone, makes poly( n, 1/α) queries and returns an estimate that, with high probability, is an -approximation to the distance of f to monotonicity. Furthermore, we show that for any constant k > 0, approximating the distance to monotonicity up to n 1/2− k -factor requires nonadaptive queries, thereby ruling out a poly( n, 1/α)-query nonadaptive algorithm for such approximations. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. Approximating the distance to a property is closely related to tolerantly testing that property. Our lower bound stands in contrast to standard (non-tolerant) testing of monotonicity that can be done nonadaptively with queries. We obtain our lower bound by proving an analogous bound for erasure-resilient testers. An α-erasure-resilient tester for a desired property gets oracle access to a function that has at most an α fraction of values erased. The tester has to accept (with probability at least 2/3) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 2/3) if every completion of erasures results in a function that is ε -far from having the property. Our method yields the same lower bounds for unateness and being a k -junta. These lower bounds improve exponentially on the existing lower bounds for these properties.

TCS Journal 2020 Journal Article

Bipartite graphs of small readability

• Rayan Chikhi
• Vladan Jovičić
• Stefan Kratsch
• Paul Medvedev
• Martin Milanič
• Sofya Raskhodnikova
• Nithin Varma

We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bioinformatics. The behavior of the parameter is poorly understood. The complexity of computing it is open and it is not known whether the decision version of the problem is in NP. The only known upper bound on the readability of a bipartite graph (following from a work of Braga and Meidanis, LATIN 2002) is exponential in the maximum degree of the graph. Graphs that arise in bioinformatics applications have low readability. In this paper, we focus on graph families with readability o ( n ), where n is the number of vertices. We show that the readability of n-vertex bipartite chain graphs is between Ω ( log ⁡ n ) and O ( n ). We give an efficiently testable characterization of bipartite graphs of readability at most 2 and completely determine the readability of grids, showing in particular that their readability never exceeds 3. As a consequence, we obtain a polynomial time algorithm to determine the readability of induced subgraphs of grids. One of the highlights of our techniques is the appearance of Euler's totient function in the analysis of the readability of bipartite chain graphs. We also develop a new technique for proving lower bounds on readability, which is applicable to dense graphs with a large number of distinct degrees.

FOCS Conference 2016 Conference Paper

Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism

• Sofya Raskhodnikova
• Adam Smith 0006

Lipschitz extensions were proposed as a tool for designing differentially private algorithms for approximating graph statistics. However, efficiently computable Lipschitz extensions were known only for 1-dimensional functions (that is, functions that output a single real value). We study efficiently computable Lipschitz extensions for multi-dimensional (that is, vector-valued) functions on graphs. We show that, unlike for 1-dimensional functions, Lipschitz extensions of higher-dimensional functions on graphs do not always exist, even with a non-unit stretch. We design Lipschitz extensions with small stretch for the sorted degree list and degree distribution of a graph, viewed as functions from the space of graphs equipped with the node distance into real space equipped with l1. Our extensions are from the space of bounded-degree graphs to the space of arbitrary graphs. The extensions use convex programming and are efficiently computable. We also develop a new tool for employing Lipschitz extensions in differentially private algorithms that operate with no prior knowledge of the graph (and, in particular, no knowledge of the degree bound). Specifically, we generalize the exponential mechanism, a widely used tool in data privacy. The exponential mechanism is given a collection of score functions that map datasets to real values. It returns the name of the function with nearly minimum value on the dataset. Our generalized exponential mechanism provides better accuracy than the standard exponential mechanism when the sensitivity of an optimal score function is much smaller than the maximum sensitivity over all score functions. We use our Lipschitz extensions and the generalized exponential mechanism to design a node differentially private algorithm for approximating the degree distribution of a sensitive graph. Our algorithm is much more accurate than those from previous work. In particular, our algorithm is accurate on all graphs whose degree distributions decay at least as fast as those of "scale-free" graphs. Using our methodology, we also obtain more accurate node-private algorithms for 1-dimensional statistics.

STOC Conference 2014 Conference Paper

L p -testing

• Piotr Berman
• Sofya Raskhodnikova
• Grigory Yaroslavtsev

I&C Journal 2013 Journal Article

Approximation algorithms for spanner problems and Directed Steiner Forest

• Piotr Berman
• Arnab Bhattacharyya
• Konstantin Makarychev
• Sofya Raskhodnikova
• Grigory Yaroslavtsev

We present an O ( n log n ) -approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G = ( V, E ) with nonnegative edge lengths d: E → R ⩾ 0 and a stretch k ⩾ 1, a subgraph H = ( V, E H ) is a k-spanner of G if for every edge ( s, t ) ∈ E, the graph H contains a path from s to t of length at most k ⋅ d ( s, t ). The previous best approximation ratio was O ˜ ( n 2 / 3 ), due to Dinitz and Krauthgamer (STOC ʼ11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from O ˜ ( n ) to O ( n 1 / 3 log n ). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS ʼ10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and Krauthgamerʼs lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O ( n 1 / 3 log n ) -approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O ( n ) -approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O ( n 2 / 3 + ϵ ) for any constant ϵ > 0, which improves the O ( n ϵ ⋅ min ( n 4 / 5, m 2 / 3 ) ) ratio due to Feldman, Kortsarz and Nutov (JCSSʼ12).

SODA Conference 2013 Conference Paper

Learning pseudo-Boolean k -DNF and submodular functions

• Sofya Raskhodnikova
• Grigory Yaroslavtsev

We prove that any submodular function f: {0, 1} n → {0, 1, …, k } can be represented as a pseudo-Boolean 2 k -DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Håstad's switching lemma holds for pseudo-Boolean k -DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k -DNFs to pseudo-Boolean k -DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f: {0, 1} n → {0, 1, …, k }. Our algorithm runs in time polynomial in n, k O ( k log k /ε) and log(1/δ) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC ′11), Gupta, Hardt, Roth, Ullman (STOC ′11), Cheraghchi, Klivans, Kothari, Lee (SODA ′12)] implies only n O ( k ) query complexity for learning submodular functions in this setting, for fixed ε and δ. Our learning algorithm implies a property tester for submodularity of functions f: {0, 1} n → {0, …, k } with query complexity polynomial in n for k = O ((log n /log log n ) 1/2 ) and constant proximity parameter ε.

FOCS Conference 2011 Conference Paper

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

• Madhav Jha
• Sofya Raskhodnikova

A function f: D → R has Lipschitz constant c if d R (f(x), f(y)) ≤ c·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 that rescaling by a factor of 1/c converts a function with a Lipschitz constant c into a Lipschitz function.) In other words, Lipschitz functions are not very sensitive to small changes in the input. We initiate the study of testing and local reconstruction of the Lipschitz property of functions. A property tester has to distinguish functions with the property (in this case, Lipschitz) from functions that are ϵ-far from having the property, that is, differ from every function with the property on at least an ϵ fraction of the domain. A local filter reconstructs an arbitrary function f to ensure that the reconstructed function g has the desired property (in this case, is Lipschitz), changing f only when necessary. A local filter is given a function f and a query x and, after looking up the value of f on a small number of points, it has to output g(x) for some function g, which has the desired property and does not depend on x. If f has the property, g must be equal to f. We consider functions over domains of the form {1, ⋯, n} d equipped with ℓ 1 distance. We design efficient testers of the Lipschitz property for functions of the form f: {1, 2} d → δZ, where δ ∈ (0, 1] and δZ is the set of integer multiples of δ, and of the form f: {1, ⋯, n} d → R, where R is (discretely) metrically convex. We also present an efficient local filter of the Lipschitz property for functions of the form f: {1, ⋯, n} d → R. We give corresponding lower bounds on the complexity of testing and local reconstruction. The algorithms we design have applications to program analysis and data privacy. The application to privacy is based on the fact that a function f of entries in a database of sensitive information can be released with noise of magnitude proportional to a Lipschitz constant of f, while preserving the privacy of individuals whose data is stored in the database (Dwork, McSherry, Nissim and Smith, TCC 2006). We give a differentially private mechanism, based on local filters, for releasing a function f when a purported Lipschitz constant of f is provided by a distrusted client. We show that when no reliable Lipschitz constant of f is given, previously known differentially private mechanisms have either a substantially higher running time or a higher expected error, for a large class of symmetric functions f.

SODA Conference 2009 Conference Paper

Transitive-closure spanners

• Arnab Bhattacharyya 0001
• Elena Grigorescu
• Kyomin Jung
• Sofya Raskhodnikova
• David P. Woodruff

We define the notion of a transitive-closure spanner of a directed graph. Given a directed graph G = ( V, E ) and an integer k ≥ 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. These spanners were studied implicitly in access control, property testing, and data structures, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of TC-spanners. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We study the approximability of the size of the sparsest k -TC-spanner for a given digraph. Our technical contributions fall into three categories: algorithms for general digraphs, inapproximability results, and structural bounds for a specific graph family which imply an efficient algorithm with a good approximation ratio for that family. Algorithms. We present two efficient deterministic algorithms that find k -TC-spanners of near optimal size. The first algorithm gives an -approximation for k > 2. Our method, based on a combination of convex programming and sampling, yields the first sublinear approximation ratios for (1) D irected k -S panner, a well-studied generalization of k -TC-S panner, and (2) its variants C lient /S erver D irected k -S panner, and the k -D iameter S panning S ubgraph. This resolves the main open question of Elkin and Peleg (IPCO, 2001). The second algorithm, specific to the k -TC-spanner problem, gives an -approximation. It shows that for, our problem has a provably better approximation ratio than D irected k -S panner and its variants. This algorithm also resolves an open question of Hesse (SODA, 2003).

FOCS Conference 2008 Conference Paper

What Can We Learn Privately?

• Shiva Prasad Kasiviswanathan
• Homin K. Lee
• Kobbi Nissim
• Sofya Raskhodnikova
• Adam Smith 0006

Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask: what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in the contexts where aggregate information is released about a database containing sensitive information about individuals. We present several basic results that demonstrate general feasibility of private learning and relate several models previously studied separately in the contexts of privacy and standard learning.

STOC Conference 2007 Conference Paper

Smooth sensitivity and sampling in private data analysis

• Kobbi Nissim
• Sofya Raskhodnikova
• Adam Smith 0006

We introduce a new, generic framework for private data analysis.The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains.Our framework allows one to release functions f of the data withinstance-based additive noise. That is, the noise magnitude is determined not only by the function we want to release, but also bythe database itself. One of the challenges is to ensure that the noise magnitude does not leak information about the database. To address that, we calibrate the noise magnitude to the smoothsensitivity of f on the database x --- a measure of variabilityof f in the neighborhood of the instance x . The new frameworkgreatly expands the applicability of output perturbation, a technique for protecting individuals' privacy by adding a smallamount of random noise to the released statistics. To our knowledge, this is the first formal analysis of the effect of instance-basednoise in the context of data privacy. Our framework raises many interesting algorithmic questions. Namely,to apply the framework one must compute or approximate the smoothsensitivity of f on x . We show how to do this efficiently for several different functions, including the median and the cost ofthe minimum spanning tree. We also give a generic procedure based on sampling that allows one to release f(x) accurately on manydatabases x . This procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of f is known orwhen f is given as a black box. We illustrate the procedure by applying it to k -SED ( k -means) clustering and learning mixtures of Gaussians.

FOCS Conference 2007 Conference Paper

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

• Sofya Raskhodnikova
• Dana Ron
• Amir Shpilka
• Adam Smith 0006

We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least 1/n. This problem is closely related to the problem of approximating the number of distinct elements in a sequence of length n. For both problems, we prove a nearly linear in n lower bound on the query complexity, applicable even for approximation with additive error. At the heart of the lower bound is a construction of two positive integer random variables. X 1 and X 2, with very different expectations and the following condition on the first k moments: E[X 1 ]/E[X 2 ] = E[X 1 2 ]/E[X 2 2 ] =. .. = E[X 1 k ]/E[X 2 k ]. Our lower bound method is also applicable to other problems. In particular, it gives new lower bounds for the sample complexity of (1) approximating the entropy of a distribution and (2) approximating how well a given string is compressed by the Lempel-Ziv scheme.

STOC Conference 2003 Conference Paper

A sublinear algorithm for weakly approximating edit distance

• Tugkan Batu
• Funda Ergün
• Joe Kilian
• Avner Magen
• Sofya Raskhodnikova
• Ronitt Rubinfeld
• Rahul Sami

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns " CLOSE " if their edit distance is O(n Α ), and " FAR " if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(n max(Α/2, 2Α - 1\) ) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(n Α/2 ) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most n Α from those with edit distance at least n/6.

SODA Conference 2003 Conference Paper

Lower bounds for embedding edit distance into normed spaces

• Alexandr Andoni
• Michel Deza
• Anupam Gupta 0001
• Piotr Indyk
• Sofya Raskhodnikova

STOC Conference 2003 Conference Paper

Some 3CNF properties are hard to test

• Eli Ben-Sasson
• Prahladh Harsha
• Sofya Raskhodnikova

For a boolean formula φ on n variables, the associated property P φ is the collection of n-bit strings that satisfy φ. 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(√n) queries[7]. Notice that for every bad instance (i.e. an assignment that does not satisfy φ) there is a 3-bit query that witnesses this fact. Nevertheless, finding such a short witness requires a linear number of queries, even for assignments that are very far from satisfying.We provide sufficient conditions for linear properties to be hard to test, and in the course of the proof include a couple of observations which are of independent interest.

STOC Conference 2002 Conference Paper

Monotonicity testing over general poset domains

• Eldar Fischer
• Eric Lehman
• Ilan Newman
• Sofya Raskhodnikova
• Ronitt Rubinfeld
• Alex Samorodnitsky

The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are 'far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n -dimensional hypercube {1,…, m } n . These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2 -CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest.