Publication
Construction of Polar Codes With Sublinear Complexity
Related publications (53)
An Optimal Space Lower Bound for Approximating MAX-CUT
We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...
ASSOC COMPUTING MACHINERY2019Online Matching with General Arrivals
Ola Nils Anders Svensson, Mikhail Kapralov, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc
The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...
IEEE COMPUTER SOC2019On the Size of K-Cross-Free Families
János Pach, Andrei Kupavskii, Istvan Tomon
Two subsets A,B of an n-element ground set X are said to be crossing, if none of the four sets AB, A\B, B\A and X(AB) are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family F of subsets of X does not contain k pairwise cr ...
SPRINGER HEIDELBERG2019Round 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 MACHINERY2018On some problems related to 2-level polytopes
In this thesis we investigate a number of problems related to 2-level polytopes, in particular from the point of view of the combinatorial structure and the extension complexity. 2-level polytopes were introduced as a generalization of stable set polytopes ...
EPFL2018Participation processes in the field of public transportation
As the complexity of urban planning increases by the discovery of new issues and new dynamics, it appears that the “role of the planner as the technical expert just supporting the political decision makers has been progressively substituted by the awarenes ...
2018Finding Perfect Matchings in Bipartite Hypergraphs
Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...
SPRINGER HEIDELBERG2018Matching fields and lattice points of simplices
We show that the Chow covectors of a linkage matching field define a bijection of lattice points and we demonstrate how one can recover the linkage matching field from this bijection. This resolves two open questions from Sturmfels & Zelevinsky (1993) on l ...
2018The weighted stable matching problem
We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general ...
2017Optimal Representations for Adaptive Streaming in Interactive Multiview Video Systems
Interactive multiview video streaming (IMVS) services permit to remotely navigate within a 3D scene with an immersive experience. This is possible by transmitting a set of reference camera views (anchor views), which are used by the clients to freely navig ...
Ieee-Inst Electrical Electronics Engineers Inc2017