Publication
An Optimal Space Lower Bound for Approximating MAX-CUT
Publications associées (36)
Local approximation of the Maximum Cut in regular graphs
This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...
ELSEVIER2020Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos
Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...
ASSOC COMPUTING MACHINERY2020Minimum-Error Classes for Matching Parts
This paper examines the binning of two types of parts with random characteristics, so that a componentwise monotonic evaluation criterion exhibits a minimum deviation to a given target value over all possible realizations. The optimal matching classes are ...
2020New Graph Algorithms via Polyhedral Techniques
In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...
EPFL2019Local Approximation of the Maximum Cut in Regular Graphs
This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...
SPRINGER INTERNATIONAL PUBLISHING AG2019Graph fragmentation problem: analysis and synthesis
Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of indivi ...
WILEY2019Construction of Polar Codes With Sublinear Complexity
Rüdiger Urbanke, Seyed Hamed Hassani, Marco Mondelli
Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019Round Compression for Parallel Matching Algorithms
Slobodan Mitrovic, Aleksander Madry
For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture th ...
ASSOC COMPUTING MACHINERY2018An FFT-based Numerical Method for Elasto-Plastic Contact
Jean-François Molinari, Guillaume Anciaux, Lucas Henri Galilée Frérot
Contact of rough surfaces is of prime importance in the study of friction and wear. Numerical simulations are well suited for this non-linear problem, but natural surfaces being fractal [1], they have high discretization requirements. There is therefore a ...
2018When Stuck, Flip a Coin
Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question:
How can we design efficient algorithms for large-scale computation?
In this thesis, we focus on devising a general strategy to addr ...
EPFL2018