**arxiv**4004

[1906.06732] The SDP value for random two-eigenvalue CSPs

12 hours ago by louigi

The SDP value for random two-eigenvalue CSPs. (arXiv:1906.06732v1 [cs.DS]) http://bit.ly/2IT22hO

We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, ``two-eigenvalue 2CSPs''. We show this SDP value coincides with the spectral relaxation value, possibly indicating a computational threshold. Our analysis extends the previously resolved cases of random regular $\mathsf{2XOR}$ and $\textsf{NAE-3SAT}$, and includes new cases such as random $\mathsf{Sort}_4$ (equivalently, $\mathsf{CHSH}$) and $\mathsf{Forrelation}$ CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara--Bass Formula, and the Friedman/Bordenave proof of Alon's Conjecture.

arXiv
We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, ``two-eigenvalue 2CSPs''. We show this SDP value coincides with the spectral relaxation value, possibly indicating a computational threshold. Our analysis extends the previously resolved cases of random regular $\mathsf{2XOR}$ and $\textsf{NAE-3SAT}$, and includes new cases such as random $\mathsf{Sort}_4$ (equivalently, $\mathsf{CHSH}$) and $\mathsf{Forrelation}$ CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara--Bass Formula, and the Friedman/Bordenave proof of Alon's Conjecture.

12 hours ago by louigi

[1906.06405] Box-ball system: soliton and tree decomposition of excursions

12 hours ago by louigi

Box-ball system: soliton and tree decomposition of excursions. (arXiv:1906.06405v1 [math.PR]) http://bit.ly/2x1nUC8

We review combinatorial properties of solitons of the Box-Ball system introduced by Takahashi and Satsuma. Starting with several definitions of the system, we describe ways to identify solitons and review a proof of the conservation of the solitons under the dynamics. Ferrari, Nguyen, Rolla and Wang proposed a soliton decomposition of an excursion over the current minima of the walk representative of a ball configuration. Building on this approach, we propose a new soliton decomposition which is equivalent to the classical branch decomposition of the tree associated to the excursion. When the ball occupation numbers are independent Bernoulli variables of parameter $\lambda<1/2$, the representative is a simple random walk with negative drift $2\lambda-1$ and infinitely many excursions. The soliton decomposition of that walk consists on independent double-infinite vectors of iid geometric random variables, property shared by the branch decomposition of the excursion trees of the random walk.

arXiv
We review combinatorial properties of solitons of the Box-Ball system introduced by Takahashi and Satsuma. Starting with several definitions of the system, we describe ways to identify solitons and review a proof of the conservation of the solitons under the dynamics. Ferrari, Nguyen, Rolla and Wang proposed a soliton decomposition of an excursion over the current minima of the walk representative of a ball configuration. Building on this approach, we propose a new soliton decomposition which is equivalent to the classical branch decomposition of the tree associated to the excursion. When the ball occupation numbers are independent Bernoulli variables of parameter $\lambda<1/2$, the representative is a simple random walk with negative drift $2\lambda-1$ and infinitely many excursions. The soliton decomposition of that walk consists on independent double-infinite vectors of iid geometric random variables, property shared by the branch decomposition of the excursion trees of the random walk.

12 hours ago by louigi

[1906.05502] Localization in Gaussian disordered systems at low temperature

4 days ago by louigi

Localization in Gaussian disordered systems at low temperature. (arXiv:1906.05502v1 [math.PR]) http://bit.ly/2IGzRCO

For a broad class of Gaussian disordered systems at low temperature, we show that the Gibbs measure is asymptotically localized in small neighborhoods of a small number of states. From a single argument, we obtain (i) a version of "complete" path localization for directed polymers that is not available even for exactly solvable models; and (ii) a result about the exhaustiveness of Gibbs states in spin glasses not requiring the Ghirlanda-Guerra identities.

arXiv
For a broad class of Gaussian disordered systems at low temperature, we show that the Gibbs measure is asymptotically localized in small neighborhoods of a small number of states. From a single argument, we obtain (i) a version of "complete" path localization for directed polymers that is not available even for exactly solvable models; and (ii) a result about the exhaustiveness of Gibbs states in spin glasses not requiring the Ghirlanda-Guerra identities.

4 days ago by louigi

[1906.05037] Activated Random Walks on $mathbb{Z}^d$

5 days ago by louigi

Activated Random Walks on $\mathbb{Z}^d$. (arXiv:1906.05037v1 [math.PR]) http://bit.ly/2WCw2IF

Some stochastic systems are particularly interesting as they exhibit critical behavior without fine-tuning of a parameter, a phenomenon called self-organized criticality. In the context of driven-dissipative steady states, one of the main models is that of Activated Random Walks. Long-range effects intrinsic to the conservative dynamics and lack of a simple algebraic structure cause standard tools and techniques to break down. This makes the mathematical study of this model remarkably challenging. Yet, some exciting progress has been made in the last ten years, with of a framework of tools and methods which is finally becoming more structured. In these lecture notes we present the existing results and reproduce the techniques developed so far.

arXiv
Some stochastic systems are particularly interesting as they exhibit critical behavior without fine-tuning of a parameter, a phenomenon called self-organized criticality. In the context of driven-dissipative steady states, one of the main models is that of Activated Random Walks. Long-range effects intrinsic to the conservative dynamics and lack of a simple algebraic structure cause standard tools and techniques to break down. This makes the mathematical study of this model remarkably challenging. Yet, some exciting progress has been made in the last ten years, with of a framework of tools and methods which is finally becoming more structured. In these lecture notes we present the existing results and reproduce the techniques developed so far.

5 days ago by louigi

**related tags**

Copy this bookmark: