Speakers Open problem session (pdf) Yaniv Erlich Title: Burn the textbook! Challenges in applying compressed sensing approaches for human diseases Yaniv Erlich, Whitehead Institute for Biomedical Research, Nine Cambridge Center, Cambridge, MA 02142 Revealing the genetic factors that impact human disease susceptibility is one of the major challenges of modern biology. Accumulating lines of evidence have highlighted the pivotal role of rare genetic variations in a wide variety diseases, from hypertension through schizophrenia to autism. Rare variations in large cohorts can be thought of as a sparse signal. Thus, their detection is amenable to a Compressed Sensing (CS) protocol. We have developed an ultra-cost effective strategy called “DNA Sudoku” to profile rare variations in large cohorts using a CS approach. As a test case, we identified rare genetic variations in a batch of 40,000 bacterial colonies by sensing only 1,900 combinatorial pools. We recovered 98.2% of the signal correctly. In the past two years, our CS approach for bacteria has been extensively used by the industry for biotechnological applications. Adapting DNA Sudoku to human genetics poses new and exciting theoretical challenges to the ‘traditional’ compressed sensing approach. These challenges come in three categories: incorporating a-priori genetic information, technical constraints, and the small experiment problem. In my talk, I will present in detail the challenges and will call for an extended CS theory to address the challenges. Bio: Yaniv Erlich received his Bachelor's degree from Tel-Aviv University at Israel in 2006 and his Ph.D. from the Waston School of Biological Sciences at Cold Spring Harbor Laboratory, NY, in 2010. He is currently a Principal Investigator/Andria and Paul Heafy Family Fellow at the Whitehead Institute for Biomedical Research. Yaniv Erlich's research interests are computational human genetics. He has extensive experience in developing new algorithms for high throughputs sequencing and to detect disease genes. In two of his studies, he identified the genetic basis of devastating genetic disorders. The Erlich lab works on a wide range of topics including developing Compressed Sensing approach to identify rare genetic variations, devising new algorithms for personal genomics, and using Web 2.0 information for genetic studies. Dr. Erlich is the recipient of Harold M. Weintraub award, the IEEE/ACM-CS HPC award, Goldberg-Lindsay Fellowship, Wolf foundation scholarship for Excellence in exact science, Emmanuel Ax scholarship, and was selected as one of 2010 Tomorrow's PIs team of Genome Technology. Anna Gilbert Title: A Survey of Sparse Approximation (pdf)   Venkat Guruswami Title: Coding theory in pseudorandomness: A tale of two applications Abstract:There is a rich interplay between coding theory and computational complexity theory that has enriched both disciplines over the years. In particular, error-correcting codes have been instrumental in several advances in the subject of pseudorandomness, leading to explicit constructions of objects (such as expander graphs, randomness extractors, pseudorandom generators, matrices, etc.) with desirable properties similar to those achieved by random objects. This talk will survey some applications of coding-theoretic ideas in pseudorandomness from recent years, showcasing two examples: the construction of lossless expanders and randomness extractors from a variant of Reed-Solomon codes, and the construction of Euclidean sections and compressed sensing matrices from expander codes. Bio: Venkatesan Guruswami received his Bachelor's degree from the Indian Institute of Technology at Madras in 1997 and his Ph.D. from the Massachusetts Institute of Technology in 2001. He is currently an Associate Professor in the Computer Science Department at Carnegie Mellon University. From 2002-09, he was a faculty member in the Department of Computer Science and Engineering at the University of Washington. Venkat was a Miller Research Fellow at the University of California, Berkeley during 2001-02, and was a member in the School of Mathematics, Institute for Advanced Study during 2007-08. Venkat Guruswami's research interests span a broad array of topics including the theory of error-correcting codes, approximation algorithms and non-approximability results for NP-hard optimization problems, explicit combinatorial constructions and pseudorandomness, probabilistically checkable proofs, computational complexity theory, and algebraic algorithms. Dr. Guruswami currently serves on the editorial boards of the SIAM Journal on Computing, IEEE Transactions on Information Theory, and the ACM Transactions on Computation Theory. He is recipient of the Packard Fellowship, Sloan Fellowship, NSF CAREER award, ACM's Doctoral Dissertation Award, and the IEEE Information Theory Society Paper Award. Brett Hemenway Title: Error Correction (pdf) Piotr Indyk Title: Simple and Practical Algorithm for Sparse Fourier Transform We consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coefficients of the Fourier transform of x. The problem is of key interest in several areas, including audio/image/video compression, signal processing, data analytics and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal processing, notably Gaussian and Dolph-Chebyshev filters. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity k for which the algorithm is faster than FFT, both in theory and practice. Bio: Bio: Piotr Indyk is a Professor of Electrical Engineering and Computer Science at MIT (as of July 1). He joined MIT in 2000, after earning PhD from Stanford University. Earlier, he received Magister degree from Uniwersytet Warszawski in 1995. His research interests include high-dimensional computational geometry, sketching and streaming algorithms, sparse recovery and compressive sensing. He has received the NSF CAREER Award, Sloan Fellowship and Packard Fellowship. He is an Associate Editor for the IEEE Transactions on Signal Processing.   Dick Lipton Shachar Lovett Title: Pseudorandomness - tutorial Abstract: I would give an introduction to pseudorandomness focusing on 3 concrete examples: limited independence, expander graphs and derandomizing small space computations.   Andrew McGregor Title: Data Streams Tutorial Abstract: In this brief tutorial you'll be presented with a sequence of definitions, results, and techniques that relate to data stream algorithms. Your task is to make sense of this data subject to the constraints that a) you have limited memory, b) you don't get to control the order in which the data arrives, and c) the data may arrive very quickly. Perhaps randomization and approximation will help. Bio: Andrew McGregor is an Assistant Professor at the University of Massachusetts, Amherst. He received a B.A. degree and Certificate of Advance Study in Mathematics from the University of Cambridge and a Ph.D. from the University of Pennsylvania. He also spent a couple of years as a post-doc at UC San Diego and Microsoft Research SVC. He enjoys all areas of theoretical computer science but is particularly interested in data stream algorithms, linear sketching, and communication complexity. Olgica Milenkovic Eric Price Title: On the Power of Adaptivity in Sparse Recovery Abstract: The goal of (stable) sparse recovery is to recover a K-sparse approximation x* of a vector x in R^N from M linear measurements of x. A common formulation is to recover x* such that ||x-x*||_2 < C min_{K-sparse x'} ||x-x'||_2 for some constant C with 3/4 probability over the choice of measurements. It is known that this is possible with M = O(K log (N/K)) non-adaptive measurements and that this bound is tight. In this paper, we show that with /adaptive/ measurements, where the choice of each successive measurement can depend on the results of previous measurements, we can reduce the number of measurements to M = O(K log log (N/K)). These are the first results showing asymptotic improvement on M using adaptivity. This is joint work with Piotr Indyk and David Woodruff. Mike Saks, Rutgers University Title: Approximating the longest increasing subsequence in polylogarithmic time Bio: Michael Saks has worked in a number of areas of theory of computing and discrete mathematics. His first love is lower bounds, but sometimes reality forces him to think about algorithms. Abstract: Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Simple O(n log n) algorithms, based on dynamic programming, are known for solving this problem exactly on arrays of length n. In this talk I'll discuss recent work of C. Seshadhri and myself, in which we consider the problem of approximating the LIS in time polylogarithmic in the input size. Specifically for any chosen constant c > 0, the algorithm outputs an approximation to the length of the LIS that (with high probability) is accurate to within an additive cn. Previously, the best known polylogarithmic time algorithms could achieve only an additive n/2 approximation. It is easy to see that approximation based on uniform random sampling of the input can give a very poor approximation to the LIS. Our algorithm uses random sampling that is both non-uniform and adaptive (that is the choice of points to sample depends on values observed previously). Dieter van Melkebeek Title: Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses Abstract: Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer d>=3 and positive real epsilon we show that if satisfiability for n-variable d-CNF formulas has a protocol of cost O(n^{d-epsilon}) then the polynomial-time hierarchy collapses. The result is tight as there exists a trivial protocol for epsilon = 0. Under the standard complexity-theoretic hypothesis that the polynomial-time hierarchy does not collapse, the result implies tight lower bounds for parameters of interest in several areas, including sparsification, probabilistically checkable proofs, instance compression, and kernelization in parameterized complexity. By reduction similar results hold for other NP-complete problems. The proofs hinge on the existence of high-density subsets of the integers without nontrivial arithmetic progressions of length three. Joint work with Holger Dell. Bio: Dieter van Melkebeek obtained his undergraduate degree in Computer Science Engineering and Applied Mathematics from the Katholieke Universiteit Leuven (Belgium) and a PhD in Computer Science from the University of Chicago. After a postdoctoral position at DIMACS and the Institute for Advanced Study (Princeton), he joined the faculty at the University of Wisconsin-Madison, where he currently is an associate professor of Computer Sciences. Dieter van Melkebeek received the 1999 ACM Doctoral Dissertation Award. He serves on the editorials boards of SIAM Journal on Computing, Computational Complexity, ACM Transactions on Computation Theory, and Electronic Colloquium on Computational Complexity. Ryan Williams Title: Non-Uniform ACC Circuit Lower Bounds Abstract: The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m > 1 is an arbitrary constant. I will outline a proof that there is a function in NEXP (nondeterministic exponential time) which does not have polynomial size ACC circuits. (It was open for 20+ years whether all of EXP^{NP} had depth-3 polynomial size circuits made out of only MOD6 gates.) This talk will try to focus on aspects of the proof that are of maximum interest to the workshop attendees. Virginia Vassilevska Williams Title: Path, matrix and triangle problems -- subcubic algorithms and equivalences Abstract: Many graph and matrix problems studied in optimization have relatively simple algorithms which run in time cubic in the number of vertices or rows. Some examples include matrix multiplication and all-pairs shortest paths. In 1969, Strassen gave a clever truly subcubic algorithm for matrix multiplication, and this insight has since lead to faster algorithms for many of the graph and matrix problems solvable in cubic time. Nevertheless, several stubborn problems remain for which the best known running time is essentially cubic. The prototypical of these problems is all-pairs shortest paths. Other stubborn problems include the minimum weight cycle (girth) problem, the replacement paths problem, the second shortest simple path problem, and the simplest of them all, the problem of detecting a negative weight triangle in a graph. We are able to show, perhaps surprisingly, that all these problems are equivalent, in the sense that if one has a truly subcubic algorithm, then all of them do. In this talk I will give an overview of our results, trying to highlight some open problems that may be of interest to the workshop attendees. Bio: Virginia Vassilevska Williams is a Computing Innovations Fellow at the University of California, Berkeley hosted by Prof. Satish Rao. Her main interests lie in theoretical computer science and in computational social choice. Virginia obtained her B.S. degree in mathematics and engineering and applied science from the California Institute of Technology in 2003, and her Ph.D. in computer science from Carnegie Mellon University in 2008 under the guidance of Prof. Guy Blelloch. In the 2008-2009 academic year she was a member at the Institute for Advanced Study in Princeton. David Woodruff Title: (1+eps)-Approximate Sparse Recovery Abstract: In compressed sensing there is an n-dimensional signal x, we compute Ax for a sketching matrix A, and from this we output a signal y for which |x-y|_p <= C |x-x_[k]|_p, where x_[k] denotes the k-sparse signal which agrees with x on its largest k entries. In applications it is important that C = 1+eps for a small eps. The number of rows required of A for constant probability of success is not well understood as a function of eps. We give new algorithms and lower bounds in terms of n, k, and eps for the important cases of p = 1 and p = 2. The bounds are Theta~(k/eps^{p/2}). If we require that y itself be k-sparse, the bounds are Theta~(k/eps^p). This shows the distinction between sparse and non-sparse outputs is fundamental. Joint work with Eric Price. David Zuckerman Title: Pseudorandom Generators for Polynomial Threshold Functions and Combinatorial Shapes Abstract: In this talk we discuss two related constructions of pseudorandom generators (PRGs). The first is a PRG for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length (log n)/eps^{O(d)} fooling degree d PTFs with error at most eps. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error eps. For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter eps and obtain a PRG with seed-length O(log n + log^2(1/eps)). Previously, only PRGs with seed length O(log n log^2(1/eps)/eps^2) were known for halfspaces. The main theme of our constructions and analysis is the use of invariance principles to construct pseudorandom generators. We also introduce the notion of monotone read-once branching programs, which is key to improving the dependence on the error rate eps for halfspaces. Our second PRG is for "combinatorial shapes," which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function f:[m]^n to {0,1}$ is an (m,n)-combinatorial shape if there exist subsets A_1,…,A_n of [m] and a symmetric function h:{0,1}^n to {0,1} such that f(x_1,…,x_n) = h(1_{A_1}(x_1),\ldots,1_{A_n}(x_n)). Our generator uses seed length O(log m + log n + log^2(1/\eps)) to get error eps. When m =2, this gives the first generator of seed length O(\log n) which fools all weight-based tests, meaning that the distribution of the weight of any subset is eps-close to the appropriate binomial distribution in statistical distance. For our proof we give a simple lemma which allows us to convert closeness in Kolmogorov (cdf) distance to closeness in statistical distance. The first result is joint with Raghu Meka, and the second is joint with Parikshit Gopalan, Raghu Meka, and Omer Reingold. Bio: David Zuckerman holds an Endowed Professorship in the Computer Science Department at the University of Texas at Austin. He earned his A.B. in Mathematics from Harvard University in 1987 and his Ph.D. from the University of California at Berkeley in 1991. His research focuses on the role of randomness in computation, especially pseudorandomness and randomness extraction. His awards include a Guggenheim Fellowship, a Radcliffe Fellowship, a Packard Fellowship, a Sloan Fellowship, and an NSF Young Investigator Award.   Organizers Anna Gilbert, Martin Strauss, Atri Rudra, Hung Ngo, Ely Porat, S. Muthukrishnan Sponsors Department of Mathematics, Institute for Mathematics and its Applications (IMA), NSF, and Michigan Math Journal For website problems, contact Webmaster