More Like this

1. Intersecting sets in probability spaces and Shelah’s classification

   Chernikov, Artem; Towsner, Henry (July 2024, 14th Panhellenic Logic Symposium)

   For n ∈ N and ε > 0, given a sufficiently long sequence of events in a probability space all of measure at least ε, some n of them will have a common intersection. A more subtle pattern: for any 0 < p < q < 1, we cannot find events Ai and Bi so that μ (Ai ∩ Bj ) ≤ p and μ (Aj ∩ Bi ) ≥ q for all 1 < i < j < n, assuming n is sufficiently large. This is closely connected to model-theoretic stability of probability algebras. We survey some results from our recent work in [7] on more complicated patterns that arise when our events are indexed by multiple indices. In particular, how such results are connected to higher arity generalizations of de Finetti’s theorem in probability, structural Ramsey theory, hypergraph regularity in combinatorics, and model theory. 

   more » « less
2. Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization

   Dey, Papri; Kannan, Ravi; Ryder, Nick; Srivastava, Nikhil (January 2023, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023))

   We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An Õ(n^{ω+3}a+n⁴a²+n^ωlog(1/ε)) time algorithm for finding an ε-approximation to the Jordan Normal form of an integer matrix with a-bit entries, where ω is the exponent of matrix multiplication. (2) An Õ(n⁶d⁶a+n⁴d⁴a²+n³d³log(1/ε)) time algorithm for ε-approximately computing the spectral factorization P(x) = Q^*(x)Q(x) of a given monic n× n rational matrix polynomial of degree 2d with rational a-bit coefficients having a-bit common denominators, which satisfies P(x)⪰0 for all real x. The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in n of degree at least twelve [Cai, 1994]. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself. 

   more » « less
3. A PDE hierarchy for directed polymers in random environments

   https://doi.org/10.1088/1361-6544/ac23b7  

   Gu, Yu; Henderson, Christopher (September 2021, Nonlinearity)

   Abstract For a Brownian directed polymer in a Gaussian random environment, with q ( t , ⋅) denoting the quenched endpoint density and Q n ( t , x 1 , … , x n ) = E [ q ( t , x 1 ) … q ( t , x n ) ] , we derive a hierarchical PDE system satisfied by { Q n } n ⩾ 1 . We present two applications of the system: (i) we compute the generator of { μ t ( d x ) = q ( t , x ) d x } t ⩾ 0 for some special functionals, where { μ t ( d x ) } t ⩾ 0 is viewed as a Markov process taking values in the space of probability measures; (ii) in the high temperature regime with d ⩾ 3, we prove a quantitative central limit theorem for the annealed endpoint distribution of the diffusively rescaled polymer path. We also study a nonlocal diffusion-reaction equation motivated by the generator and establish a super-diffusive O ( t 2/3 ) scaling. 

   more » « less
4. Convex Polygon Containment: Improving Quadratic to Near Linear Time

   https://doi.org/10.4230/LIPIcs.SoCG.2024.34  

   Chan, Timothy M; Hair, Isaac M (June 2024, Proc. 40th Sympos. Computational Geometry (SoCG))

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   We revisit a standard polygon containment problem: given a convex k-gon P and a convex n-gon Q in the plane, find a placement of P inside Q under translation and rotation (if it exists), or more generally, find the largest copy of P inside Q under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir (1998) all required Ω(n²) time, even in the simplest k = 3 case. We present a significantly faster new algorithm for k = 3 achieving O(n polylog n) running time. Moreover, we extend the result for general k, achieving O(k^O(1/ε) n^{1+ε}) running time for any ε > 0. Along the way, we also prove a new O(k^O(1) n polylog n) bound on the number of similar copies of P inside Q that have 4 vertices of P in contact with the boundary of Q (assuming general position input), disproving a conjecture by Agarwal, Amenta, and Sharir (1998). 

   more » « less
5. Fast and Exact Convex Hull Simplification

   https://doi.org/10.4230/LIPIcs.FSTTCS.2021.26  

   Klimenko, Georgiy; Raichel, Benjamin (October 2021, Foundations of Software Technology and Theoretical Computer Science (FSTTCS))

   Bojanczyk, Mikolaj; Chekuri, Chandra (Ed.)

   Given a point set P in the plane, we seek a subset Q ⊆ P, whose convex hull gives a smaller and thus simpler representation of the convex hull of P. Specifically, let cost(Q,P) denote the Hausdorff distance between the convex hulls CH(Q) and CH(P). Then given a value ε > 0 we seek the smallest subset Q ⊆ P such that cost(Q,P) ≤ ε. We also consider the dual version, where given an integer k, we seek the subset Q ⊆ P which minimizes cost(Q,P), such that |Q| ≤ k. For these problems, when P is in convex position, we respectively give an O(n log²n) time algorithm and an O(n log³n) time algorithm, where the latter running time holds with high probability. When there is no restriction on P, we show the problem can be reduced to APSP in an unweighted directed graph, yielding an O(n^2.5302) time algorithm when minimizing k and an O(min{n^2.5302, kn^2.376}) time algorithm when minimizing ε, using prior results for APSP. Finally, we show our near linear algorithms for convex position give 2-approximations for the general case. 

   more » « less