Welcome to the Q4C (QForce) Series

Queens For Computing
Queens College CUNY Computer Science Colloquium

This colloquium is intended to bring together Computer Science and Data Science researchers in the tri-state area (especially in NYC) and to foster collaboration. We welcome talks on any topic of interest to the CS community, including theory, algorithms, machine learning, and data science. If you are interested in attending in-person or online, or would like to give a talk, please contact the organizers.

  1. 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.

  2. 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.

  3. 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.

  4. Wednesday, 03/15/2023, 12:15PM - 1:30PM
    Science Building, C205
    Speaker: Jun Li, Department of Computer Science, Queens College CUNY

  5. Wednesday, 03/29/2023, 12:15PM - 1:30PM
    Science Building, C205
    Speaker: Chao Chen, Stony Brook University

  6. Wednesday, 04/19/2023, 12:15PM - 1:30PM
    Science Building, C205
    Speaker: Joseph S.B. Mitchell, Stony Brook University

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

The seminar is organized by Mayank Goswami
Email Contact: mayank.goswami@qc.cuny.edu