SODA accepts…

That time of year again… the list of accepted papers for SODA has been posted. Some of the papers that might be of (direct or indirect*) interest to the streaming/sketching crowd include:

• Sublinear Time, Measurement-Optimal, Sparse Recovery For All [Porat, Strauss]
• Analyzing Graph Structure via Linear Measurements [Ahn, Guha, McGregor]
• Sparser Johnson-Lindenstrauss Transforms [Kane, Nelson]
• On the communication and streaming complexity of maximum bipartite matching [Goel, Kapralov, Khanna]
• The Shifting Sands Algorithm [McGregor, Valiant]
• Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy [Phillips, Verbin, Zhang]
• A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size [Onak, Ron, Rosen, Rubinfeld]
• Optimal Column-Based Low-Rank Matrix Reconstruction [Guruswami, Sinop]
• Simple and Practical Algorithm for Sparse Fourier Transform [Hassanieh, Indyk, Katabi, Price]
• Sketching Valuation Functions [Badanidiyuru, Dobzinski, Fu, Kleinberg, Nisan, Roughgarden]
• Width of Points in the Streaming Model [Andoni, Nguyen]

(*) I’m not entirely sure what metric I’m using to determine “indirect interest” but rest assured, once I know, I’ll let you know. There also might be some additions to the above list once I’ve seen the actual papers.

BONUS! Comments from the chair… The PC chair, Yuval Rabani, discusses the selection process. Other posts on the selected papers include this and that and can be found here and there.

Slides, Questions, and a Little Trick

A few weeks ago I attended a workshop on Coding, Complexity, and Sparsity at the University of Michigan. Thanks to the organizers (Anna Gilbert, Martin Strauss, Atri Rudra, Hung Ngo, Ely Porat, and S. Muthukrishnan) for not only putting together a great program but also for treating the speakers like celebrities! The place swarmed with autograph hunters, roads were closed, and security kept the paparazzi at bay… at least I think this was all for our benefit.

I gave a brief tutorial on data streams and my slides can be found here if you’re interested. One of the results I went through was for the -sampling problem introduced by [Cormode, Muthukrishnan, Rozenbaum] and [Frahling, Indyk, Sohler]. See also [Monemizadeh and Woodruff] and [Jowhari, Saglam, Tardos]. Here the set-up is that you see a sequence of updates to a length vector . These updates can increment or decrement entries of although for the talk I assumed that the entires themselves always remained non-negative. E.g., for the sequence

would result in the vector . An algorithm for -sampling should return an element chosen uniformly at random from the set . See the slides (or the original papers) for an algorithm using space. Anyhow, during the talk I mentioned there was a simple trick to determine whether

.

But I decided to leave it as an easy puzzle for which I’d give the answer later. Of course, I forgot. See the comments to this post for the answer.

Other things to check out:

• I just noticed that Martin Strauss has typed up some of the open questions from the workshop.
• Dick Lipton blogged about the workshop talk on (1+eps)-Approximate Sparse Recovery by David Woodruff, joint work with Eric Price.

Open Problems: The Bertinoro and Kanpur Lists

Piotr Indyk, Ilan Newman, Krzysztof Onak, and I have just finished up a new open problems list. Here it is! It mainly covers topics in data streams and property testing but there’s also some other cool stuff. The list is compiled from the recent Bertinoro workshop and the slightly less recent Kanpur workshop.

(Cartoon from XKCD obviously.)

RANDOM/APPROX accepts…

Streaming and sketching papers in the RANDOM/APPROX accepted list include:

• Streaming Algorithms with One-Sided Estimation [Brody, Woodruff]
• Everywhere-Tight Information Cost Tradeoffs for Augmented Index [Chakrabarti, Kondapally]
• Almost Optimal Explicit Johnson-Lindenstrauss Transformations [Kane, Meka, Nelson]
• Periodicity and Cyclic Shifts via Linear Sketches [Crouch, McGregor]
• Sparse recovery with partial support knowledge [Do Ba, Indyk]

Sublinear Algorithms: Day 5b

