You are currently browsing the category archive for the ‘accepted papers’ category.

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.

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]

Papers accepted for STOC include:

- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance [Chakrabarti, Regev]
- Near-Optimal Private Approximation Protocols via a Black-Box Transformation [Woodruff]
- Fast Moment Estimation in Data Streams in Optimal Space [Kane, Nelson, Porat, Woodruff]
- Privacy-preserving Statistical Estimation with Optimal Convergence Rates [Smith]
- Subspace Embeddings for the L_1-norm with Applications [Sohler, Woodruff]
- A Unified Framework for Approximating and Clustering Data [Feldman, Langberg]

Papers accepted for STACS include:

- Spectral Sparsification in the Semi-Streaming Setting [Levin, Kelner]
- Polynomial Fitting of Data Streams with Applications to Codeword Testing [McGregor, Rudra, Uurtamo]

The list of accepted papers for SODA has been posted. Stream papers include:

- The Streaming Complexity of Cycle Counting, Sorting By Reversals, and Other Problems [Verbin, Yu]
- Efficient Sketches for the Set Query Problem [Price]
- Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Low Error [Jayram, Woodruff]
- Streaming k-means on Well-Clusterable Data [Braverman, Meyerson, Shindler, Ostrovsky, Roytman, Tagiku]

If your paper ended up on the list of excepted papers, remember that the STACS deadline is this Friday. And there’s always STOC.

Luca has just announced the accepted papers for FOCS. Papers that have direct or indirect connections to streaming and communication complexity include:

- Lower Bounds for Near Neighbor Search via Metric Expansion [Panigrahy, Talwar, Wieder]
- The Limits of Two-Party Differential Privacy [McGregor, Mironov, Pitassi, Reingold, Talwar, Vadhan]
- Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition [Chakrabarti, Cormode, Kondapally, McGregor]
- Bounded Independence Fools Degree-2 Threshold Functions [Diakonikolas, Kane, Nelson]
- Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity [Andoni, Krauthgamer, Onak]
- Sublinear Optimization for Machine Learning [Clarkson, Hazan, Woodruff]
- The Coin Problem, and Pseudorandomness for Branching Programs [Brody, Verbin]

Abstracts can be found here. More pdfs can be found at My Brain is Open.

Accepted papers from ESA and RANDOM/APPROX are out. Papers related to streaming include:

- Streaming Graph Computations with a Helpful Advisor [Thaler, Cormode, Mitzenmacher]
- On-line Embeddings [Indyk, Magen, Sidiropoulos, Zouzias]
- Periodicity in Streams [Ergun, Jowhari, Saglam]
- Better Gap-Hamming Lower Bounds via Better Round Elimination [Brody, Chakrabarti, Regev, Vidick, de Wolf]

The accepted list for ICALP has been posted. Some of the papers relevant to the blog include:

- Data Stream Algorithms for Codeword Testing [Rudra, Uurtamo]
- Streaming algorithms for independent sets [Halldorsson, Halldorsson, Losievskaja, Szegedy]
- Choosing, Agreeing, and Eliminating in Communication Complexity [Beimel, Ben Daniel, Kushilevitz, Weinreb]
- Composition theorems in communication complexity [Lee, Zhang]
- Testing Non-uniform k-wise Independent Distributions over Product Spaces [Rubinfeld, Xie]

Also, following on from my post about the PODS accepted papers, I wanted to note that the best paper was awarded to [Kane, Nelson, Woodruff] for their data streams paper on “An Optimal Algorithm for the Distinct Elements Problem.” Congrats!

**BONUS! A Challenge…** So you’re done with your FOCS submission? Well, don’t dawdle, there are plenty of deadlines over the next week to keep you occupied. Who needs sleep?

- ESA 2010 on 12th April
- MASSIVE 2010 on 14th April (a conference on algorithms for massive data sets brought to you by the MADALGO massive)
- TAXES 2010 on 15th April
- RANDOM and APPROX 2010 on 18th April

A beer/beverage-of-choice to anyone who makes them all!

Some nifty stream results in the accepted list from PODS:

- Optimal Sampling From Distributed Streams [Cormode, Yi, Zhang, Muthukrishnan]
- Fast Manhattan Sketches in Data Streams [Nelson, Woodruff]
- An Optimal Algorithm for the Distinct Elements Problem [Kane, Nelson, Woodruff]

I also like the look of the PODS tutorial on “Information Complexity” that will be presented by T. S. Jayram. This is one of the most important techniques for proving stream and communication lower bounds. Check out the abstract here.

UPDATE: “An Optimal Algorithm for the Distinct Elements Problem” received the PODS Best Paper Award. Congrats!

[FWIW, I also had a paper accepted but it was on differential privacy rather than data streams. Perhaps I should add “secrecy” as a semi-suitable synonym to subjoin to the blog’s “streams, sketches, samples, sensing” tagline. Or would that be silly?]

The accepted list from STOC has just been posted (thanks My Brain is Open). Streaming and communication complexity papers that caught my eye include:

- Recognizing well-parenthesized expressions in the streaming model [Magniez, Mathieu, Nayak]
- Measuring Independence of Datasets [Braverman, Ostrovsky]
- How to Compress Interactive Communication [Barak, Braverman, Chen, Rao]
- A Strong Direct Product Theorem for Disjointness [Klauck]

Godel’s Lost Letter had a great post about [Magniez, Mathieu, Nayak] and I previously mentioned the main problem from [Braverman, Ostrovsky]. I have a soft spot for both papers because they resolve open problems from a couple of my previous papers (this one and that one if you’re interested.)

## Recent Comments