21 citations · 32 across the 9 of their papers we have counts for
11 papers
Fairness in Streaming Submodular Maximization over a Matroid Constraint
Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard +2
Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as g…
Motif Cut Sparsifiers
Michael Kapralov, Mikhail Makarov, Sandeep Silwal +2
A motif is a frequently occurring subgraph of a given directed or undirected graph . Motifs capture higher order organizational structure of beyond edge relationships, and,…
Yang-Mills-Scalar-Matter Fields in the Two-Point Space
Gustavo Amilcar Saldaña Moncada
The purpose of this work is to present a Non--Commutative Geometrical version of the Yang--Mills Theory and the Yang--Mills Scalar Matter Theory by constructing a concrete example…
Noisy Boolean Hidden Matching with Applications
Michael Kapralov, Amulya Musipatla, Jakab Tardos +2
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et. al. [STOC'07], has played an important role in the streaming lower bounds for graph problem…
Streaming Belief Propagation for Community Detection
Yuchen Wu, MohammadHossein Bateni, Andre Linhares +4
The community detection problem requires to cluster the nodes of a network into a small number of well-connected "communities". There has been substantial recent progress in charac…
Spectral Hypergraph Sparsifiers of Nearly Linear Size
Michael Kapralov, Robert Krauthgamer, Jakab Tardos +1
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph spars…
Communication Efficient Coresets for Maximum Matching
Michael Kapralov, Gilbert Maystre, Jakab Tardos
In this paper we revisit the problem of constructing randomized composable coresets for bipartite matching. In this problem the input graph is randomly partitioned across playe…
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, Jakab Tardos +1
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently bee…
Fairness in Streaming Submodular Maximization: Algorithms and Hardness
Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard +2
Submodular maximization has become established as the method of choice for the task of selecting representative and diverse summaries of data. However, if datapoints have sensitive…
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Michael Kapralov, Slobodan Mitrović, Ashkan Norouzi-Fard +1
Given a source of iid samples of edges of an input graph with vertices and edges, how many samples does one need to compute a constant factor approximation to the maxim…
Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
Michael Kapralov, Navid Nouri, Aaron Sidford +1
In this paper we consider the problem of computing spectral approximations to graphs in the single pass dynamic streaming model. We provide a linear sketching based solution that g…