The sun is setting on La Rocca di Bertinoro. The pasta has run dry and the wifi signal is fading. Theorists are scurrying towards taxis and preparing themselves for their overnight flights. Sublinear Algorithms 2011 is all over. But fear not! There are still three more talks to report…

First Robi Krauthgamer discussed “Polylogarithmic Approximation for Edit Distance” [Andoni, Krauthgamer, Onak]. Given two length sequences, the edit distance is the minimum number of character operations (inserts, deletions, substitutions) that are sufficient to transform the first string into the latter. Masek and Paterson showed that the edit distance could be computed exactly in time. Recent work has focused on approximation in near-linear time. Robi presented an algorithm that achieves a approximation in time. This was a significant improvement over the previous best of approximation. [Andoni, Krauthgamer, Onak] is also the paper that sowed the seeds for the precision-sampling technique that Alex presented on Wednesday (one of my favorite talks from the workshop).

Next, Artur Czumaj gave a talk entitled “Planar Graphs: Random Walks and Bipartiteness Testing” [Czumaj, Monemizadeh, Onak, Sohler]. This is one of the few results for property testing in general graphs, i.e., not dense graphs or graphs with constant degree. In the dense graph model you can query entries of the adjacency matrix and need to accept input graphs with the property of interest and reject graphs if entries of the adjacency matrix would need to be changed in order to have a graph that has the property. After about ten years of research we have a very good understanding of what is possible in this model. Attention has since focussed on the bounded-degree adjacency list model where every node has degree at most and we need to reject graphs if changes would be necessary to satisfy the property. In both models, testing bipartiteness has been an important problem: in the dense graph model the complexity is constant (we’re treating as constant) and in the bounded-degree model the complexity is In the general graph model, there is no bound on the max-degree and we may query the graph by a) asking for the -th neighbor of a specific node or b) asking for the degree of a specific node. In practice it seems like asking for a random neighbor of a specific node is sufficiently powerful. Artur showed that it was possible to test bipartiteness in planar graphs with constant queries.

The very last talk was given Ronitt Rubinfeld on “Testing Collections of Properties” [Levi, Ron, Rubinfeld]. Previous work on property testing of distributions considered single distributions or pairs of distributions: we’d take iid samples from the distributions and try to determine if, e.g., the distributions where identical or far from identical (i.e., the distance between the distributions is at least .). Ronitt considered a more general model in which there are distributions over and a (known or unknown) distribution over . On querying the distributions we get where and . The goals included determining whether all are identical or whether they can be clustered into clusters such that within a cluster, all distributions are close. Results included a tight bound if of for the question of testing if all distributions where identical. Using the observation that are independent iff all ‘s are equal, this also gives a tight lower bound for independence testing, resolving an open question from previous work.

BONUS! More Photos… Here are a few more photos from the workshop.

By day we’d listen to theory talks in the Fresco room…

By night we’d talk about theory over dinner…

On our afternoon off, we admired cathedrals and talked more theory.

Sublinear Algorithms: Day 5a

It’s the last day of Sublinear Algorithms 2011. Thanks to Artur Czumaj, Piotr Indyk, Ronitt Rubinfeld, and Robi Krauthgamer for organizing such a great workshop. Thanks also to all the guest bloggers (Jelani Nelson, Krzysztof Onak, Seshadhri, Piotr Indyk, Sariel Har-Peled) this week for doing such a great job. My only concern is that readers of this blog might start to expect posts of such a high quality. To minimize this risk, I’ll finish up the workshop blogging.

The day started with two property testing talks. First, Oded Lachish talked about “Testing a Language Accepted by a Fixed Boolean Formula”. Here we assume full knowledge of a formula and are given oracle access to an assignment of the variables. By querying only a few of the variable assignments we wish to distinguish between the cases when the assignment satisfies and the case when is far from doing so, i.e., all satisfying assignments differ in at least positions. Oded presented quasi-polynomial algorithms for a variety of cases including binary, read-once formula and binary, monotone and read-k-times formula.

