Skip to main content

Braverman, Vladimir

Associate Professor
Computer Science
https://www.cs.jhu.edu/~vova

Malone 211
(410) 516-4975
vbraver1@jhu.edu

Jump to:

News

Vladimir Braverman

CS’ Vladimir Braverman to receive NSF CAREER Award

January 31, 2017

Vladimir Braverman, an assistant professor in the Department of Computer Science, has been chosen by the National Science Foundation for its prestigious CAREER Award, which recognizes early stage scholars with high levels of promise and excellence.

Read More

About

Education
  • Ph.D. 2011, Univ of California Los Angeles
  • Master of Science 2004, Ben-Gurion Univ of The Negev
  • Bachelor of Science 1998, Ben-Gurion Univ of The Negev
Research Areas
  • Algorithms
  • BIG data
  • Theoretical Computer Science
Awards
  • 2014:  Google Research Award
Presentations
  • "An Optimal Algorithm For Large Frequency Moments Using O(n^1-2/k) Bits", NII Shonan Meeting on "Algorithms for Large-Scale Graphs".  Shonan, Japan.  October 17, 2014
  • "An Optimal Algorithm For Large Frequency Moments Using O(n^1-2/k) Bits", Maryland Theory Day 2014.  University of Maryland.  October 10, 2014
  • "Approximating Large Frequency Moments with $O(n^{1−2/k})$ Bits", Bertinoro Workshop on Sublinear Algorithms.  Bertinoro, Italy.  May 28, 2014
  • "Approximating Large Frequency Moments with O(n^{1-2/k}) Bits", Theory of Computation at Harvard.  Harvard University.  January 28, 2014

Publications

