Queens College CUNY Computer Science Colloquium

- Wednesday, 02/01/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Prantar Ghosh, DIMACS Rutgers University**Title**: Vertex Ordering Problems in Directed Graph Streams**Abstract**: In the graph streaming model, edges of a massive input graph arrive in a sequence or stream, and our goal is to solve a given problem on the graph by optimizing the memory usage. In this talk, I shall discuss streaming algorithms for problems on directed graphs. Although many graphs that motivate the study of graph streaming are directed (e.g., "follows" on social networks, citation graphs, web graphs with hyperlinks, etc), most of the streaming literature prior to work had focussed only on undirected graphs. We consider fundamental digraph problems mostly related to orderings of vertices, such as topological sorting, acyclicity testing, minimum feedback arc set (edges whose removal yields an acyclic graph), reachability, and finding a source/sink vertex. We are interested in both adversarially ordered and randomly ordered streams. For adversarial-order streams, we show that most of these problems have high space complexity, precluding sublinear-space solutions. Some lower bounds also apply when the stream is randomly ordered: e.g., in our most technical result we show that testing acyclicity or reachability in the p-pass random-order model requires roughly n^{1+1/p} space. For some other problems, we show that random ordering can make a dramatic difference: e.g., we show an exponential separation in space complexity between random- and adversarial-order streams for finding a sink node in an acyclic tournament. We also design sublinear algorithms for the feedback arc set problem in tournaments: we give a single-pass (1+ε)-approximation algorithm using O(n/ε^2) space. Given that this algorithm takes exponential time, we also design a polynomial-time algorithm achieving 3-approximation using p passes and n^{1+1/p} space. Collectively, our results establish a solid foundation for streaming digraph problems.Based on joint work with Amit Chakrabarti, Andrew McGregor, and Sofya Vorotnikova.

- Wednesday, 02/15/2023, 12:15PM - 1:30PM

Sceince Building, C205

Speaker: Sophie Huiberts, Columbia University**Title**: Smoothed analysis of the simplex method**Abstract**: The simplex method is an important algorithm for solving linear optimization problems. The algorithm is very efficient in practice, but theoretical explanations of this fact are lacking. In this talk, I will describe smoothed analysis, one of the primary theoretical frameworks for analysing the simplex method, and present upper and lower bounds on the running time.

- Wednesday, 03/01/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Christopher Musco, New York University**Title**:Linear and sublinear time spectral density estimation.**Abstract**: I will discuss new work on algorithms for approximating the spectral density (eigenvalue distribution) of an n x n symmetric matrix A. We will see that natural variants of popular moment matching methods algorithms achieve strong worst-case approximation guarantees: they can approximate the spectral density for any matrix A to epsilon accuracy in the Wasserstein-1 distance with roughly O(1/epsilon) matrix-vector multiplications with A. Moreover, we will show that these methods are robust to error in these matrix-vector multiplications, which allows them to be combined with any approximate multiplication algorithm. As an application, we develop a randomized sublinear time algorithm for approximating the spectral density of a normalized graph adjacency or Laplacian matrices. The talk will cover the main tools used in our work, which include random importance sampling methods and stability results for computing orthogonal polynomials via three-term recurrence relations.Based on joint work with Aditya Krishnan and Vladimir Braverman that appeared at STOC 2022. https://arxiv.org/abs/2104.03461.

- Wednesday, 03/15/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Jun Li, Department of Computer Science, Queens College CUNY

- Wednesday, 03/29/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Chao Chen, Stony Brook University

- Wednesday, 04/19/2023, 12:15PM - 1:30PM

Science Building, C205

Speaker: Joseph S.B. Mitchell, Stony Brook University

- Wenesday, 05/03/2023, 12:15PM - 1:30PM

TBA

The seminar is organized by Mayank Goswami

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