Next up was Gilad Tsur who talked about “Approximating the Number of Relevant Variables in a Function” [Ron, Tsur]. Here there’s also a boolean formula but in contrast to the previous talk we don’t know . Rather, we can query the value of on inputs of our choosing. The goal is to multiplicatively estimate how many variables in the input actually play a role in determining the function. Unfortunately this is hard in general: consider a function that always a evaluates to 0 except on one specific input. However, Gilad showed it was possible for certain families of functions such as linear functions. He then considered the relaxation to distinguishing between the case when the number of relevant variables is at most , and the case in which it is far from any function in which the number of relevant variable is more than for some parameter .

After a short break, I talked about “Data Streams, Dyck Languages, and Detecting Dubious Data Structures” [Chakrabarti, Cormode, Kondapally, McGregor]. Here’s the problem… You are watching your friend interact with a priority queue: at each step she either inserts a new value into the queue or asks for the minimum value currently in the queue to be extracted. However, you’re suspicious that the priority queue may not always be extracting the correct minimum. Can you help your friend recognize when this happens without having to remember all the values she has inserted? In the talk we showed how this was possible. We also discussed recognizing whether a string of brackets was balanced and concluded that reading backwards can be a very useful skill. Slides are here.

Sublinear Algorithms: Day 4b

(Piotr reports on the last two talks of Day 4.)

After lunch, Christian Sohler served new results on property testing in hyperfinite graphs. A family of graphs is -hyperfinite if in any graph we can remove edges to obtain connected components of size at most k. For example, by planar separator theorem, planar graphs qualify for this distinction. In the talk, Christian focused on graphs of bounded degree and k.

Christian presented a number of results, including the following (and surprising) one: every property is testable on hyperfinite graphs. The basic idea is: for any graph G in the family, if we remove some edges from G, then the resulting graph G’ can be fully described as a distribution over graphs of size at most k and one can approximate this distribution by random sampling. One interesting implication of his work is that computing statistics of “graph motifs” in large networks (a popular tool in network analysis) is justified, since such statistics identify the graph itself.

The final talk of the day was by Oded Goldreich, who talked about sub-linear algorithms in graphs of bounded degree. He considered a model where one can ask for a specific (i.e., the i-th) neighbor of a given node. He considered the problem of *finding* (not just testing existence of) cycles and trees in a given graph. The first of them was a (roughly) -time algorithm for finding cycles in N-vertex graphs that are eps-far from being cycle free. One can also generalize this result to finding cycles of length at least k, for a fixed k. He also showed that one cannot do (much) better than is optimal. In contrast, he also gave constant time algorithms for finding trees of size at least k (for constant k).

The algorithms are based on the following observation linking one-sided property testing and finding structures with that property. Specifically, if such tester rejects a graph, it must have some “evidence” that the property does not hold. E.g., if we test for bipartiteness, then the violating structure is a non-bipartite graph. This leads to an algorithm that finds a desired structure.

To obtain an algorithm for finding cycles (or testing cycle freeness), he used a reduction to bipartite-ness testing. The idea is simple and very cute: for each each edge one replaces it by a 2-path with prob. 1/2, and keeps it intact otherwise. Clearly, any cycle-free graph is mapped into a cycle-free (and therefore bipartite) graph. The key observation is that a graph that is far from being cycle free is mapped into a graph that is far from being bipartite.

Sublinear Algorithms: Day 4a

(Piotr Indyk reports from Day 4 at Sublinear Algorithms. Includes contributions from Sariel Har Peled.)

The first session of the day was dedicated to distributed algorithms. It was headlined by Roger Wattenhofer, who gave a very nice overview of the area. Distributed algorithms have recently found applications in sub-linear world, e.g., see the talks on Monday. Distributed algorithms communicate along the edges of a graph, and the algorithm complexity is measured in rounds of communication.

