More Like this

1. New Spectral Algorithms for Refuting Smoothed k-SAT

   https://doi.org/10.1145/3635117  

   Guruswami, Venkatesan; Kothari, Pravesh K; Manohar, Peter (March 2025, Communications of the ACM)

   Despite being a quintessential example of a hard problem, the quest for finding fast algorithms for deciding satisfiability of propositional formulas has occupied computer scientists both in theory and in practice. In this article, we survey recent progress on designing algorithms with strong refutation guarantees forsmoothedinstances of the $k$-SAT problem. Smoothed instances are formed by slight random perturbations of arbitrary instances, and their study is a way to bridge the gap between worst-case and average-case models of problem instances. Our methods yield new algorithms for smoothed $k$-SAT instances with guarantees that match those for the significantly simpler and well-studied model ofrandomformulas. Additionally, they have led to a novel and unexpected line of attack on some longstanding extremal combinatorial problems in graph theory and coding theory. As an example, we will discuss the resolution of a 2008 conjecture of Feige on the existence of short cycles in hypergraphs. 

   more » « less
2. On the upper tail problem for random hypergraphs

   https://doi.org/10.1002/rsa.20975  

   Liu, Yang P.; Zhao, Yufei (November 2020, Random Structures & Algorithms)

   The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős‐Rényi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not seen in random graphs. We conjecture a formula for the large deviation rate, that is, the first order asymptotics of the log‐probability that the number of copies of fixed subgraphHin a sparse Erdős‐Rényi randomk‐uniform hypergraph exceeds its expectation by a constant factor. This conjecture turns out to be significantly more intricate compared to the case for graphs. We verify our conjecture when the fixed subgraphHbeing counted is a clique, as well as whenHis the 3‐uniform 6‐vertex 4‐edge hypergraph consisting of alternating faces of an octahedron, where new techniques are required. 

   more » « less
3. From sum of two squares to arithmetic Siegel–Weil formulas

   https://doi.org/10.1090/bull/1786  

   Li, Chao (July 2023, Bulletin of the American Mathematical Society)

   The main goal of this expository article is to survey recent progress on the arithmetic Siegel–Weil formula and its applications. We begin with the classical sum of two squares problem and put it in the context of the Siegel–Weil formula. We then motivate the geometric and arithmetic Siegel–Weil formula using the classical example of the product of modular curves. After explaining the recent result on the arithmetic Siegel–Weil formula for Shimura varieties of arbitrary dimension, we discuss some aspects of the proof and its application to the arithmetic inner product formula and the Beilinson–Bloch conjecture. Rather than being intended as a complete survey of this vast field, this article focuses more on examples and background to provide easier access to several recent works by the author with W. Zhang and Y. Liu. 

   more » « less
4. A separation theorem for simple theories

   https://doi.org/10.1090/tran/8513  

   Malliaris, M.; Shelah, S. (April 2022, Transactions of the American Mathematical Society)

   This paper builds model-theoretic tools to detect changes in complexity among the simple theories. We develop a generalization of dividing, called shearing, which depends on a so-called context c. This leads to defining c-superstability, a syntactical notion, which includes supersimplicity as a special case. The main result is a separation theorem showing that for any countable context and any two theories T1, T2, such that T1 is c-superstable and T2 is c-unsuperstable, and for arbitrarily large mu, it is possible to build models of any theory interpreting both T1 and T2 whose restriction to tau(T1) is mu-saturated and whose restriction to tau(T2) is not aleph1-saturated. (This suggests “c-superstable” is really a dividing line.) The proof uses generalized Ehrenfeucht-Mostowski models, and along the way, we clarify the use of these techniques to realize certain types while omitting others. In some sense, shearing allows us to study the interaction of complexity coming from the usual notion of dividing in simple theories and the more combinatorial complexity detected by the general definition. This work is inspired by our recent progress on Keisler’s order, but does not use ultrafilters, rather aiming to build up the internal model theory of these classes. https://doi.org/10.1090/tran/8513 

   more » « less
5. Functional central limit theorem via nonstationary projective conditions

   Florence Merlevede and Magda Peligrad (April 2023, Progress in probability)

   Radosław Adamczak, Nathael Gozlan (Ed.)

   In this paper we survey some recent progress on the Gaussian approximation for nonstationary dependent structures via martingale methods. First we present general theorems involving projective conditions for triangular arrays of random variables and then present various applications for rho-mixing and alpha-dependent triangular arrays, stationary sequences in a random time scenery, application to the quenched FCLT, application to linear statistics with alpha-dependent innovations, application to functions of a triangular stationary Markov chain. 

   more » « less