More Like this

1. Stability and chaos in dynamical last passage percolation

   https://doi.org/10.1090/cams/35  

   Ganguly, Shirshendu; Hammond, Alan (June 2024, Communications of the American Mathematical Society)

   Many complex disordered systems in statistical mechanics are characterized by intricate energy landscapes. The ground state, the configuration with lowest energy, lies at the base of the deepest valley. In important examples, such as Gaussian polymers and spin glass models, the landscape has many valleys and the abundance of near-ground states (at the base of valleys) indicates the phenomenon ofchaos, under which the ground state alters profoundly when the disorder of the model is slightly perturbed. In this article, we compute the critical exponent that governs the onset of chaos in a dynamic manifestation of a canonical model in the Kardar-Parisi-Zhang [KPZ] universality class, Brownian last passage percolation [LPP]. In this model in its static form, semidiscrete polymers advance through Brownian noise, their energy given by the integral of the white noise encountered along their journey. A ground state is ageodesic, of extremal energy given its endpoints. We perturb Brownian LPP by evolving the disorder under an Ornstein-Uhlenbeck flow. We prove that, for polymers of length $n$, a sharp phase transition marking the onset of chaos is witnessed at the critical time $n^{-<\#comment/>1/3}$. Indeed, the overlap between the geodesics at times zero and $t>0$that travel a given distance of order $n$will be shown to be of order $n$when $t\ll <\#comment/>n^{-<\#comment/>1/3}$; and to be of smaller order when $t\gg <\#comment/>n^{-<\#comment/>1/3}$. We expect this exponent to be universal across a wide range of interface models. The present work thus sheds light on the dynamical aspect of the KPZ class; it builds on several recent advances. These include Chatterjee’s harmonic analytic theory [Superconcentration and related topics, Springer, Cham, 2014] of equivalence ofsuperconcentrationandchaosin Gaussian spaces; a refined understanding of the static landscape geometry of Brownian LPP developed in the companion paper (see S. Ganguly and A. Hammond [Electron. J. Probab. 28 (2023), 80 pp.]); and, underlying the latter, strong comparison estimates of the geodesic energy profile to Brownian motion (see J. Calvert, A. Hammond, and M. Hegde [Astérisque 441 (2023), pp. v+119]). 

   more » « less
2. Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams

   Bera, Suman K; Chakrabarti, Amit (March 2017, 34th Symposium on Theoretical Aspects of Computer Science)

   We revisit the much-studied problem of space-efficiently estimating the number of triangles in a graph stream, and extensions of this problem to counting fixed-sized cliques and cycles, obtaining a number of new upper and lower bounds. For the important special case of counting triangles, we give a $$4$$-pass, $$(1\pm\varepsilon)$$-approximate, randomized algorithm that needs at most $$\widetilde{O}(\varepsilon^{-2}\cdot m^{3/2}/T)$$ space, where $$m$$ is the number of edges and $$T$$ is a promised lower bound on the number of triangles. This matches the space bound of a very recent algorithm (McGregor et al., PODS 2016), with an arguably simpler and more general technique. We give an improved multi-pass lower bound of $$\Omega(\min\{m^{3/2}/T, m/\sqrt{T}\})$$, applicable at essentially all densities $$\Omega(n) \le m \le O(n^2)$$. We also prove other multi-pass lower bounds in terms of various structural parameters of the input graph. Together, our results resolve a couple of open questions raised in recent work (Braverman et al., ICALP 2013). Our presentation emphasizes more general frameworks, for both upper and lower bounds. We give a sampling algorithm for counting arbitrary subgraphs and then improve it via combinatorial means in the special cases of counting odd cliques and odd cycles. Our results show that these problems are considerably easier in the cash-register streaming model than in the turnstile model, where previous work had focused (Manjunath et al., ESA 2011; Kane et al., ICALP 2012). We use Tur{\'a}n graphs and related gadgets to derive lower bounds for counting cliques and cycles, with triangle-counting lower bounds following as a corollary. 

   more » « less
3. Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs

   https://doi.org/10.1145/3695839  

   Im, Sungjin; Moseley, Benjamin; Ngo, Hung Q; Pruhs, Kirk (November 2024, Proceedings of the ACM on Management of Data)

   Datalog^ois an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Like Datalog, Datalogo programs can be evaluated via the natural iterative algorithm until a fixed point is reached. However unlike Datalog, the natural iterative evaluation of some Datalogo programs over some semirings may not converge. It is known that the commutative semirings for which the iterative evaluation of Datalogo programs is guaranteed to converge are exactly those semirings that are stable. Previously, the best known upper bound on the number of iterations until convergence over p-stable semirings is ∑i=1 ^n (p+2)ⁱ= Θ(pⁿ) steps, where n is (essentially) the output size. We establish that, in fact, the natural iterative evaluation of a Datalogo program over a p-stable semiring converges within a polynomial number of iterations. In particular our upper bound is O(σ p n²( n²lg Λ + lg σ)) where σ is the number of elements in the semiring present in either the input databases or the Datalogo program, and λ is the maximum number of terms in any product in the Datalogo program. 

   more » « less
4. Bandits with Stochastic Experts: Constant Regret, Empirical Experts and Episodes

   https://doi.org/10.1145/3680279  

   Sharma, Nihal; Sen, Rajat; Basu, Soumya; Shanmugam, Karthikeyan; Shakkottai, Sanjay (September 2024, ACM Transactions on Modeling and Performance Evaluation of Computing Systems)

   We study a variant of the contextual bandit problem where an agent can intervene through a set of stochastic expert policies. Given a fixed context, each expert samples actions from a fixed conditional distribution. The agent seeks to remain competitive with the “best” among the given set of experts. We propose the Divergence-based Upper Confidence Bound (D-UCB) algorithm that uses importance sampling to share information across experts and provide horizon-independent constant regret bounds that only scale linearly in the number of experts. We also provide the Empirical D-UCB (ED-UCB) algorithm that can function with only approximate knowledge of expert distributions. Further, we investigate the episodic setting where the agent interacts with an environment that changes over episodes. Each episode can have different context and reward distributions resulting in the best expert changing across episodes. We show that by bootstrapping from\(\mathcal {O}(N\log (NT^2\sqrt {E}))\)samples, ED-UCB guarantees a regret that scales as\(\mathcal {O}(E(N+1) + \frac{N\sqrt {E}}{T^2})\)forNexperts overEepisodes, each of lengthT. We finally empirically validate our findings through simulations. 

   more » « less
5. Matrix Schubert varieties, binomial ideals, and reduced Gröbner bases

   https://doi.org/10.1090/proc/17175  

   Stelzer, Ada (July 2025, Proceedings of the American Mathematical Society)

   We prove a sharp lower bound on the number of terms in an element of the reduced Gröbner basis of a Schubert determinantal ideal $I_w$under the term order of Knutson–Miller [Ann. of Math. (2) 161 (2005), pp. 1245–1318]. We give three applications. First, we give a pattern-avoidance characterization of the matrix Schubert varieties whose defining ideals are binomial. This complements a result of Escobar–Mészáros [Proc. Amer. Math. Soc. 144 (2016), pp. 5081–5096] on matrix Schubert varieties that are toric with respect to their natural torus action. Second, we give a combinatorial proof that the recent formulas of Rajchgot–Robichaux–Weigandt [J. Algebra 617 (2023), pp. 160–191] and Almousa–Dochtermann–Smith [Preprint, arXiv:2209.09851, 2022] computing the Castelnuovo–Mumford regularity of vexillary $I_w$and toric edge ideals of bipartite graphs respectively agree for binomial $I_w$. Third, we demonstrate that the Gröbner basis for $I_w$given by the minimal generators of Gao–Yong [J. Commut. Algebra 16 (2024), pp. 267–273] is reduced if and only if the defining permutation $w$is vexillary. 

   more » « less