The central character in Roger’s talk was the Maximal Independent Set (MIS) problem. Despite many years of research on this problem, some basic questions are still open (e.g., is there a deterministic algorithm with rounds?). Roger described a randomized algorithm that runs in rounds. The algorithm is local: a decision made at a given node depends only on actions of the nodes in its small neighborhood. He then proceeded to show that any algorithm for MIS requires at least rounds. The proof used Ramsey theory, which was a nice coincidence, given that a workshop on this topic was held in parallel. The lower bound in fact holds even for the line graph. Unfortunately (if you are a pessimist), for the line graph, there is a matching upper bound of . Therefore, to improve the lower bound one needs a richer class of instances. Roger showed a construction of graphs for which one can show a lower bound of or (for a closely related problem of vertex cover). The graph was highly unusual, in that it was “highly symmetric” and “asymmetric” at the same time.

The next talk, by Pierre Fraigniaud, was on local distributed decisions (i.e., decision problems). An example of such problem is coloring validation: given a coloring, is it legal ? Other examples include: checking whether there is at most one marked node, consensus, etc. In general, one can define the notion of distributed language, which is a decidable collection of configurations. A configuration is accepted iff it is accepted by all nodes. In other words, the configuration is not accepted if someone says it is not accepted. Pierre presented several results on randomized algorithms for decision making, including a strong derandomization result (under certain conditions).

In the next session, Ning Xie talked about Local Computation Algorithms. Here the idea is that you are given the input, and problem at hand generates a large output. For example, the input is a graph and the task at hand is computing a maximal independent set (MIS). Let us assume that we want to output only one specific bit of the output. The question is whether we can do it in sublinear time, and in a way that is consistent, if we decide to read i bits of the output in some arbitrary fashion (i.e., think about the algorithm here is a query data-structure that outputs the desired bit). Since we need to be consistent across different queries, if we are going to use randomness, it needs to be compactly represented. To this end, one uses k-pairwise independent sequence of random bits, which can be specified compactly with a “few” random bits, and one can generate a long sequence implicitly that can “cheat” many algorithms. Secondary, to get a local computation, we need to be able to break up the input quickly into small fragments, such that the fragment that defines the desired output (i.e., it contains the vertex we need to output if it is in the MIS or not). The main idea is now to use Beck’s constructive version of the Lovasz Local Lemma. For example, you run a randomized MIS algorithm (parallel version) for a small number of iterations, and then you run a greedy algorithm on each remaining connected component. The randomized algorithm here chooses a vertex to the independent set with probability ( is the degree in the given regular graph), and insert it if there are no collisions. After iterations, one proves that each remaining connected components is of size with high probability. Thus, we can simulate this algorithm locally given a query vertex, and run on the relevant connected component directly, getting a sublinear running time.

Yuichi Yoshida talked about constant-time approximation algorithms. He started from recalling the result of Raghavendra who showed that if the Unique Games Conjecture is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it. He then showed that similar results hold for constant- time approximation algorithms in the bounded-degree model. He obtained the results in three steps. First, he showed that for every CSP, one can construct an oracle that serves an access, in constant time, to a nearly optimal solution to a basic LP relaxation of the CSP. Using the oracle, he then showed a constant-time rounding scheme that achieves an approximation ratio coincident with the integrality gap of the basic LP. Finally, he gave a generic conversion from integrality gaps of basic LPs to hardness results.

The last talk before lunch was by Vladimir Braverman. He focused on the following class of streaming problems: given a function G, estimate a statistic that is equal to the sum, over all i, of terms , where is the number of times an element appears in the stream. Alon,Matias and Szegedy asked for which functions G it is possible to approximate this statistic using a single pass over the data and using poly-logarithmic memory. Vladimir showed a precise characterization for all monotonically increasing functions such that . He also introduced the method of recursive sketching that can be used, e.g., for approximating frequency moments.

Sublinear Algorithms: Day 3

(It’s Day 3 at Sublinear Algorithms and today Seshadhri is taking on blogging duties. Thanks Sesh!)

