Noticias en español
Convex hierarchies, scheduling and symmetries
Abstract: The Sum of Squares (SoS) hierarchy provides a finite nested family K_1, K_2, … , K_n of convex relaxations for an integer program with n variables, that reaches the integer hull, i.e., K_n corresponds to the convex hull of the integer feasible solution. A natural question is to understand how the integrality gap evolves over the family. In particular, a rapid decay of the gap might yield good approximation algorithms. We show that for the classic problem of scheduling identical machines to minimize the makespan, the SoS hierarchy exhibits an integrality gap curve that remains at...
Read MoreComplexity of point-to-planar convex set distance
Abstract: In computer science, there are several equivalent ways to define a com- putable compact set in $\R^k$. One of them is the so called “locally com- putable compact set”, that is, being able to decide whether or not a given ball intersects the set – this is often referred to as the “pixel information” of the set because, loosely speaking, it allows us to know which pixels must be coloured when drawing a picture of the set on a screen. It is not hard to see that from the pixel information of a set one can compute the distance to a given point, but the computational cost of doing so may...
Read MoreOn Distributed Merlin-Arthur Decision Protocols
Abstract: In a distributed locally-checkable proof, we are interested in checking the legality of a given network configuration with respect to some Boolean predicate. To do so, the network enlists the help of a prover — a computationally-unbounded oracle that aims at convincing the network that its state is legal, by providing the nodes with certificates that form a distributed proof of legality. The nodes then verify the proof by examining their certificate, their local neighborhood and the certificates of their neighbors. In this talk we examine the power of a randomized form of...
Read MoreSuper-logarithmic cliques in dense inhomogeneous random graphs
Abstract: In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1]^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G(n,W), that can be viewed as a generalization of the Erdos-Renyi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order log(n) for the size of the largest clique in G(n,W) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G(n,W)...
Read MoreBalancing Vectors in any Norm
Abstract: In the vector balancing problem, we are given symmetric convex bodies C and K in R^n, and our goal is to determine the minimum number β ≥ 0, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside βK. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Appl. Math ‘81), Spencer’s “six standard deviations suffice” theorem (Trans. Amer. Math. Soc ‘85) and Banaszczyk’s vector balancing theorem (Random Structures & Algorithms ‘98) correspond to...
Read More