We consider the totally asymmetric simple exclusion process in a critical scaling parametrized by @math , which creates a shock in the particle density of order @math @math the observation time. When starting from step initial data, we provide bounds on the limiting law which in particular imply that in the double limit @math one recovers the product limit law and the degeneration of the correlation length observed at shocks of order @math . This result is shown to apply to a general last-passage percolation model. We also obtain bounds on the two-point functions of several @math processes.
A result we shall use repeatedly in this paper concerns the transversal fluctuations of the maximizer @math when @math are i.i.d. and @math there are bounds on the probability that the maximizer @math from @math to a point @math deviates more than @math from the straight line @math , @math . This is a result from @cite_11 and cited here as Theorem 3.2. Furthermore, for line-to-point problems, we have detailed control over the distribution of the (random) starting point of @math , see @cite_4 , Lemma 1.1, Lemma 1.2 and also (4.18) in @cite_1 .
@cite_1 @cite_4 @cite_11
2963279081 2952647761 117385580
We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . Given two graphs @math and @math , the Subgraph Isomorphism problem asks if @math is isomorphic to a subgraph of @math . While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time @math using the color-coding technique of Alon, Yuster, and Zwick; (2) in time @math using Courcelle's Theorem; (3) in time @math using a result on first-order model checking by Frick and Grohe; or (4) in time @math for connected @math using the algorithm of Matou s ek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of @math and @math (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time [ f_1(p_1,p_2,..., p_ ) n^ f_2(p_ +1 ,..., p_k) ] exist, where each of @math is one of the 10 parameters depending only on @math or @math . We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of @math gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when @math is a bounded-degree tree of constant pathwidth and @math is a planar graph of bounded pathwidth. The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as @math , etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical @math -Coloring . A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the @math -level Hierarchical @math -Coloring problem is @math , for @math . The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized @math -time algorithm solving the LCL can be transformed into a deterministic @math -time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges @math --- @math or @math --- @math . 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in @math time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be @math and @math . We study competing first passage percolation on graphs generated by the configuration model. At time 0, vertex 1 and vertex 2 are infected with the type 1 and the type 2 infection, respectively, and an uninfected vertex then becomes type 1 (2) infected at rate @math ( @math ) times the number of edges connecting it to a type 1 (2) infected neighbor. Our main result is that, if the degree distribution is a power-law with exponent @math , then, as the number of vertices tends to infinity and with high probability, one of the infection types will occupy all but a finite number of vertices. Furthermore, which one of the infections wins is random and both infections have a positive probability of winning regardless of the values of @math and @math . The picture is similar with multiple starting points for the infections.