Poster Abstracts

Zhenming LiuOn Continuous Counting and Learning in a Distributed System

Abstract Consider a distributed system that consists of a coordinator node connected to multiple sites. Items from a data stream arrive to the system one by one, and are arbitrarily distributed to different sites. The goal of the system is to continuously track a function of the items received so far within a prescribed relative accuracy and at the lowest possible communication cost. This class of problems is called a continual distributed stream monitoring.

In this talk we will focus on two problems from this class. We will first discuss the count tracking problem (counter), which is an important building block for other more complex algorithms. The goal of the counter is to keep a track of the sum of all the items from the stream at all times. We show that for a class of input loads a randomized algorithm guarantees to track the count accurately with high probability and has the expected communication cost that is sublinear in both data size and the number of sites. We also establish matching lower bounds. We then illustrate how our non-monotonic counter can be applied to solve more complex problems, such as to track the second frequency moment and the Bayesian linear regression of the input stream.

We will next discuss the online non-stochastic experts problem in the continual distributed setting. Here, at each time-step, one of the sites has to pick one expert from the set of experts, and then the same site receives information about payoffs of all experts for that round. The goal of the distributed system is to minimize regret with respect to the optimal choice in hindsight, while simultaneously keeping communication to the minimum. This problem is well understood in the centralized setting, but the communication trade-off in the distributed setting is unknown. The two extreme solutions to this problem are to communicate with everyone after each payoff, and not to communicate at all. We will discuss how to achieve the trade-off between these two approaches. We will present an algorithm that achieves a non-trivial trade-off and show the difficulties of further improving its performance.

Brief bio Z. Liu's research interests are distributed streaming algorithms and stochastic processes. He is a postdoctoral research associate at Princeton University in the Computer Science Department.
Yang LiuQuantum and randomized communication complexity of XOR functions in the SMP model

Abstract Quantum and randomized communication complexity of XOR functions in the SMP model.
Brief bio Y. Liu's research interests include communication complexity, streaming algorithms, sketching, and coding theory. Yang is a graduate student at the Chinese University of Hong Kong.
Jesse HartloffCombining traitor tracing and revocation in a single broadcast encryption scheme

Abstract Combining traitor tracing and revocation in a single broadcast encryption scheme (joint with Jimmy Dobler).
Brief bio J. Hartloff's research interests include coding, algorithms, biometrics, and cryptography. He is a graduate student at University at Buffalo in the Computer Science Department.
Mert SaglamOn the communication complexity of sparse set disjointness and exists-equal problems

Abstract Improving on the works of Hastad and Widgerson from 1997, we give a new protocol for the two player communication problem set disjointness. The protocol determines if the sets players receive are disjoint by communicating O(k log^{(r)} k) bits over r rounds. Our main contribution is a matching lower bound: we show this protocol is optimal in a very strong sense. The core of our proof is an analysis of error-correction properties of an adversarially chosen large subset of [t]^n, i.e., the set of n dimensional vectors over alphabet [1..t]
Brief bio M. Saglam's research interests include Streaming algorithms, Small space computation, Communication complexity. He is a graduate student at the University of Washington in the Computer Science Department.
Keith LevinSpoken term discovery

Abstract The task of automatically identifying words or phrases in speech data, requires that we search a large amount of audio for repeated acoustic patterns. Previous work used randomized hashing and approximate nearest neighbor search to enable fast audio search over hundreds of hours of speech data without the need for statistical acoustic or language models. We explore ways to extend this approach so that our randomized hashing functions capture linguistic information such as phonetic context, in the hope that such information improves both the speed and accuracy of audio search.
Brief bio K. Levin is at Johns Hopkins University and his interests are in streaming algorithms, pattern recognition, and compressed sensing.
Michael CrouchGraph Algorithms in the Sliding Windows Model

Abstract We present the first graph algorithms in the sliding window model, where older data elements are considered \"stale\" and should be implicitly ignored. We construct basic graph synopses such as combinatorial sparsifiers and spanners, and we show approximations for the sizes of graph matchings and minimum spanning trees.
Brief bio M. Crouch is at the University of Massachusetts at Amherst and his interests are in streaming algorithms, communication complexity, and complexity theory.
Hanzhong LiuHigh dimensional inference and model selection

Abstract coming soon.
Brief bio H. Liu is at the University of California, Berkeley and is interested in high dimensional inference and model selection.
Dehui YangOn Projection Matrix Optimization for Compressive Sensing Systems

Abstract We consider the problem of designing the projection matrix $\\Phi$ for the compressive sensing (CS) system in which the dictionary $\\Psi$ is assumed to be given. The optimal projection matrix design is formulated in terms of finding those $\\Phi$, such that the Frobenius norm of the difference between the Gram matrix of the equivalent dictionary $\\Phi \\Psi$ and the identity matrix is minimized. A class of the solution is derived in a closed-form. Moreover, it is observed that the solution set is characterized by an arbitrary orthonormal matrix. This freedom is then used to further enhance the performance of the CS system by minimizing the coherence between the atoms of the equivalent dictionary. Simulations are carried out and show that the proposed approach significantly improves the signal recovery accuracy of the CS system.
Brief bio D. Yang is at the Colorado School of Mines and is interested in low-dimensional models for signal processing.