295 research outputs found
Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion
No full textThe Lovasz Local Lemma (LLL) is a powerful tool that can be used to prove that an object having none of a set of bad properties exists, using the probabilistic method. In many applications of the LLL it is also desirable to explicitly construct the combinatorial object. Recently it was shown that this is possible using a randomized algorithm in the full asymmetric LLL setting [R. Moser and G. Tardos, 2010]. A strengthening of the LLL for the case of dense local neighborhoods proved in [R. Bissacot et al., 2010] was recently also made constructive in [W. Pegden, 2011]. In another recent work [B. Haupler, B. Saha, A. Srinivasan, 2010], it was proved that the algorithm of Moser and Tardos is still efficient even when the number of events is exponential. Here we prove that these last two contributions can be combined to yield a new version of the LLL
Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
No full textThe HYBRID model was recently introduced by Augustine et al. [John Augustine et al., 2020] in order to characterize from an algorithmic standpoint the capabilities of networks which combine multiple communication modes. Concretely, it is assumed that the standard LOCAL model of distributed computing is enhanced with the feature of all-to-all communication, but with very limited bandwidth, captured by the node-capacitated clique (NCC). In this work we provide several new insights on the power of hybrid networks for fundamental problems in distributed algorithms.
First, we present a deterministic algorithm which solves any problem on a sparse n-node graph in ̃(√n) rounds of HYBRID, where the notation ̃(⋅) suppresses polylogarithmic factors of n. We combine this primitive with several sparsification techniques to obtain efficient distributed algorithms for general graphs. Most notably, for the all-pairs shortest paths problem we give deterministic (1 + ε)- and log n/log log n-approximate algorithms for unweighted and weighted graphs respectively with round complexity ̃(√n) in HYBRID, closely matching the performance of the state of the art randomized algorithm of Kuhn and Schneider [Kuhn and Schneider, 2020]. Moreover, we make a connection with the Ghaffari-Haeupler framework of low-congestion shortcuts [Mohsen Ghaffari and Bernhard Haeupler, 2016], leading - among others - to a (1 + ε)-approximate algorithm for Min-Cut after (polylog (n)) rounds, with high probability, even if we restrict local edges to transfer (log n) bits per round. Finally, we prove via a reduction from the set disjointness problem that Ω̃(n^{1/3}) rounds are required to determine the radius of an unweighted graph, as well as a (3/2 - ε)-approximation for weighted graphs. As a byproduct, we show an Ω̃(n) round-complexity lower bound for computing a (4/3 - ε)-approximation of the radius in the broadcast variant of the congested clique, even for unweighted graphs
Sample-Optimal Identity Testing with High Probability
No full textWe study the problem of testing identity against a given distribution with a focus on the high confidence regime. More precisely, given samples from an unknown distribution p over n elements, an explicitly given distribution q, and parameters 0< epsilon, delta < 1, we wish to distinguish, with probability at least 1-delta, whether the distributions are identical versus epsilon-far in total variation distance. Most prior work focused on the case that delta = Omega(1), for which the sample complexity of identity testing is known to be Theta(sqrt{n}/epsilon^2). Given such an algorithm, one can achieve arbitrarily small values of delta via black-box amplification, which multiplies the required number of samples by Theta(log(1/delta)).
We show that black-box amplification is suboptimal for any delta = o(1), and give a new identity tester that achieves the optimal sample complexity. Our new upper and lower bounds show that the optimal sample complexity of identity testing is Theta((1/epsilon^2) (sqrt{n log(1/delta)} + log(1/delta))) for any n, epsilon, and delta. For the special case of uniformity testing, where the given distribution is the uniform distribution U_n over the domain, our new tester is surprisingly simple: to test whether p = U_n versus d_{TV} (p, U_n) >= epsilon, we simply threshold d_{TV}({p^}, U_n), where {p^} is the empirical probability distribution. The fact that this simple "plug-in" estimator is sample-optimal is surprising, even in the constant delta case. Indeed, it was believed that such a tester would not attain sublinear sample complexity even for constant values of epsilon and delta.
An important contribution of this work lies in the analysis techniques that we introduce in this context. First, we exploit an underlying strong convexity property to bound from below the expectation gap in the completeness and soundness cases. Second, we give a new, fast method for obtaining provably correct empirical estimates of the true worst-case failure probability for a broad class of uniformity testing statistics over all possible input distributions - including all previously studied statistics for this problem. We believe that our novel analysis techniques will be useful for other distribution testing problems as well
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
No full textIn this paper, we refine the (almost) \emph{existentially optimal}
distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng,
Sun, and Ye (FOCS `21) into an (almost) \emph{universally optimal} distributed
Laplacian solver.
Specifically, when the topology is known, we show that any Laplacian system
on an -node graph with \emph{shortcut quality} can be solved
within rounds, where
is the required accuracy. This almost matches our lower bound which guarantees
that any correct algorithm on requires
rounds, even for a crude solution with . Even in the
unknown-topology case (i.e., standard CONGEST), the same bounds also hold in
most networks of interest. Furthermore, conditional on conjectured improvements
in state-of-the-art constructions of low-congestion shortcuts, the CONGEST
results will match the known-topology ones.
Moreover, following a recent line of work in distributed algorithms, we
consider a hybrid communication model which enhances CONGEST with limited
global power in the form of the node-capacitated clique (NCC) model. In this
model, we show the existence of a Laplacian solver with round complexity
.
The unifying thread of these results, and our main technical contribution, is
the study of novel \emph{congested} generalization of the standard
\emph{part-wise aggregation} problem. We develop near-optimal algorithms for
this primitive in the Supported-CONGEST model, almost-optimal algorithms in
(standard) CONGEST, as well as a very simple algorithm for bounded-treewidth
graphs with slightly worse bounds. This primitive can be readily used to
accelerate the FOCS`21 Laplacian solver. We believe this primitive will find
further independent applications
Testing Shape Restrictions of Discrete Distributions
No full textWe study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution D over [n] and a property P, the goal is to distinguish between D ∈ P and `1(D,P) > ε. We develop a general algorithm for this question, which applies to a large range of “shape-constrained” properties, including monotone,log-concave, t-modal, piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all cases considered, our algorithm has near-optimal sample complexity with regard to the domain size and is computationally efficient. For most of these classes, we provide the first non-trivial tester in the literature. In addition, we also describe a generic method to prove lower bounds for this problem, and use it to show our upper bounds are nearly tight. Finally, we extend some of our techniques to tolerant testing, deriving nearly–tight upper and lower bounds for the corresponding questions
Sampling correctors
No full textIn many situations, sample data is obtained from a noisy or imperfect source. In order to address such corruptions, this paper introduces the concept of a sampling corrector. Such algorithms use structure that the distribution is purported to have, in order to allow one to make "on-the-fly" corrections to samples drawn from probability distributions. These algorithms then act as filters between the noisy data and the end user.
We show connections between sampling correctors, distribution learning algorithms, and distribution property testing algorithms. We show that these connections can be utilized to expand the applicability of known distribution learning and property testing algorithms as well as to achieve improved algorithms for those tasks. As a first step, we show how to design sampling correctors using proper learning algorithms. We then focus on the question of whether algorithms for sampling correctors can be more efficient in terms of sample complexity than learning algorithms for the analogous families of distributions. When correcting monotonicity, we show that this is indeed the case when also granted query access to the cumulative distribution function. We also obtain sampling correctors for monotonicity without this stronger type of access, provided that the distribution be originally very close to monotone (namely, at a distance O(1/log2 n)). In addition to that, we consider a restricted error model that aims at capturing "missing data" corruptions. In this model, we show that distributions that are close to monotone have sampling correctors that are significantly more efficient than achievable by the learning approach. We then consider the question of whether an additional source of independent random bits is required by sampling correctors to implement the correction process. We show that for correcting close-to-uniform distributions and close-to-monotone distributions, no additional source of random bits is required, as the samples from the input source itself can be used to produce this randomness
Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else
No full textWe study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric space. The goal is, starting from a particular point of the metric space (the origin), to serve all these requests while minimizing the total time spent. The server moves with unit speed or is "waiting" (zero speed) at some location. We consider two variants: in the open variant, the goal is achieved when the last request is served. In the closed one, the server additionally has to return to the origin. We adopt a prediction model, introduced for OLTSP on the line [Gouleakis et al., 2023], in which the predictions correspond to the locations of the requests and extend it to more general metric spaces.
We first propose an oracle-based algorithmic framework, inspired by previous work [Bampis et al., 2023]. This framework allows us to design online algorithms for general metric spaces that provide competitive ratio guarantees which, given perfect predictions, beat the best possible classical guarantee (consistency). Moreover, they degrade gracefully along with the increase in error (smoothness), but always within a constant factor of the best known competitive ratio in the classical case (robustness).
Having reduced the problem to designing suitable efficient oracles, we describe how to achieve this for general metric spaces as well as specific metric spaces (rings, trees and flowers), the resulting algorithms being tractable in the latter case. The consistency guarantees of our algorithms are tight in almost all cases, and their smoothness guarantees only suffer a linear dependency on the error, which we show is necessary. Finally, we provide robustness guarantees improving previous results
Global Magnetospheric Response to an Interplanetary Shock: THEMIS Observations
No full textWe investigate the global response of geospace plasma environment to an interplanetary shock at approx. 0224 UT on May 28, 2008 from multiple THEMIS spacecraft observations in the magnetosheath (THEMIS B and C) and the mid-afternoon (THEMIS A) and dusk magnetosphere (THEMIS D and E). The interaction of the transmitted interplanetary shock with the magnetosphere has global effects. Consequently, it can affect geospace plasma significantly. After interacting with the bow shock, the interplanetary shock transmitted a fast shock and a discontinuity which propagated through the magnetosheath toward the Earth at speeds of 300 km/s and 137 km/s respectively. THEMIS A observations indicate that the plasmaspheric plume changed significantly by the interplanetary shock impact. The plasmaspheric plume density increased rapidly from 10 to 100/ cubic cm in 4 min and the ion distribution changed from isotropic to strongly anisotropic distribution. Electromagnetic ion cyclotron (EMIC) waves observed by THEMIS A are most likely excited by the anisotropic ion distributions caused by the interplanetary shock impact. To our best knowledge, this is the first direct observation of the plasmaspheric plume response to an interplanetary shock's impact. THEMIS A, but not D or E, observed a plasmaspheric plume in the dayside magnetosphere. Multiple spacecraft observations indicate that the dawn-side edge of the plasmaspheric plume was located between THEMIS A and D (or E)
Magnetopause reconnection across wide local time
No full textDuring April to July 2007 a combination of 10 spacecraft provided simultaneous monitoring of the dayside magnetopause across a wide range of local times. The array of four Cluster spacecraft, separated at large distances (10 000 km), were traversing the dawn-side magnetopause at high and low latitudes; the five THEMIS spacecraft were often in a 4 + 1 grouped configuration, traversing the low latitude, dusk-side magnetosphere, and the Double star, TC-1 spacecraft was in an equatorial orbit between the local times of the THEMIS and Cluster orbits. We show here a number of near simultaneous conjunctions of all 10 spacecraft at the magnetopause. One conjunction identifies an extended magnetic reconnection X-line, tilted in the low latitude, sub-solar region, which exists together with active anti-parallel reconnection sites extending to locations on the dawn-side flank. Oppositely moving FTE's are observed on all spacecraft, consistent with the initially strong IMF By conditions and the comparative locations of the spacecraft both dusk-ward and dawn-ward of noon. Comparison with other conjunctions of magnetopause crossings, which are also distributed over wide local times, supports the result that reconnection activity may occur at many sites simultaneously across the sub-solar and flank magnetopause, but linked to the large scale (extended) configuration of the merging line; broadly depending on IMF orientation. The occurrence of MR therefore inherently follows a "component" driven scenario irrespective of the guide field conditions. Some conjunctions allow the global magnetopause response to IMF changes to be observed and the distribution of spacecraft can directly confirm its shape, motion and deformation at local noon, dawn and dusk-side, simultaneously
Current reduction in a pseudo-breakup event: THEMIS observations
No full textPseudo-breakup events are thought to be generated by the same physical processes as substorms. This paper reports on the cross-tail current reduction in an isolated pseudo-breakup observed by three of the THEMIS probes (THEMIS A (THA), THEMIS D (THD), and THEMIS E (THE)) on 22 March 2010. During this pseudo-breakup, several localized auroral intensifications were seen by ground-based observatories. Using the unique spatial configuration of the three THEMIS probes, we have estimated the inertial and diamagnetic currents in the near-Earth plasma sheet associated with flow braking and diversion. We found the diamagnetic current to be the major contributor to the current reduction in this pseudo-breakup event. During flow braking, the plasma pressure was reinforced, and a weak electrojet and an auroral intensification appeared. After flow braking/diversion, the electrojet was enhanced, and a new auroral intensification was seen. The peak current intensity of the electrojet estimated from ground-based magnetometers, ~0.7 × 105 A, was about 1 order of magnitude lower than that in a typical substorm. We suggest that this pseudo-breakup event involved two dynamical processes: a current-reduction associated with plasma compression ahead of the earthward flow and a current-disruption related to the flow braking/diversion. Both processes are closely connected to the fundamental interaction between fast flows, the near-Earth ambient plasma, and the magnetic field
- …
