Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Mikołaj Boja´nczyk, Emanuela Merelli (Ed.)We initiate a systematic study of algorithms that are both differentiallyprivate and run in sublinear time for several problems in which the goal is to estimate natural graph parameters. Our main result is a differentiallyprivate $(1+\rho)$approximation algorithm for the problem of computing the average degree of a graph, for every $\rho>0$. The running time of the algorithm is roughly the same (for sparse graphs) as its nonprivate version proposed by Goldreich and Ron (Sublinear Algorithms, 2005). We also obtain the first differentiallyprivate sublineartime approximation algorithms for the maximum matching size and the minimum vertex cover size of a graph. An overarching technique we employ is the notion of \emph{coupled global sensitivity} of randomized algorithms. Related variants of this notion of sensitivity have been used in the literature in adhoc ways. Here we formalize the notion and develop it as a unifying framework for privacy analysis of randomized approximation algorithms.

Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal tradeoffs between their redundancy and their errorcorrection capabilities, as well as {\em efficient} encoding and decoding algorithms. In many applications, polynomial running time may still be prohibitively expensive, which has motivated the study of codes with {\em superefficient} decoding algorithms. These have led to the wellstudied notions of Locally Decodable Codes (LDCs) and Locally Correctable Codes (LCCs). Inspired by these notions, Ostrovsky and PaskinCherniavsky (Information Theoretic Security, 2015) generalized Hamming LDCs to insertions and deletions. To the best of our knowledge, these are the only known results that study the analogues of Hamming LDCs in channels performing insertions and deletions. Here we continue the study of insdel codes that admit local algorithms. Specifically, we reprove the results of Ostrovsky and PaskinCherniavsky for insdel LDCs using a different set of techniques. We also observe that the techniques extend to constructions of LCCs. Specifically, we obtain insdel LDCs and LCCs from their Hamming LDCs and LCCs analogues, respectively. The rate and errorcorrection capability blow up only by a constant factor, while the query complexity blows up by a poly log factor in themore »

We study the problem of finding all $k$periods of a length$n$ string $S$, presented as a data stream. $S$ is said to have $k$period $p$ if its prefix of length $np$ differs from its suffix of length $np$ in at most $k$ locations. We give a onepass streaming algorithm that computes the $k$periods of a string $S$ using $\poly(k, \log n)$ bits of space, for $k$periods of length at most $\frac{n}{2}$. We also present a twopass streaming algorithm that computes $k$periods of $S$ using $\poly(k, \log n)$ bits of space, regardless of period length. We complement these results with comparable lower bounds.

Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in latticebased communication and cryptography. In this work, we initiate a systematic study of {\em local testing} for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following: \begin{enumerate} \item We show that in order to achieve low query complexity, it is sufficient to design onesided nonadaptive {\em canonical} tests. This result is akin to, and based on an analogous result for errorcorrecting codes due to BenSasson \etal\ (SIAM J. Computing 35(1) pp121). \item We demonstrate upper and lower bounds on the query complexity of local testing for membership in {\em code formula} lattices. We instantiate our results for code formula lattices constructed from ReedMuller codes to obtain nearlymatching upper and lower bounds on the query complexity of testing such lattices. \item We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing lowdimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in {\em knapsack lattices}. On the other hand, we showmore »