@inproceedings{LarsenNNT16,
  author = {Kasper Green Larsen and Jelani Nelson and Huy L. Nguy$\tilde{\hat{\mbox{e}}}$n and Mikkel Thorup},
  title = {Heavy hitters via cluster-preserving clustering},
  year = {2016},
  booktitle = {Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
}

@article{NelsonNW14,
  author = {Jelani Nelson and Huy L. Nguy$\tilde{\hat{\mbox{e}}}$n and David P. Woodruff},
  title = {On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation},
  journal = {Linear Algebra and its Applications, Special Issue on Sparse Approximate Solution of Linear Systems},
  volume = 441,
  pages = "152--167",
  year = 2014,
}

@inproceedings{AiHLW16,
  author    = {Yuqing Ai and
               Wei Hu and
               Yi Li and
               David P. Woodruff},
  title     = {New Characterizations in Turnstile Streams with Applications},
  booktitle = {Proceedings of the 31st Conference on Computational Complexity (CCC)},
  pages     = {20:1--20:22},
  year      = {2016},
}

@inproceedings{LiNW14,
  author    = {Yi Li and
               Huy L. Nguyen and
               David P. Woodruff},
  title     = {Turnstile streaming algorithms might as well be linear sketches},
  booktitle = {Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {174--183},
  year      = {2014},
}

@inproceedings{IndykW05,
  author    = {Piotr Indyk and
               David P. Woodruff},
  title     = {Optimal approximations of the frequency moments of data streams},
  booktitle = {Proceedings of the 37th Annual {ACM} Symposium on Theory of Computing (STOC)},
  pages     = {202--208},
  year      = {2005},
}

@article{Indyk06,
  author    = {Piotr Indyk},
  title     = {Stable distributions, pseudorandom generators, embeddings, and data stream computation},
  journal   = {J. {ACM}},
  volume    = {53},
  number    = {3},
  pages     = {307--323},
  year      = {2006},
}

@inproceedings{FlajoletFGM07,
  author = {Philippe Flajolet and \'{E}ric Fusy and Olivier Gandouet and Fr\'{e}d\'{e}ric Meunier},
  title = {HyperLogLog: the analysis of a near-optimal cardinality estimation algorith},
  booktitle = {Proceedings of the 2007 International Conference on the Analysis of Algorithms (AoFA)},
  year = 2007,
}

@article{BarYossefJKS04,
  author    = {Ziv Bar{-}Yossef and
               T. S. Jayram and
               Ravi Kumar and
               D. Sivakumar},
  title     = {An information statistics approach to data stream and communication complexity},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {68},
  number    = {4},
  pages     = {702--732},
  year      = {2004},
}

@inproceedings{BarYossefJKST02,
  author    = {Z. Bar-Yossef and T.S. Jayram and R. Kumar and D. Sivakumar and L. Trevisan},
  title     = "Counting Distinct Elements in a Data Stream",
  booktitle = "RANDOM",
  pages     = "1--10",
  year      = 2002
}

@article{Rudelson99,
  author = {Mark Rudelson},
  title = {Random vectors in the isotropic position},
  journal = {J. Functional Analysis},
  volume = 164,
  number = 1,
  pages = "60--72",
  year = 1999,
}

@article{AlonMS99,
  author = {Noga Alon and Yossi Matias and  Mario Szegedy},
  title = {The Space Complexity of Approximating the Frequency Moments},
  journal = {J. Comput. Syst. Sci.},
  volume = 58,
  number = 1,
  pages = "137--147",
  year = 1999,
}

@article{FlajoletM85,
  author = {Philippe Flajolet and G. Nigel Martin},
  title = {Probabilistic counting algorithms for data base applications},
  journal = {J. Comput. Syst. Sci.}, 
  volume = 31,
  number = 2,
  pages = "182--209",
  year = 1985,
}

@article{JayramKS08,
  author = {T. S. Jayram, Ravi Kumar, D. Sivakumar},
  title = {The One-Way Communication Complexity of Hamming Distance},
  journal = {Theory of Computing},
  volume = 4,
  number = 1,
  pages = "129--135",
  year = 2008,
}

@inproceedings{KaneNW10,
  author = {Daniel M. Kane and Jelani Nelson and David P. Woodruff},
  title = {An optimal algorithm for the distinct elements problem},
  booktitle = {Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS)}, 
  pages = "41--52",
  year = 2010,
}

@inproceedings{Woodruff04,
  author = {David P. Woodruff},
  title = {Optimal space lower bounds for all frequency moments},
  booktitle = {SODA}, 
  pages = "167--175",
  year = 2004,
}

@article{Alon03,
  author    = {Noga Alon},
  title     = {Problems and results in extremal combinatorics--{I}},
  journal   = {Discrete Mathematics},
  volume    = {273},
  number    = {1-3},
  pages     = {31--53},
  year      = {2003},
}

@article{LarsenN14,
  author    = {Kasper Green Larsen and
               Jelani Nelson},
  title     = {The {Johnson}-{Lindenstrauss} lemma is optimal for linear dimensionality reduction},
  journal   = {CoRR},
  volume    = {abs/1411.2404},
  year      = {2014},
}

@article{Morris78,
  author = {Robert Morris},
  title = {Counting Large Numbers of Events in Small Registers},
  journal = {Commun.  ACM},
  volume = 21,
  number = 10,
  pages = "840--842",
  year = 1978,
}

@inproceedings{KaneMN11,
  author    = {Daniel M. Kane and
               Raghu Meka and
               Jelani Nelson},
  title     = {Almost Optimal Explicit {Johnson}-{Lindenstrauss} Families},
  booktitle = {RANDOM},
  pages     = {628--639},
  year      = {2011},
}

@article{JayramW13,
  author    = {T. S. Jayram and
               David P. Woodruff},
  title     = {Optimal Bounds for {Johnson}-{Lindenstrauss} Transforms and Streaming Problems with Subconstant Error},
  journal   = {{ACM} Transactions on Algorithms},
  volume    = {9},
  number    = {3},
  pages     = {26},
  year      = {2013},
}

@article{RudelsonV13,
  author = {Mark Rudelson and Roman Vershynin},
  title = {Hanson-{W}right inequality and sub-gaussian concentration},
  journal   = {arXiv},
  volume    = {abs/1306.2872},
  year = 2013,
}

@article{HansonW71,
    AUTHOR = {David Lee Hanson and Farroll Tim Wright},
     TITLE = {A bound on tail probabilities for quadratic forms in
              independent random variables},
   JOURNAL = {Ann. Math. Statist.},
  FJOURNAL = {Annals of Mathematical Statistics},
    VOLUME = {42},
      YEAR = {1971},
     PAGES = {1079--1083},
      ISSN = {0003-4851},
   MRCLASS = {60.30},
  MRNUMBER = {0279864 (43 \#5585)},
MRREVIEWER = {T. M. Liggett},
}

@book {LedouxT91,
    AUTHOR = {Michel Ledoux and Michel Talagrand},
     TITLE = {Probability in {B}anach spaces},
 PUBLISHER = {Springer-Verlag},
   ADDRESS = {Berlin},
      YEAR = {1991},
}

@BOOK{PenaG99,
  author = {Victor de la Pe\~{n}a and Evarist Gin\'{e}},
  title = {Decoupling: From dependence to independence},
  series = {Probability and its Applications},
  address = {New York},
  publisher = {Springer-Verlag},
  year = 1999,
}

@inproceedings{DiakonikolasKN10,
  author    = {Ilias Diakonikolas and
               Daniel M. Kane and
               Jelani Nelson},
  title     = {Bounded Independence Fools Degree-2 Threshold Functions},
  booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science (FOCS)},
  pages     = {11--20},
  year      = {2010},
}

@article{KaneN14,
  author    = {Daniel M. Kane and
               Jelani Nelson},
  title     = {Sparser {Johnson}-{Lindenstrauss} transforms},
  journal = {Journal of the ACM},
  volume = 61,
  number = 1,
  pages = 4,
  year = 2014,
}

@article{MendelsonPTJ07,
  author    = {Shahar Mendelson and Alain Pajor and Nicole Tomczak-Jaegermann},
  title     = {Reconstruction and subgaussian operators in asymptotic geometric analysis},
  journal   = {Geometric and Functional Analysis},
  volume    = 17,
  pages     = "1248--1282",
  year      = 2007,
}

@article{Gordon88,
  author = {Yehoram Gordon},
  title = {On {Milman's} inequality and random subspaces which escape through a mesh in $\mathbb{R}^n$},
  journal = {Geometric Aspects of Functional Analysis},
  publisher = {Springer-Verlag Lecture Notes 1317},
  pages = "84--106",
  year = 1988,
}

@misc{Lee,
  author = {James R. Lee},
  title = {Notes on Gaussian processes and majorizing measures},
  url = {\url{http://homes.cs.washington.edu/~jrl/mm.pdf}}
}

@article{CohenNW15,
  author    = {Michael B. Cohen and
               Jelani Nelson and
               David P. Woodruff},
  title     = {Optimal approximate matrix product in terms of stable rank},
  journal   = {CoRR},
  volume    = {abs/1507.02268},
  year      = {2015},
}

@article{CormodeM05,
  author    = {Graham Cormode and
               S. Muthukrishnan},
  title     = {An improved data stream summary: the count-min sketch and its applications},
  journal   = {J. Algorithms},
  volume    = {55},
  number    = {1},
  pages     = {58--75},
  year      = {2005},
}

@article{AilonC09,
  author    = {Nir Ailon and
               Bernard Chazelle},
  title     = {The Fast {Johnson}--{Lindenstrauss} Transform and Approximate Nearest Neighbors},
  journal   = {{SIAM} J. Comput.},
  volume    = {39},
  number    = {1},
  pages     = {302--322},
  year      = {2009},
}

@inproceedings{Sarlos06,
  author    = {Tam{\'{a}}s Sarl{\'{o}}s},
  title     = {Improved Approximation Algorithms for Large Matrices via Random Projections},
  booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
               2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
  pages     = {143--152},
  year      = {2006},
}

@inproceedings{NelsonN13,
  author    = {Jelani Nelson and
               Huy L. Nguy$\tilde{\hat{\mbox{e}}}$n},
  title     = {{OSNAP:} Faster Numerical Linear Algebra Algorithms via Sparser Subspace
               Embeddings},
  booktitle = {Proceedings of the 54th Annual {IEEE} Symposium on Foundations of Computer Science (FOCS)},
  pages     = {117--126},
  year      = {2013},
}

@inproceedings{MengM13,
  author    = {Xiangrui Meng and Michael W. Mahoney},
  title     = {Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression},
  booktitle = {Proceedings of the 45th ACM Symposium on Theory of Computing (STOC)},
  year      = {2013},
  pages     = "91--100",
}

@inproceedings{ClarksonW13,
  author    = {Kenneth L. Clarkson and
                 David P. Woodruff},
  title     = {Low Rank Approximation and Regression in Input Sparsity Time},
  booktitle = {Proceedings of the 45th ACM Symposium on Theory of Computing (STOC)},
  year      = {2013},
  pages     = "81--90",
  note      = {Full version at \url{http://arxiv.org/pdf/1207.6365v4.pdf}}
}

@article{Woodruff14,
  author    = {David P. Woodruff},
  title     = {Sketching as a Tool for Numerical Linear Algebra},
  journal   = {Foundations and Trends in Theoretical Computer Science},
  volume    = {10},
  number    = {1-2},
  pages     = {1--157},
  year      = {2014},
}

@article{Candes08,
  author = {Emmanuel Cand\`{e}s},
  title = {The restricted isometry property and its implications for compressed sensing},
  journal = {Comptes Rendus Mathematique},
  volume = {346},
  number = {9-10},
  pages =  "589--592",
  year = 2008,
}

@article{CandesT06,
  author = {Emmanuel J. Cand\`{e}s and Terence Tao},
  title = {Near-optimal signal recovery from random projections: universal encoding strategies?},
  journal = {IEEE Trans. Inform. Theory},
  volume = 52,
  year = 2006,
  pages = "5406--5425",
}

@article {BaraniukDD08,
    AUTHOR = {Baraniuk, R. and Davenport, M. and DeVore, R. and
              Wakin, M.},
     TITLE = {A simple proof of the restricted isometry property for random matrices},
   JOURNAL = {Constr. Approx.},
    VOLUME = {28},
      YEAR = {2008},
    NUMBER = {3},
     PAGES = {253--263},
}

@book{FoucartR13,
  author={Simon Foucart and Holger Rauhut},
  title={A Mathematical Introduction to Compressive Sensing},
  publisher={Birkha{\"{u}}ser},
  address = {Boston},
  year={2013},
}

@article {Donoho06,
    AUTHOR = {Donoho, D.},
     TITLE = {Compressed sensing},
   JOURNAL = {IEEE Trans. Inform. Theory},
    VOLUME = {52},
      YEAR = {2006},
    NUMBER = {4},
     PAGES = {1289--1306},
}

@article{BourgainDN15,
  author    = {Jean Bourgain and Sjoerd Dirksen and Jelani Nelson},
  title     = {Toward a unified theory of sparse dimensionality reduction in {Euclidean} space},
  journal = {Geometric and Functional Analysis (GAFA), to appear},
  year = {2015},
  note      = {Preliminary version in STOC 2015.},
}

@BOOK{Talagrand14,
  author = {Michel Talagrand},
  title = {Upper and lower bounds for stochastic processes: modern methods and classical problems},
  publisher = {Springer},
  year = 2014,
}

@article{Fernique75,
  author = {Xavier Fernique},
  title = {Regularit\'{e} des trajectoires des fonctions al\'{e}atoires gaussiennes},
  volume = {480},
  pages = "1--96",
  journal = {Lecture Notes in Math.},
  year = 1975,
}

@article{Dirksen14,
  author    = {Sjoerd Dirksen},
  title     = {Dimensionality reduction with subgaussian matrices: a unified theory},
  journal   = {CoRR},
  volume    = {abs/1402.3973},
  year      = {2014},
}

@article{OymakRS15,
  author    = {Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi},
  title     = {Dimensionality reduction with subgaussian matrices: a unified theory},
  journal   = {CoRR},
  volume    = {abs/1506.03521},
  year      = {2015},
}

@article{Dirksen13,
  author    = {Sjoerd Dirksen},
  title     = {Tail bounds via generic chaining},
  journal   = {CoRR},
  volume    = {abs/1309.3522v2},
  year      = {2013},
}

@article{KlartagM05,
  author = {Bo'az Klartag and Shahar Mendelson},
  title = {Empirical processes and random projections},
  journal = {J. Funct. Anal.}, 
  volume = 225,
  number = 1,
  pages = "229--245",
  year = 2005,
}

@article{KMR14,
  author = {Felix Krahmer and Shahar Mendelson and Holger Rauhut},
  title = {Suprema of chaos processes and the restricted isometry property},
  journal = {{C}omm. {P}ure {A}ppl. {M}ath.},
  year = {2014},
  number = 11,
  pages = {1877--1904},
  volume = 67,
}

@article{BDN15,
  author = {Jean Bourgain and Sjoerd Dirksen and Jelani Nelson},
  year={2015},
  journal={Geometric and Functional Analysis},
  title={Toward a unified theory of sparse dimensionality reduction in {Euclidean} space},
  publisher={Springer Basel},
  pages={1-80},
}

@Article{JL84,
  author = {William B. Johnson and Joram Lindenstrauss},
  title = {Extensions of {Lipschitz} mappings into a {Hilbert} space},
  journal = {Contemporary Mathematics},
  volume = 26,
  pages = "189--206",
  year = 1984
}

@article{CharikarCF04,
  author    = {Moses Charikar and
               Kevin C. Chen and
               Martin Farach{-}Colton},
  title     = {Finding frequent items in data streams},
  journal   = {Theor. Comput. Sci.},
  volume    = {312},
  number    = {1},
  pages     = {3--15},
  year      = {2004},
}

@article{ThorupZ12,
  author    = {Mikkel Thorup and
               Yin Zhang},
  title     = {Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation},
  journal   = {{SIAM} J. Comput.},
  volume    = {41},
  number    = {2},
  pages     = {293--331},
  year      = {2012},
}