Journal Articles
  • Ivkin N, Ben Basat R, Liu Z, Einziger G, Friedman R, Braverman V (2020).  I Know What You Did Last Summer: Network Monitoring using Interval Queries.  Performance Evaluation Review.  48(1).  61-62.
  • Ivkin N, Basat RB, Liu Z, Einziger G, Friedman R, Braverman V (2020).  I Know What You Did Last Summer: Network Monitoring using Interval Queries.  SIGMETRICS Performance 2020 - Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems.  61-62.
  • Leung DG, Bocchieri AE, Ahlawat S, Jacobs MA, Parekh VS, Braverman V, Summerton K, Mansour J, Bibat G, Morris C, Marraffino S, Wagner KR (2020).  Longitudinal functional and imaging outcome measures in FKRP limb-girdle muscular dystrophy.  BMC Neurology.  20(1).
  • Ivkin N, Yu Z, Braverman V, Jin X (2019).  QPipe: Quantiles sketch fully in the data plane.  CoNEXT 2019 - Proceedings of the 15th International Conference on Emerging Networking Experiments and Technologies.  285-291.
  • Braverman V, Lang H, Ullah E, Zhou S (2019).  Improved algorithms for time decay streams.  Leibniz International Proceedings in Informatics, LIPIcs.  145.
  • Braverman V, Feldman D, Lang H, Rus D (2019).  Streaming coreset constructions for M-estimators.  Leibniz International Proceedings in Informatics, LIPIcs.  145.
  • Liu Z, Ben-Basat R, Einziger G, Kassner Y, Braverman V, Friedman R, Sekar V (2019).  NitroSketch: Robust and general sketch-based monitoring in software switches.  SIGCOMM 2019 - Proceedings of the 2019 Conference of the ACM Special Interest Group on Data Communication.  334-350.
  • Ivkin N, Basat RB, Liu Z, Einziger G, Friedman R, Braverman V (2019).  Attack time localization using interval queries.  SIGCOMM 2019 - Proceedings of the 2019 ACM SIGCOMM Conference Posters and Demos, Part of SIGCOMM 2019.  85-87.
  • Braverman V, Charikar M, Kuszmaul W, Woodruff DP, Yang LF (2019).  The one-way communication complexity of dynamic time warping distance.  Leibniz International Proceedings in Informatics, LIPIcs.  129.
  • Yang L, Yu Z, Braverman V, Zhao T, Wang M (2019).  Online factorization and partition of complex networks by random walk.  35th Conference on Uncertainty in Artificial Intelligence, UAI 2019.
  • Liu Z, Bai Z, Liu Z, Li X, Kim C, Braverman V, Jin X, Stoica I (2019).  Distcache: Provable load balancing for large-scale storage systems with distributed caching.  Proceedings of the 17th USENIX Conference on File and Storage Technologies, FAST 2019.  143-157.
  • Braverman V (2019).  Approximations of schatten norms via taylor expansions.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  11532 LNCS.  70-79.
  • Yang LF, Braverman V, Zhao T, Wang M (2019).  Online factorization and partition of complex networks from random walks.  35th Conference on Uncertainty in Artificial Intelligence, UAI 2019.
  • Yang L, Yu Z, Braverman V, Zhao T, Wang M (2019).  Online factorization and partition of complex networks by random walk.  35th Conference on Uncertainty in Artificial Intelligence, UAI 2019.
  • Yang LF, Braverman V, Zhao T, Wang M (2019).  Online factorization and partition of complex networks from random walks.  35th Conference on Uncertainty in Artificial Intelligence, UAI 2019.
  • Braverman V, Grigorescu E, Lang H, Woodruff DP, Zhou S (2018).  Nearly optimal distinct elements and heavy hitters on sliding windows.  Leibniz International Proceedings in Informatics, LIPIcs.  116.
  • Braverman V, Viola E, Woodru DP, Yang LF (2018).  Revisiting frequency moment estimation in random order streams.  Leibniz International Proceedings in Informatics, LIPIcs.  107.
  • Blum A, Braverman V, Kumar A, Lang H, Yang LF (2018).  Approximate convex hull of data streams.  Leibniz International Proceedings in Informatics, LIPIcs.  107.
  • Ivkin N, Liu Z, Yang LF, Kumar SS, Lemson G, Neyrinck M, Szalay AS, Braverman V, Budavari T (2018).  Scalable streaming tools for analyzing N-body simulations: Finding halos and investigating excursion sets in one pass.  Astronomy and Computing.  23.  166-179.
  • Braverman V, Liu Z, Singh T, Vinodchandran NV, Yang LF (2018).  New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory.  Algorithmica.  80(2).  652-667.
  • Yang LF, Arora R, Zhao T, Braverman V (2018).  The physical systems behind optimization algorithms.  Advances in Neural Information Processing Systems.  2018-December.  4372-4381.
  • Arora R, Braverman V, Upadhyay J (2018).  Differentially private robust low-rank approximation.  Advances in Neural Information Processing Systems.  2018-December.  4137-4145.
  • Iyer AP, Liu Z, Jin X, Venkataraman S, Braverman V, Stoica I (2018).  Towards fast and scalable graph pattern mining.  10th USENIX Workshop on Hot Topics in Cloud Computing, HotCloud 2018, co-located with USENIX ATC 2018.
  • Iyer AP, Liu Z, Jin X, Venkataraman S, Braverman V, Stoica I (2018).  Towards fast and scalable graph pattern mining.  10th USENIX Workshop on Hot Topics in Cloud Computing, HotCloud 2018, co-located with USENIX ATC 2018.
  • Braverman V, Chestnut S, Krauthgamer R, Li Y, Woodruff D, Yang L (2018).  Matrix norms in data streams: Faster, multi-pass and row-order.  35th International Conference on Machine Learning, ICML 2018.  2.  1036-1045.
  • Blasiok J, Braverman V, Chestnut SR, Krauthgamer R, Yang LF (2017).  Streaming symmetric norms via measure concentration.  Proceedings of the Annual ACM Symposium on Theory of Computing.  Part F128415.  716-729.
  • Braverman V, Chestnut SR, Ivkin N, Nelson J, Wang Z, Woodruff DP (2017).  BPTree: An ℓ2 heavy hitters algorithm using constant memory.  Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.  Part F127745.  361-376.
  • Braverman V, Lang H, Levin K (2017).  Accurate low-space approximation of metric k-median for insertion-only streams.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  10156 LNCS.  72-82.
  • Braverman V, Frahling G, Lang H, Sohler C, Yang LF (2017).  Clustering high dimensional dynamic data streams.  34th International Conference on Machine Learning, ICML 2017.  2.  927-948.
  • Braverman V, Roytman A, Vorsanger G (2016).  Approximating subadditive hadamard functions on implicit matrices.  Leibniz International Proceedings in Informatics, LIPIcs.  60.
  • Liu Z, Manousis A, Vorsanger G, Sekar V, Braverman V (2016).  One sketch to rule them all: Rethinking network flow monitoring with UnivMon.  SIGCOMM 2016 - Proceedings of the 2016 ACM Conference on Special Interest Group on Data Communication.  101-114.
  • Braverman V, Ivkin N, Chestnut SR, Woodruff DP (2016).  Beating CountSketch for heavy hitters in insertion streams.  Proceedings of the Annual ACM Symposium on Theory of Computing.  19-21-June-2016.  740-753.
  • Braverman V, Chestnut SR, Woodruff DP, Yang LF (2016).  Streaming space complexity of nearly all functions of one variable on frequency vectors.  Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.  26-June-01-July-2016.  261-276.
  • Braverman V, Lang H, Levin K, Monemizadeh M (2016).  Clustering problems on sliding windows.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.  2.  1374-1390.
  • Braverman V, Lang H, Levin K, Monemizadeh M (2015).  Clustering on sliding windows in polylogarithmic space.  Leibniz International Proceedings in Informatics, LIPIcs.  45.  350-364.
  • Liu Z, Vorsanger G, Braverman V, Sekar V (2015).  Enabling a "rISC" approach for software-defined monitoring using universal streaming.  Proceedings of the 14th ACM Workshop on Hot Topics in Networks, HotNets-XIV 2015.
  • Liu Z, Ivkin N, Yang L, Neyrinck M, Lemson G, Szalay A, Braverman V, Budavari T, Burns R, Wang X (2015).  Streaming algorithms for halo finders.  Proceedings - 11th IEEE International Conference on eScience, eScience 2015.  342-351.
  • Braverman V, Ostrovsky R, Vorsanger G (2015).  Weighted sampling without replacement from data streams.  Information Processing Letters.  115(12).  923-926.
  • Braverman V, Ostrovsky R, Roytman A (2015).  Zero-one laws for sliding windows and universal sketches.  Leibniz International Proceedings in Informatics, LIPIcs.  40.  573-590.
  • Braverman V, Chestnut SR (2015).  Universal sketches for the frequency negative moments and other decreasing streaming sums.  Leibniz International Proceedings in Informatics, LIPIcs.  40.  591-605.
  • Braverman V, Liu Z, Singh T, Vinodchandran NV, Yang LF (2015).  New bounds for the CLIQUE-GAP problem using graph decomposition theory.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  9235.  151-162.
  • Braverman V, Katzman J, Seidell C, Vorsanger G (2014).  An optimal algorithm for large frequency moments using o(n1-2/κ) bits.  Leibniz International Proceedings in Informatics, LIPIcs.  28.  531-544.
  • Braverman V, Chestnut SR (2014).  Streaming sums in sublinear space.  CoRR.  abs/1408.5096.
  • Braverman V, Vorsanger G (2014).  Sampling from dense streams without penalty improved bounds for frequency moments and heavy hitters.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  8591 LNCS.  13-24.
  • Braverman V, Katzman J, Seidell C, Vorsanger G (2014).  Approximating Large Frequency Moments with O(n1-2/k) Bits.  CoRR.  abs/1401.1763.
  • Braverman V, Ostrovsky R, Roytman A (2014).  Universal Streaming.  CoRR.  abs/1408.2604.
  • Braverman V, Gelles R, Ostrovsky R (2014).  How to catch L2-heavy-hitters on sliding windows.  Theoretical Computer Science.  554(C).  82-94.
  • Braverman V, Gelles R, Ostrovsky R (2014).  How to catch L_2-heavy-hitters on sliding windows.  Theor. Comput. Sci..  554.  82-94.
  • Braverman V, Ostrovsky R (2013).  Approximating large frequency moments with pick-and-drop sampling.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  8096 LNCS.  42-57.
  • Braverman V, Ostrovsky R (2013).  Generalizing the layering method of indyk and Woodruff: Recursive sketches for frequency-based vectors on streams.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  8096 LNCS.  58-70.
  • Braverman V, Gelles R, Ostrovsky R (2013).  How to catch l 2-heavy-hitters on sliding windows.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  7936 LNCS.  638-650.
  • Braverman V, Ostrovsky R, Vilenchik D (2013).  How hard is counting triangles in the streaming model?.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  7965 LNCS(PART 1).  244-254.
  • Braverman V, Ostrovsky R, Vilenchik D (2013).  How Hard is Counting Triangles in the Streaming Model.  CoRR.  abs/1304.1458.
  • Braverman V, Ostrovsky R (2012).  Approximating Large Frequency Moments with Pick-and-Drop Sampling.  CoRR.  abs/1212.0202.
  • Braverman V, Ostrovsky R, Zaniolo C (2012).  Optimal sampling from sliding windows.  Journal of Computer and System Sciences.  78(1).  260-272.
  • Braverman V, Ostrovsky R, Zaniolo C (2012).  Optimal sampling from sliding windows.  Journal of Computer and System Sciences.  78(1).  260-272.
  • Braverman V, Meyerson A, Ostrovsky R, Roytman A, Shindler M, Tagiku B, SIAM , ACM (2011).  Streaming k-means on Well-Clusterable Data.  Proceedings of the Twenty-Second Annual Acm-Siam Symposium on Discrete Algorithms.  26-40.
  • Braverman V, Meyerson A, Ostrovsky R, Roytman A, Shindler M, Tagiku B (2011).  Streaming k-means on well-clusterable data.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.  26-40.
  • Braverman V, Chung KM, Liu Z, Mitzenmacher M, Ostrovsky R (2010).  AMS without 4-wise independence on product domains.  Leibniz International Proceedings in Informatics, LIPIcs.  5.  119-130.
  • Braverman V, Ostrovsky R (2010).  Zero-one frequency laws.  Proceedings of the Annual ACM Symposium on Theory of Computing.  281-290.
  • Braverman V, Ostrovsky R (2010).  Measuring independence of datasets.  Proceedings of the Annual ACM Symposium on Theory of Computing.  271-280.
  • Braverman V, Ostrovsky R (2010).  Effective computations on sliding windows.  SIAM Journal on Computing.  39(6).  2113-2131.
  • Braverman V, Ostrovsky R, ACM (2010).  Measuring Independence of Datasets.  Stoc 2010: Proceedings of the 2010 Acm Symposium on Theory of Computing.  271-280.
  • Braverman V, Gelles R, Ostrovsky R (2010).  How to Catch L_2-Heavy-Hitters on Sliding Windows.  CoRR.  abs/1012.3130.
  • Braverman V, Ostrovsky R (2010).  EFFECTIVE COMPUTATIONS ON SLIDING WINDOWS.  Siam Journal on Computing.  39(6).  2113-2131.
  • Braverman V, Ostrovsky R, ACM (2010).  Zero-One Frequency Laws.  Stoc 2010: Proceedings of the 2010 Acm Symposium on Theory of Computing.  281-290.
  • Braverman V, Ostrovsky R (2010).  Recursive Sketching For Frequency Moments.  CoRR.  abs/1011.2571.
  • Braverman V, Ostrovsky R, Rabani Y (2010).  Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform.  CoRR.  abs/1011.2590.
  • Braverman V, Ostrovsky R, Zaniolo C (2009).  Optimal sampling from sliding windows.  Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.  147-156.
  • Berend D, Braverman V (2009).  A linear algorithm for computing convex hulls for random lines.  ACM Transactions on Algorithms.  5(4).
  • Braverman V, Ostrovsky R, Zaniolo C, ACM (2009).  Optimal Sampling from Sliding Windows.  Pods'09: Proceedings of the Twenty-Eighth Acm Sigmod-Sigact-Sigart Symposium on Principles of Database Systems.  147-156.
  • Berend D, Braverman V (2009).  A Linear Algorithm for Computing Convex Hulls for Random Lines.  Acm Transactions on Algorithms.  5(4).
  • Braverman V, Ostrovsky R (2008).  Measuring $k$-Wise Independence of Streaming Data.  CoRR.  abs/0806.4790.
  • Braverman V, Ostrovsky R (2007).  Smooth histograms for sliding windows.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.  283-293.
  • Braverman V, Ostrovsky R (2007).  Smooth histograms for sliding windows.  48th Annual Ieee Symposium on Foundations of Computer Science, Proceedings.  283-293.
  • Braverman V, Ostrovsky R, Zaniolo C (2007).  Succinct Sampling on Streams.  CoRR.  abs/cs/0702151.
  • Iyer AP, Liu Z, Jin X, Venkataraman S, Braverman V, Stoica I (2007).  ASAP: Fast, approximate graph pattern mining at scale.  Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018.  745-761.
  • Bachmat E, Braverman V (2006).  Batched disk scheduling with delays.  Performance Evaluation Review.  33(4).  36-41.
  • Bachmat E, Braverman V (2006).  Batched disk scheduling with delays.  SIGMETRICS Performance Evaluation Review.  33(4).  36-41.
  • Braverman VY (1978).  PECULIARITIES OF GMDH APPLICATIONS TO ECONOMIC RESEARCH..  Soviet automatic control.  11(6).  49-52.
  • Braverman VY, Fomychov OO (1974).  SOME ASPECTS OF THE USE OF THE GROUP METHOD OF DATA HANDLING IN THE CASE OF SMALL SAMPLES..  Sov Autom Control.  7(2).  26-32.
