Queens College CUNY Computer Science Colloquium

- Monday, 08/28/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Surya Teja Gavva, Queens College CUNY**Title**: Explicit Signings for the Kadison-Singer Problem in Graphs.**Abstract**: The solution to the long-standing Kadison-Singer problem by Marcus, Spielman, and Srivastava demonstrates the existence of unweighted spectral sparsifiers for graphs. However, the solution based on the expected characteristic polynomial only establishes existence, leaving the computation of sparse approximations as an important open problem. In this study, we present algorithms (along with explicit signings) tailored for specific classes of graphs. Of particular interest is the variety of tools from harmonic analysis, discrepancy theory, and random regular graphs that appear while analyzing this problem.

- Monday, 09/11/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Boris Aronov, NYU**Title**: Dynamic Approximate Multiplicatively-Weighted Nearest Neighbor**Abstract**: In the nearest-neighbor problem, given a set P of points (in the plane, in 3-space, or higher dimension), we want to preprocess P so that, given another point q, its nearest neighbor (closest point) in P can be found efficiently. The approximate version of the problem does not insist that we return the point that's closest to q: returning a point that is a little further away is acceptable.We describe a dynamic data structure for approximate nearest neighbor (ANN) queries with respect to multiplicatively weighted distances with additive offsets. Queries take polylogarithmic time, while the cost of updates is amortized polylogarithmic. The data structure requires near-linear space and construction time. The approach works not only for the Euclidean norm, but for other norms in R^d, for any fixed d. We employ our ANN data structure to construct a faster dynamic structure for approximate SINR queries, ensuring polylogarithmic query and polylogarithmic amortized update for the case of non-uniform power transmitters, thus closing a gap in previous state of the art.

- Tuesday, 10/10/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Karthik C.S., Rutgers University

- Monday, 10/16/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Chee Yap, NYU

- Monday, 10/23/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Janani Sundaresan, Rutgers University

- Monday, 11/06/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Yifan Sun, Stony Brook University

- Monday, 11/13/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Shubham Jain, Stony Brook University

The seminar is organized by Mayank Goswami

Email Contact: mayank.goswami@qc.cuny.edu