October 26-27, 2018 • Queens College, CUNY
Hosted and sponsored by the Department of Computer Science.
Title: Incidence geometry, rank bounds for design matrices, and applications
Abstract: The classical Sylvester-Gallai theorem states that for any finite set of points in the Euclidean plane, if the line through every pair of points passes through a third point, then all points must be collinear. Thus basically the result shows that many `local' linear dependencies implies a `global' bound on the dimension of the entire set of points. Variations of these questions have been well studied in additive combinatorics and incidence geometry. In the last few years, techniques from these areas have proven to be very useful in several structural results in theoretical computer science, in areas such as arithmetic complexity as well as coding theory. In this talk I will survey some of these connections as well as highlight some of the proof techniques (such as the study of rank bounds for design matrices). I will also talk about a recent result which gives a linear lower bound for the number of ordinary lines (lines through exactly two points) determined by a point set spanning 3 dimensional complex space.
Based on joint works with Abdul Basit, Zeev Dvir, Neeraj Kayal, Avi Wigderson and Charles Wolf
Title: Protecting Data Privacy in a Socially Connected World
We live in a world in which people are socially connected through an increasing number of mobile devices. Information is collected from these devices and exchanged with each other. In this talk I will discuss new challenges of data privacy with social connectivity in a variety of settings: alignment of two social networks for identity de-anonymization, inference of location/trajectory by co-location events; as well as new algorithms for collecting private trajectory data in a distributed manner, or protecting sensitive features by introducing carefully engineered noises. The algorithms or attacks use geometric insights.
Bio: Jie Gao is a Professor of Computer Science at Stony Brook University. She received BS from the special class for the gifted young program at University of Science and Technology of China in 1999 and Ph.D in computer science from Computer Science department, Stanford University in 2004. She received NSF Career award in 2006, IMC best paper award in 2009, and multiple awards at Stony Brook CS department on Excellence in Research. She published over 120 referred papers in computer networking and theoretical computer science. She co-chaired the ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), 2018. She is currently serving on the editorial board of ACM Transactions on Sensor Networks and Journal of Discrete Algorithms.