More Like this

1. Local Existence, lower mass bounds, and a new continuation criterion for the Landau equation

   Henderson, Christopher; Snelson, Stanley; Tarfulea, Andrei. (January 2019, Journal of differential equations)

   We consider the spatially inhomogeneous Landau equation with soft potentials. First, we establish the short-time existence of solutions, assuming the initial data has sufficient decay in the velocity variable and regularity (no decay assumptions are made in the spatial variable). Next, we show that the evolution instantaneously spreads mass throughout the domain. The resulting lower bounds are sub-Gaussian, which we show is optimal. The proof of mass-spreading is based on a stochastic process, and makes essential use of nonlocality. By combining this theorem with prior results, we derive two important applications: $$C^\infty$$-smoothing, even for initial data with vacuum regions, and a continuation criterion (the solution can be extended as long as the mass and energy densities stay bounded from above). This is the weakest condition known to prevent blow-up. In particular, it does not require a lower bound on the mass density or an upper bound on the entropy density. 

   more » « less
2. Efficient Interactive Proofs for Non-Deterministic Bounded Space

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.47  

   Cook, Joshua; Rothblum, Ron D. (September 2023, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023))

   Megow, Nicole; Smith, Adam (Ed.)

   The celebrated IP = PSPACE Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch’s Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols for nondeterministic algorithms directly to get faster verifiers. More specifically, for any non-deterministic space S algorithm, we construct an interactive proof in which the verifier runs in time Õ(n+S²). This improves on the best previous bound of Õ(n+S³) and matches the result for deterministic space bounded algorithms, up to polylog(S) factors. We further generalize to alternating bounded space algorithms. For any language L decided by a time T, space S algorithm that uses d alternations, we construct an interactive proof in which the verifier runs in time Õ(n + S log(T) + S d) and the prover runs in time 2^O(S). For d = O(log(T)), this matches the best known interactive proofs for deterministic algorithms, up to polylog(S) factors, and improves on the previous best verifier time for nondeterministic algorithms by a factor of log(T). We also improve the best prior verifier time for unbounded alternations by a factor of S. Using known connections of bounded alternation algorithms to bounded depth circuits, we also obtain faster verifiers for bounded depth circuits with unbounded fan-in. 

   more » « less
3. Pseudorandomness, Symmetry, Smoothing: I

   https://doi.org/10.4230/LIPICS.CCC.2024.18  

   Derksen, Harm; Ivanov, Peter; Lee, Chin Ho; Viola, Emanuele (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that - achieve an optimal lower bound on their statistical distance to any bounded-uniform distribution. This closes a line of research initiated by Alon, Goldreich, and Mansour in 2003, and improves on a result by O'Donnell and Zhao. - have heavier tail mass than the uniform distribution. This answers a question posed by several researchers including Bun and Steinke. - rule out a popular paradigm for constructing pseudorandom generators, originating in a 1989 work by Ajtai and Wigderson. This again answers a question raised by several researchers. For branching programs, our result matches a bound by Forbes and Kelley. Our small-bias distributions above are symmetric. We show that the xor of any two symmetric small-bias distributions fools any bounded function. Hence our examples cannot be extended to the xor of two small-bias distributions, another popular paradigm whose power remains unknown. We also generalize and simplify the proof of a result of Bazzi. 

   more » « less
4. Gardner formula for Ising perceptron models at small densities

   Bolthausen, E.; Nakajima, S; Sun, N; Xu, C (January 2022, Conference on Learning Theory)

   We consider the Ising perceptron model with N spins and M = N*alpha patterns, with a general activation function U that is bounded above. For U bounded away from zero, or U a one-sided threshold function, it was shown by Talagrand (2000, 2011) that for small densities alpha, the free energy of the model converges in the large-N limit to the replica symmetric formula conjectured in the physics literature (Krauth–Mezard 1989, see also Gardner–Derrida 1988). We give a new proof of this result, which covers the more general class of all functions U that are bounded above and satisfy a certain variance bound. The proof uses the (first and second) moment method conditional on the approximate message passing iterates of the model. In order to deduce our main theorem, we also prove a new concentration result for the perceptron model in the case where U is not bounded away from zero. 

   more » « less
5. Conformal equivalence of visual metrics in pseudoconvex domains

   https://doi.org/10.1007/s00208-020-01962-1  

   Capogna, Luca; Le Donne, Enrico (January 2021, Mathematische Annalen)

   null (Ed.)

   We refine estimates introduced by Balogh and Bonk, to show that the boundary exten- sions of isometries between bounded, smooth strongly pseudoconvex domains in Cn are conformal with respect to the sub-Riemannian metric induced by the Levi form. As a corollary we obtain an alternative proof of a result of Fefferman on smooth exten- sions of biholomorphic mappings between bounded smooth pseudoconvex domains. The proofs are inspired by Mostow’s proof of his rigidity theorem and are based on the asymptotic hyperbolic character of the Kobayashi or Bergman metrics and on the Bonk-Schramm hyperbolic fillings. 

   more » « less