Conference Proceedings
  • Braverman V, Vorsanger G (2014).  Sampling from Dense Streams without Penalty - Improved Bounds for Frequency Moments and Heavy Hitters.  Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings.  13-24.
  • Braverman V, Katzman J, Seidell C, Vorsanger G (2014).  An Optimal Algorithm for Large Frequency Moments Using O(n(1-2/k)) Bits.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain.  531-544.
  • Braverman V, Ostrovsky R (2013).  Approximating Large Frequency Moments with Pick-and-Drop Sampling.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings.  42-57.
  • Braverman V, Gelles R, Ostrovsky R (2013).  How to Catch L _2-Heavy-Hitters on Sliding Windows.  Computing and Combinatorics, 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings.  638-650.
  • Braverman V, Ostrovsky R, Vilenchik D (2013).  How Hard Is Counting Triangles in the Streaming Model?.  Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I.  244-254.
  • Braverman V, Ostrovsky R (2013).  Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings.  58-70.
  • Braverman V, Chung K, Liu Z, Mitzenmacher M, Ostrovsky R (2010).  AMS Without 4-Wise Independence on Product Domains.  27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France.  119-130.
Patents
  • "System and method for pick-and-drop sampling", 2015.
  • "Methods for effective processing of time series", 2015.
  • Braverman V  "System and method for pick-and-drop sampling", 2014.
  • "Method and system for creation and dynamic updating of best data arrangement in digital data store system", 2013.
Back to top