Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSherali--Adams Strikes Back
133
0
0.0
(
0
)
Added by
Tselil Schramm
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be any $n$-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by $1/sqrt{Delta}$ (for example, a random graph $G$ of average degree~$Theta(Delta)$ typically has this property). We show that the $expBig(c frac{log n}{log Delta}Big)$-round Sherali--Adams linear programming hierarchy certifies that the maximum cut in such a~$G$ is at most $50.1%$ (in fact, at most $tfrac12 + 2^{-Omega(c)}$). For example, in random graphs with $n^{1.01}$ edges, $O(1)$ rounds suffice; in random graphs with $n cdot text{polylog}(n)$ edges, $n^{O(1/log log n)} = n^{o(1)}$ rounds suffice. Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for maxcut and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constant-round Sherali--Adams can strongly refute random Boolean $k$-CSP instances with $n^{lceil k/2 rceil + delta}$ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.
rate research
Read More
Given a pair of graphs $textbf{A}$ and $textbf{B}$, the problems of deciding whether there exists either a homomorphism or an isomorphism from $textbf{A}$ to $textbf{B}$ have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where $textbf{A}$ and $textbf{B}$ are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy.
In the classical Online Metric Matching problem, we are given a metric space with $k$ servers. A collection of clients arrive in an online fashion, and upon arrival, a client should irrevocably be matched to an as-yet-unmatched server. The goal is to find an online matching which minimizes the total cost, i.e., the sum of distances between each client and the server it is matched to. We know deterministic algorithms~cite{KP93,khuller1994line} that achieve a competitive ratio of $2k-1$, and this bound is tight for deterministic algorithms. The problem has also long been considered in specialized metrics such as the line metric or metrics of bounded doubling dimension, with the current best result on a line metric being a deterministic $O(log k)$ competitive algorithm~cite{raghvendra2018optimal}. Obtaining (or refuting) $O(log k)$-competitive algorithms in general metrics and constant-competitive algorithms on the line metric have been long-standing open questions in this area. In this paper, we investigate the robustness of these lower bounds by considering the Online Metric Matching with Recourse problem where we are allowed to change a small number of previous assignments upon arrival of a new client. Indeed, we show that a small logarithmic amount of recourse can significantly improve the quality of matchings we can maintain. For general metrics, we show a simple emph{deterministic} $O(log k)$-competitive algorithm with $O(log k)$-amortized recourse, an exponential improvement over the $2k-1$ lower bound when no recourse is allowed. We next consider the line metric, and present a deterministic algorithm which is $3$-competitive and has $O(log k)$-recourse, again a substantial improvement over the best known $O(log k)$-competitive algorithm when no recourse is allowed.
In this short presentation I emphasize the increased importance of kaon flavour physics in the search for new physics (NP) that we should witness in the rest of this decade and in the next decade. The main actors will be the branching ratios for the rare decays $K^+rightarrowpi^+ ubar u$ and $K_{L}rightarrowpi^0 ubar u$, to be measured by NA62 and KOTO, and their correlations with the ratio $varepsilon/varepsilon$ on which recently progress by lattice QCD and large $N$ dual QCD approach has been made implying a new flavour anomaly. Further correlations of $K^+rightarrowpi^+ ubar u$, $K_{L}rightarrowpi^0 ubar u$ and $varepsilon/varepsilon$ with $varepsilon_K$, $Delta M_K$, $K_Ltomu^+mu^-$ and $K_Ltopi^0ell^+ell^-$ will help us to identify indirectly possible NP at short distance scales. This talk summarizes the present highlights of this fascinating field including some results from concrete NP scenarios.
This paper studies new properties of the front and back ends of a sorting network, and illustrates the utility of these in the search for new bounds on optimal sorting networks. Search focuses first on the outsides of the network and then on the inner part. All previous works focus only on properties of the front end of networks and on how to apply these to break symmetries in the search. The new, out-side-in, properties help shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimal sorting networks. We present new parallel sorting networks for 17 to 20 inputs. For 17, 19, and 20 inputs these networks are faster than the previously known best networks. For 17 inputs, the new sorting network is shown optimal in the sense that no sorting network using less layers exists.
In the conventional view of type II migration, a giant planet migrates inward in the viscous velocity of the accretion disc in the so-call disc-dominate case. Recent hydrodynamic simulations, however, showed that planets migrate with velocities much faster than the viscous one in massive discs. Such fast migration cannot be explained by the conventional picture. Scardoni et al. (2020) has recently argued this new picture. By carrying out similar hydrodynamic simulations, they found that the migration velocity slows down with time and eventually reaches the prediction by the conventional theory. They interpreted the fast migration as an initial transient one and concluded that the conventional type II migration is realised after the transient phase. We show that the migration velocities obtained by Scardoni et al. (2020) are consistent with the previous simulations even in the transient phase that they proposed. We also find that the transient fast migration proposed by Scardoni et al. (2020) is well described by a new model of Kanagawa et al. (2018). The new model can appropriately describe significant inward migration during the initial transient phase that Scardoni et al. (2020) termed. Hence, we conclude that the time-variation of the transient migration velocity is due to the changes of the orbital radius of the planet and its background surface density during the migration.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
