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.
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.
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.
Title: Straggler-free Coding for Distributed Matrix Multiplication
Abstract:
Built on top of a large number of commodity nodes, large-scale distributed systems running multiple tasks in parallel on different nodes suffer from unreliable performance, as stragglers are the rule rather than the exception. Although stragglers can be tolerated by replicating tasks on multiple nodes or relaunching affected tasks via straggler detection, either approach requires a significant amount of resources or compromises completion time. Our recent research has focused on using erasure coding to create coded tasks that can efficiently tolerate stragglers with much lower overhead. Specifically, this talk will present the coding schemes we have designed for single and batch matrix multiplication in distributed systems.
Title: Deep Structural Representation Learning
Abstract:
Modern analytics is facing highly complex and heterogeneous data. While deep learning models have pushed our prediction power to a new level, they are not satisfactory in some crucial merits such as transparency, robustness, data-efficiency, etc. To address these challenges, I am generally interested in incorporating mathematical modeling of topology, geometry and dynamics seamlessly into the learning pipeline. Such model-informed learning approach will be more transparent, steerable and less data-hungry.
Title: Geometric Optimization Problems in Packing, Covering, and Routing
Abstract: A fundamental class of combinatorial optimization problems involve packing and covering. Examples include maximum independent
set, dominating set, set cover, hitting set, etc. Motivated by
applications in sensor networks and robotics, natural instances of
such problems arise in geometric situations, such as covering points
with a small number of disks, viewing "art galleries" with a small
number of guards or with a mobile guard on a short route, packing
disks or other shapes within a bounded domain, etc. Almost all of
these problems are NP-hard even in simple two-dimensional settings.
The problems get even harder when we take into account uncertain data,
time constraints for scheduled coverage, and routing/connectivity
problems in combination with coverage constraints. We discuss several
of these geometric optimization problems from the perspective of
approximation algorithms and we describe some techniques that have led
to new or improved bounds or running times for selected packing,
covering, and routing/coverage problems. Some of the problems are also
amenable to algorithm engineering, with promising heuristic methods
that allow significant size problems to be solved to near optimality in practice.
Title: Group-Based Cryptography in the Quantum and Artificial Intelligence Era
Abstract: In this talk, I present an overview of the current state-of-the-art in post-quantum group-based cryptography. I describe several families of groups that have been proposed as platforms, with special emphasis in polycyclic groups and graph groups, dealing in particular with their algorithmic properties and cryptographic applications. I then describe some applications of combinatorial algebra in fully homomorphic encryption.