IC Colloquium : Sublinear Algorithms for Modern Graph Analysis
Event details
| Date | 23.02.2015 |
| Hour | 10:15 › 11:30 |
| Location | |
| Category | Conferences - Seminars |
By : Michael Kapralov - IBM T. J. Watson Research Center
IC Faculty candidate
Abstract :
Graphs are a common abstraction for representing large social and information networks, and a powerful set of algorithmic primitives has been developed for their analysis. As the sizes of modern datasets grow, however, many classical polynomial time (and sometimes even linear time) solutions become prohibitively expensive. This calls for sublinear algorithms, i.e. algorithms whose resource requirements are substantially smaller than the size of the input that they operate on.
In this talk, we describe a new approach to the problem of approximating the size of maximum matching in a large graph given as a stream of edge updates using sublinear space. The matching problem is one of the most well-studied questions in combinatorial optimization, and has important applications in modern big data analysis (e.g. online advertising). We obtain a polylogarithmic approximation to maximum matching size using space sublinear in the number of *vertices* in the graph and exponentially smaller than previously known. This is the first algorithm for a graph problem that achieves truly sublinear space in the streaming setting, suggesting the possibility of a new class of more efficient graph analysis primitives.
Bio :
Michael Kapralov is a Herman Goldstine Postdoctoral Fellow at the IBM T.J. Watson Research Center. Michael obtained his Ph.D. from Stanford University in 2012, after which he spent two years as a postdoc in the Theory of Computation Group at MIT CSAIL. His research interests are in design of efficient algorithms. He has worked on various questions in theoretical foundations of big data analysis: algorithms for solving graph problems on massive inputs that achieve sublinear runtime, can operate under tight restrictions on space (streaming algorithms) and communication (sketching algorithms) or can deal with uncertainty in future inputs (online algorithms). His most recent interests include sparse recovery and Fourier sampling.
More information
IC Faculty candidate
Abstract :
Graphs are a common abstraction for representing large social and information networks, and a powerful set of algorithmic primitives has been developed for their analysis. As the sizes of modern datasets grow, however, many classical polynomial time (and sometimes even linear time) solutions become prohibitively expensive. This calls for sublinear algorithms, i.e. algorithms whose resource requirements are substantially smaller than the size of the input that they operate on.
In this talk, we describe a new approach to the problem of approximating the size of maximum matching in a large graph given as a stream of edge updates using sublinear space. The matching problem is one of the most well-studied questions in combinatorial optimization, and has important applications in modern big data analysis (e.g. online advertising). We obtain a polylogarithmic approximation to maximum matching size using space sublinear in the number of *vertices* in the graph and exponentially smaller than previously known. This is the first algorithm for a graph problem that achieves truly sublinear space in the streaming setting, suggesting the possibility of a new class of more efficient graph analysis primitives.
Bio :
Michael Kapralov is a Herman Goldstine Postdoctoral Fellow at the IBM T.J. Watson Research Center. Michael obtained his Ph.D. from Stanford University in 2012, after which he spent two years as a postdoc in the Theory of Computation Group at MIT CSAIL. His research interests are in design of efficient algorithms. He has worked on various questions in theoretical foundations of big data analysis: algorithms for solving graph problems on massive inputs that achieve sublinear runtime, can operate under tight restrictions on space (streaming algorithms) and communication (sketching algorithms) or can deal with uncertainty in future inputs (online algorithms). His most recent interests include sparse recovery and Fourier sampling.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Nisheeth Vishnoi