869 research outputs found
Efficient Removal Lemmas for Matrices
No full textThe authors and Fischer recently proved that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing an (ordered) matrix removal lemma, which states the following: If a matrix is far from satisfying some hereditary property, then a large enough constant-size random submatrix of it does not satisfy the property with probability at least 9/10. Here being far from the property means that one needs to modify a constant fraction of the entries of the matrix to make it satisfy the property.
However, in the above general removal lemma, the required size of the random submatrix grows very fast as a function of the distance of the matrix from satisfying the property. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following: If an epsilon-fraction of the entries of a binary matrix M can be covered by pairwise-disjoint copies of some (s x t) matrix A, then a delta-fraction of the (s x t)-submatrices of M are equal to A, where delta is polynomial in epsilon.
We generalize the work of Alon, Fischer and Newman [SICOMP'07] and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas
Efficient Splitting of Necklaces
No full textWe provide efficient approximation algorithms for the Necklace Splitting problem. The input consists of a sequence of beads of n types and an integer k. The objective is to split the necklace, with a small number of cuts made between consecutive beads, and distribute the resulting intervals into k collections so that the discrepancy between the shares of any two collections, according to each type, is at most 1. We also consider an approximate version where each collection should contain at least a (1-ε)/k and at most a (1+ε)/k fraction of the beads of each type. It is known that there is always a solution making at most n(k-1) cuts, and this number of cuts is optimal in general. The proof is topological and provides no efficient procedure for finding these cuts. It is also known that for k = 2, and some fixed positive ε, finding a solution with n cuts is PPAD-hard.
We describe an efficient algorithm that produces an ε-approximate solution for k = 2 making n (2+log (1/ε)) cuts. This is an exponential improvement of a (1/ε)^O(n) bound of Bhatt and Leighton from the 80s. We also present an online algorithm for the problem (in its natural online model), in which the number of cuts made to produce discrepancy at most 1 on each type is Õ(m^{2/3} n), where m is the maximum number of beads of any type. Lastly, we establish a lower bound showing that for the online setup this is tight up to logarithmic factors. Similar results are obtained for k > 2
Hitting a Prime in 2.43 Dice Rolls (on average) and on Round-Robin Tournaments with a Unique Maximum Score
No full textYaakov Malinovsky will discuss two different topics. The first describing joint work with Noga Alon and the second with John W. Moon. For a detailed abstract, see sites.math.rutgers.edu/~zeilberg/expmath/YM22abstract.pdf.https://vimeo.com/77508663
Palette Sparsification Beyond (Δ+1) Vertex Coloring
No full textA recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every n-vertex graph G with maximum degree Δ, sampling O(log n) colors per each vertex independently from Δ+1 colors almost certainly allows for proper coloring of G from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for (Δ+1) coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms.
In this paper, we focus on palette sparsification beyond (Δ+1) coloring, in both regimes when the number of available colors is much larger than (Δ+1), and when it is much smaller. In particular,
- We prove that for (1+ε) Δ coloring, sampling only O_ε(√{log n}) colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors - this shows a separation between (1+ε) Δ and (Δ+1) coloring in the context of palette sparsification.
- A natural family of graphs with chromatic number much smaller than (Δ+1) are triangle-free graphs which are O(Δ/ln Δ) colorable. We prove a palette sparsification theorem tailored to these graphs: Sampling O(Δ^γ + √{log n}) colors per vertex is sufficient and necessary to obtain a proper O_γ(Δ/ln Δ) coloring of triangle-free graphs.
- We also consider the "local version" of graph coloring where every vertex v can only be colored from a list of colors with size proportional to the degree deg(v) of v. We show that sampling O_ε(log n) colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of (1+ε) ⋅ deg(v) arbitrary colors, or even only deg(v)+1 colors when the lists are the sets {1,…,deg(v)+1}.
Our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms
Primer pla del professor Noga Alon a l'acte de cloenda del Curs Erdös 2010-2011
No full textCloenda "Curs Erdös 2010-2011 amb la conferència "Paul Erdős and probabilistic reasoning" a càrrec del Professor Noga Alon (Tel Aviv University) l'11-5-2011. Accés a l'enregistrament a la Videoteca de l'FME: http://hdl.handle.net/2099.2/234
Primer pla del professor Noga Alon a l'acte de cloenda del Curs Erdös 2010-2011
No full textCloenda "Curs Erdös 2010-2011 amb la conferència "Paul Erdős and probabilistic reasoning" a càrrec del Professor Noga Alon (Tel Aviv University) l'11-5-2011. Accés a l'enregistrament a la Videoteca de l'FME: http://hdl.handle.net/2099.2/234
Primer pla del professor Noga Alon a l'acte de cloenda del Curs Erdös 2010-2011
No full textCloenda "Curs Erdös 2010-2011 amb la conferència "Paul Erdős and probabilistic reasoning" a càrrec del Professor Noga Alon (Tel Aviv University) l'11-5-2011. Accés a l'enregistrament a la Videoteca de l'FME: http://hdl.handle.net/2099.2/234
Primer pla del professor Noga Alon a l'acte de cloenda del Curs Erdös 2010-2011
No full textCloenda "Curs Erdös 2010-2011 amb la conferència "Paul Erdős and probabilistic reasoning" a càrrec del Professor Noga Alon (Tel Aviv University) l'11-5-2011. Accés a l'enregistrament a la Videoteca de l'FME: http://hdl.handle.net/2099.2/234
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
No full textIn this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms.
For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O~(m sqrt{n}). Here we provide the first deterministic algorithm for this problem, with the same O~(m sqrt{n}) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of O~(mn) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in O~(m sqrt{n}) time, and a deterministic algorithm for the k-simple shortest paths problem in O~(k m sqrt{n}) time (for any integer constant k > 0).
For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t in V and F subseteq E cup V, |F| <=f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \ F (i.e., the distance from s to t in the graph G after removing from it the failing edges and vertices F).
For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized f-DSOs. In particular, they presented a combinatorial f-DSO with O~(mn^{4-alpha}) preprocessing time and subquadratic O~(n^{2-2(1-alpha)/f}) query time, giving a tradeoff between preprocessing and query time for every value of 0 < alpha < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time
Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
No full textWe prove a lower bound of Omega(n^2/log^2 n) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f(x_1, ..., x_n). Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([Ran Raz et al., 2008]), who proved a lower bound of Omega(n^{4/3}/log^2 n) for the same polynomial. Our improvement follows from an asymptotically optimal lower bound for a generalized version of Galvin's problem in extremal set theory
- …
