1,721,057 research outputs found
Automating Algebraic Proof Systems is NP-Hard
No full textWe show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali--Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Muller (JACM 2020) that established an analogous result for Resolution
Support of closed walks and second eigenvalue multiplicity of graphs
No full textWe show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree ?is bounded by O(n ?7/5/log1/5-o(1)n) for any ?, and improve this to O(nlog1/2d/log1/4-o(1)n) for simple d-regular graphs when d? log1/4n. In fact, the same bounds hold for the number of eigenvalues in any interval of width ?2/log?1-o(1)n containing the second eigenvalue ?2. The main ingredient in the proof is a polynomial (in k) lower bound on the typical support of a closed random walk of length 2k in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix. </p
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
Full text linkWe consider the Connectivity Augmentation Problem (CAP), a classical problem
in the area of Survivable Network Design. It is about increasing the
edge-connectivity of a graph by one unit in the cheapest possible way. More
precisely, given a -edge-connected graph and a set of extra edges,
the task is to find a minimum cardinality subset of extra edges whose addition
to makes the graph -edge-connected. If is odd, the problem is
known to reduce to the Tree Augmentation Problem (TAP) -- i.e., is a
spanning tree -- for which significant progress has been achieved recently,
leading to approximation factors below (the currently best factor is
). However, advances on TAP did not carry over to CAP so far. Indeed,
only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain
the first approximation factor below for CAP by presenting a
-approximation algorithm based on a method that is disjoint from recent
advances for TAP.
We first bridge the gap between TAP and CAP, by presenting techniques that
allow for leveraging insights and methods from TAP to approach CAP. We then
introduce a new way to get approximation factors below , based on a new
analysis technique. Through these ingredients, we obtain a
-approximation algorithm for CAP, and therefore also TAP. This leads to
the currently best approximation result for both problems in a unified way, by
significantly improving on the above-mentioned -approximation for CAP and
also the previously best approximation factor of for TAP by Grandoni,
Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from
recent TAP advances is that our approach can deal with the weighted setting
when the ratio between the largest to smallest cost on extra links is bounded,
in which case we obtain approximation factors below
The Complexity of Gradient Descent: CLS = PPAD boolean AND PLS
Full text linkWe study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain [0,1]2 is PPAD ∩ PLS-complete. This is the first non-artificial problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more "natural"counterpart to PPAD ∩ PLS and contains many interesting problems - is itself equal to PPAD ∩ PLS
A deterministic algorithm for the MST problem in constant rounds of congested clique
No full textIn this paper we show that the Minimum Spanning Tree problem (MST) can be solved deterministically in O(1) rounds of the Congested Clique model. In the Congested Clique model there are n players that perform computation in synchronous rounds. Each round consist of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange O(logn) bit messages. The studies of this model began with the MST problem: in the paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05] that defines the Congested Clique model the authors give a deterministic O(loglogn) round algorithm that improved over a trivial O(logn) round adaptation of Borůvka's algorithm. There was a sequence of gradual improvements to this result: an O(logloglogn) round algorithm by Hegeman, Pandurangan, Pemmaraju, Sardeshmukh, and Scquizzato [PODC'15], an O(log? n) round algorithm by Ghaffari and Parter, [PODC'16] and an O(1) round algorithm by Jurdzi?ski and Nowicki, [SODA'18], but all those algorithms were randomized. Therefore, the question about the existence of any deterministic o(loglogn) round algorithms for the Minimum Spanning Tree problem remains open since the seminal paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05]. Our result resolves this question and establishes that O(1) rounds is enough to solve the MST problem in the Congested Clique model, even if we are not allowed to use any randomness. Furthermore, the amount of communication needed by the algorithm makes it applicable to a variant of the MPC model using machines with local memory of size O(n). </p
Approximating Nash social welfare under rado valuations
No full textWe consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to n agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of the agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. Subsequent work has obtained constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and O(n)-approximation algorithms for subadditive valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant
Vertex deletion parameterized by elimination distance and even less
No full textWe study the parameterized complexity of various classic vertex-deletion problems such as Odd cycle transversal, Vertex planarization, and Chordal vertex deletion under hybrid parameterizations. Existing FPT algorithms for these problems either focus on the parameterization by solution size, detecting solutions of size k in time f(k) · nO(1), or width parameterizations, finding arbitrarily large optimal solutions in time f(w) · nO(1) for some width measure w like treewidth. We unify these lines of research by presenting FPT algorithms for parameterizations that can simultaneously be arbitrarily much smaller than the solution size and the treewidth. The first class of parameterizations is based on the notion of elimination distance of the input graph to the target graph class , which intuitively measures the number of rounds needed to obtain a graph in by removing one vertex from each connected component in each round. The second class of parameterizations consists of a relaxation of the notion of treewidth, allowing arbitrarily large bags that induce subgraphs belonging to the target class of the deletion problem as long as these subgraphs have small neighborhoods. Both kinds of parameterizations have been introduced recently and have already spawned several independent results. Our contribution is twofold. First, we present a framework for computing approximately optimal decompositions related to these graph measures. Namely, if the cost of an optimal decomposition is k, we show how to find a decomposition of cost kO(1) in time f(k) · nO(1). This is applicable to any class for which we can solve the so-called separation problem. Secondly, we exploit the constructed decompositions for solving vertex-deletion problems by extending ideas from algorithms using iterative compression and the finite state property. For the three mentioned vertex-deletion problems, and all problems which can be formulated as hitting a finite set of connected forbidden (a) minors or (b) (induced) subgraphs, we obtain FPT algorithms with respect to both studied parameterizations. For example, we present an algorithm running in time nO(1) + 2kO(1)·(n+m) and polynomial space for Odd cycle transversal parameterized by the elimination distance k to the class of bipartite graphs.</p
Load balancing with dynamic set of balls and bins
No full textIn dynamic load balancing, we wish to distribute balls into bins in an environment where both balls and bins can be added and removed. We want to minimize the maximum load of any bin but we also want to minimize the number of balls and bins that are affected when adding or removing a ball or a bin. We want a hashing-style solution where we given the ID of a ball can find its bin efficiently. We are given a user-specified balancing parameter c=1+?, where ?e (0,1). Let n and m be the current number of balls and bins. Then we want no bin with load above C= c n/m, referred to as the capacity of the bins. We present a scheme where we can locate a ball checking 1+O(log1/?) bins in expectation. When inserting or deleting a ball, we expect to move O(1/?) balls, and when inserting or deleting a bin, we expect to move O(C/?) balls. Previous bounds were off by a factor 1/?. The above bounds are best possible when C=O(1) but for larger C, we can do much better: We define f=? C when C? log1/?, f=?C· ?log(1/(?C)) when log1/? C<1/2?2, and f=1 when C? 1/2?2. We show that we expect to move O(1/f) balls when inserting or deleting a ball, and O(C/f) balls when inserting or deleting a bin. Moreover, when C? log1/?, we can search a ball checking only O(1) bins in expectation. For the bounds with larger C, we first have to resolve a much simpler probabilistic problem. Place n balls in m bins of capacity C, one ball at the time. Each ball picks a uniformly random non-full bin. We show that in expectation and with high probability, the fraction of non-full bins is (f). Then the expected number of bins that a new ball would have to visit to find one that is not full is (1/f). As it turns out, this is also the complexity of an insertion in our more complicated scheme where both balls and bins can be added and removed. </p
- …
