More Like this

1. A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits

   https://doi.org/10.1145/3543685  

   Volk, Ben Lee; Kumar, Mrinal (June 2022, ACM Transactions on Computation Theory)

   We show that there is an equation of degree at most poly( n ) for the (Zariski closure of the) set of the non-rigid matrices: That is, we show that for every large enough field 𝔽, there is a non-zero n 2 -variate polynomial P ε 𝔽[ x 1, 1 , ..., x n, n ] of degree at most poly( n ) such that every matrix M that can be written as a sum of a matrix of rank at most n /100 and a matrix of sparsity at most n 2 /100 satisfies P(M) = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer, and Landsberg [ 9 ] and improves the best upper bound known for this problem down from exp ( n 2 ) [ 9 , 12 ] to poly( n ). We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices M such that the linear transformation represented by M can be computed by an algebraic circuit with at most n 2 /200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [ 21 ] to construct low-degree “universal” maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low-degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [ 11 ]. 

   more » « less
2. CHARACTERIZING THE CONTINUOUS DEGREES

   Andrews, Uri; Igusa, Gregory; Miller, Joseph S.; Soskova, Mariya I. (January 2019, Israel journal of mathematics)

   The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property almost totality. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees, we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees, this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees. In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. We prove that the enumeration degree of A is continuous if and only if A is codable, meaning that A is enumeration above the complement of an infinite tree, every path of which enumerates A. 

   more » « less
3. Pure Pairs. V. Excluding Some Long Subdivision

   https://doi.org/10.1007/s00493-023-00025-8  

   Scott, Alex; Seymour, Paul; Spirkl, Sophie (June 2023, Combinatorica)

   A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph. 

   more » « less
4. Triforce and corners

   https://doi.org/10.1017/s0305004119000173  

   FOX, JACOB; SAH, ASHWIN; SAWHNEY, MEHTAAB; STONER, DAVID; ZHAO, YUFEI (July 2020, Mathematical Proceedings of the Cambridge Philosophical Society)

   Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $$G = {\mathbb{F}}_2^n$$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3. 

   more » « less
5. Thermochemistry and mechanisms of the Pt ⁺ + SO ₂ reaction from guided ion beam tandem mass spectrometry and theory

   https://doi.org/10.1063/5.0091510  

   Armentrout, P. B. (May 2022, The Journal of Chemical Physics)

   The kinetic energy dependences of the reactions of Pt + ( 2 D 5/2 ) with SO 2 were studied using a guided ion beam tandem mass spectrometer and theory. The observed cationic products are PtO + and PtSO + , with small amounts of PtS + , all formed in endothermic reactions. Modeling the kinetic energy dependent product cross sections allows determination of the product bond dissociation energies (BDEs): D 0 (Pt + –O) = 3.14 ± 0.11 eV, D 0 (Pt + –S) = 3.68 ± 0.31 eV, and D 0 (Pt + –SO) = 3.03 ± 0.12 eV. The oxide BDE agrees well with more precise literature values, whereas the latter two results are the first such measurements. Quantum mechanical calculations were performed for PtO + , PtS + , PtO 2 + , and PtSO + at the B3LYP and coupled-cluster with single, double, and perturbative triple [CCSD(T)] levels of theory using the def2-XZVPPD (X = T, Q) and aug-cc-pVXZ (X = T, Q, 5) basis sets and complete basis set extrapolations. These theoretical BDEs agree well with the experimental values. After including empirical spin–orbit corrections, the product ground states are determined as PtO + ( 4 Σ 3/2 ), PtS + ( 4 Σ 3/2 ), PtO 2 + ( 2 Σ g + ), and PtSO + ( 2 A′). Potential energy profiles including intermediates and transition states for each reaction were also calculated at the B3LYP/def2-TZVPPD level. Periodic trends in the thermochemistry of the group 9 metal chalcogenide cations are compared, and the formation of PtO + from the Pt + + SO 2 reaction is compared with those from the Pt + + O 2 , CO 2 , CO, and NO reactions. 

   more » « less