How to win Netflix: The survey of the day was “Compressed sensing to matrix completion and beyond” by Benjamin Recht. We started by discussing the basic matrix completion problem. Think of a matrix with the rows being movies and columns being Netflix users. The entries are the respective ratings. Suppose we got few of those ratings. Can we reasonably guess what the remaining entries are (and thereby win $1,000,000)? Formally, we have some matrix with some entries that are provided. We assume that the matrix is of low rank, meaning that , where is and is . The total number of free variables is , which for small is much smaller than the trivial bound of . Ben showed how techniques from compressed sensing could be used to attack this problem. His work gave a strong mathematical basis for certain heuristics that people used to solve such problems.

The importance of being coherent: That segued into the next talk, the only board talk of the workshop. Michael Mahoney talked about “Fast Approximations for Matrix Coherence and Statistical Leverage”. The concept of matrix coherence was introduced by compressed sensing folks (and the related notion of statistical leverage was present in earlier work by Michael). Consider a low-rank matrix M with the SVD (so is an matrix). The coherence is the maximum length of the projection of a standard basis vector onto the subspace spanned by the column vectors of . Formally,

where ‘s are the standard basis vectors and is the projection matrix onto . Michael talked about fast algorithms to compute this quantity, involving many linear algebraic manipulations and the recent fast Johnson-Lindenstrauss algorithms.

Big brother is watching you(r net traffic): After that, it was time for more traditional theory CS. Ely Porat talked about the classic problem of pattern matching in the streaming model. We are given a text T that we stream through, and a fixed pattern P of length . The fingerprinting algorithm of Karp-Rabin solves this problem, but requires space (since it basically maintains a sliding window of that size). Ely’s aim was to get this down to space, so that it would be appropriate to be blogged about here. He discussed some clever tricks to break this pattern into smaller sub-patterns, and using recursive fingerprinting schemes. One open problem was the get space lower bounds for this rather fundamental problem. He also mentioned the open problem of arranging his sabbatical for next year! Contact him for details.

How to find your Dacians: Alexandr Andoni gave a talk on “Precision and Sampling Algorithms”. The title was changed in real time to “Sublinear Algorithms via Precision Sampling” (and hence us attendees will never know what his original talk was about). After giving the motivation of the emperor of ancient Rome attempting to estimate the total number of Dacians in various provinces, Alex described a very cute sampling problem. We want to estimate the values of , where . Unfortunately, we can only get an estimate with a precision (so ). Our power is that we can choose the precisions but have to pay a cost of . How do we get an estimate satisfying

for constant ? Alex gave a nifty algorithm that has a cost of . This had applications in approximating the edit distance and also in streaming algorithms for large frequence moments.

How to bake your cake and eat it too: Nir Halman talked about “FPTASs for Stochastic Optimization Problems”. He introduced his talk using a baking analogy. First, he told us why the result (or cake) was going to be tasty, and then gave us the ingredients and recipe for the result. The problem was a stochastic version of the classic discrete knapsack problem. We have objects with the th object having volume and profit . The volume of the knapsack is , and we can solve this problem using dynamic programming is time. This is, of course, not polynomial, and the aim to get a -approximate solution and only pay an overhead of . The general framework of this result is strong enough to generate FPTASs for various versions of knapsack. One of the important cases Nir discussed was the stochastic version, where the volume comes from some explicitly known distribution. Another interesting case was the non-linear knapsack, where we can choose integer copies of each element.

The Arthur Cayley approach to odd-cycles: Asaf Shapira was next, telling us about “Testing Odd-Cycle Freeness of Boolean Functions”. Given a boolean function , an odd cycle a set of domain points such that is odd, and . This is a property that falls into the broad class of linear-invariant properties defined by simple constraints, but uncharacteristically, does not have an bounded constraint size. The main result is that this is testable in queries. Previous testers used general characterizations that gave the standard “tower of ” query complexity (Arnab talked about this result on the previous day). Asaf gave an excellent talk on relating this problem to testing bipartiteness of the Cayley graph of , which was really the heart of the result. He gave details on how to combine Fourier analysis ideas with a spectral approach, connecting the odd cycles in to the bipartiteness (or lack thereof) of the Cayley graph. This was done extremely well, so even though he walked us through the technical approach, the main ideas were very clear (a rather tough thing to do, IMHO). Finally, he also explained that there exists a canonical -query tester for this problem. This tester randomly samples and only queries the subspace spanned by them. It is an interesting open question whether for any linear invariant property that is testable in queries, there exists a canonical tester running in time.

After lunch, it was time for the excursion to the ancient town of Ravenna. The highlights were the mosaics of the Basilica of San Vitale and the final resting place of Dante Aligheri. These involved little to no new theoretical results, and hence the blog post shall end here.

Sublinear Algorithms: Day 2b

(Krzysztof Onak continues with Tuesday’s report for Sublinear Algorithms 2011.)

The second part of the day started with a session devoted to the Johnson-Lindenstrauss lemma. Nir Ailon presented different definitions of the problem. In the embedding version, one is given a set of Euclidean vectors in and wants to map them to , where d is small and the lengths of vectors are preserved up to a factor of . It is known that a random projection on dimensions is likely to produce such vectors. The downsides of using a random projection are that both the running time and the required amount of randomness are . Nir has addressed the challenge of reducing these requirements in his papers [Ailon, Chazelle] and [Ailon, Liberty]. His papers employ the Fourier transform and error correcting codes. Nir also discussed a more recently discovered connection between this problem and the restricted isometry property in compressed sensing. This connection resulted in new algorithms for efficiently computing the Johnson-Lindenstrauss transform.

Jelani Nelson presented his recent paper with Daniel Kane. The goal is to give a distribution over sparse matrices that provides the properties required in the Johnson Linderstrauss lemma and can be computed efficiently for sparse vectors. Jelani’s work is a followup to the paper of [Dasgupta, Kumar, Sarlos]. Jelani showed two extremely simple methods for constructing such matrices. In the first, one selects a small number of entries in each column and sets them at random to and . In the other one, one partitions the rows into a number of buckets corresponding to the number of desired non-zero entries in each column. Then in each column, one chooses one non-zero entry in each bucket. The main advantage over the approach of Dasgupta et al. is that this way collisions between non-zero entries are avoided. One of the main open questions is to both derandomize the Johnson-Lindenstrauss transform and make it run fast for sparse vectors. Jelani also mentioned a recent follow-up by [Braverman, Ostrovsky, Rabani].

You can spend the following coffee break admiring one of the well preserved frescoes:

Sofya Raskhodnikova talked about the problems of testing and reconstructing Lipschitz functions [Jha, Raskhodnikova 2011]. A function is -Lipschitz if for every , it holds . In the testing problem, one wants to verify that a function is approximately Lipschitz (for some fixed ). In the reconstruction problem, one wants to design a “local filter” through which the question to a function are asked. If the distance of to the property of being Lipschitz is , then the filter provides access to a function such that is Lipschitz, and the distance between and is not much larger than . Sofya mentioned applications of this research to program analysis and data privacy. In her presentation, she focused on the case when the domain is a hypercube. She gave both positive and negative results, where she mentioned that the latter were greatly simplified by techniques from a recent paper of [Blais, Brody, Matulef].

C. Seshadhri talked about his recent result on submod… Well, Sesh eventually decided to talk about approximating the length of the longest increasing subsequence [Saks, Seshadhri]. Sesh showed that an additive -approximation to the length of the longest increasing subsequence can be computed in time, where is the length of the sequence, is an arbitrary parameter, and is a constant. Before his work, the best known for which a sublinear algorithm was known was . This result also implies a better approximation algorithm for approximating the distance to monotonicity. Sesh showed a simplified version of his algorithm that runs in time. The algorithm mimics a dynamic program, recursively searches for good splitters, and applies some boosting to obtain a better approximation than . Sesh also complained that working on the paper and making everything work was painful. He even explicitely asked: “Was it really worth it?” Sesh, I think it was. This is a really nice result!

At night we experienced earthquakes, with the strongest of magnitude 3.1. It is pretty clear that they were caused by the impression left by today’s talks.

A screenshot from www.emsc-csem.org: