More Like this

1. On correlation bounds against polynomials Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

   https://doi.org/10.4230/LIPIcs.CCC.2023.3  

   Ivanov, Peter; Pavlovic, Liam; Viola, Emanuele (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ta-Shma, Amnon (Ed.)

   We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over 𝔽₂. Our main contributions include: 1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible. 2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results." 3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction. 4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric. 

   more » « less
2. Degrees of symmetric Grothendieck polynomials and Castelnuovo-Mumford regularity

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

   Rajchgot, Jenna; Ren, Yi; Robichaux, Colleen; Dizier, Avery St; Weigandt, Anna (April 2021, Proceedings of the American Mathematical Society)

   We give an explicit formula for the degree of the Grothendieck polynomial of a Grassmannian permutation and a closely related formula for the Castelnuovo-Mumford regularity of the Schubert determinantal ideal of a Grassmannian permutation. We then provide a counterexample to a conjecture of Kummini-Lakshmibai-Sastry-Seshadri on a formula for regularities of standard open patches of particular Grassmannian Schubert varieties and show that our work gives rise to an alternate explicit formula in these cases. We end with a new conjecture on the regularities of standard open patches ofarbitraryGrassmannian Schubert varieties. 

   more » « less
3. Counterexamples to the tilting and (p,r)-filtration conjectures

   https://doi.org/10.1515/crelle-2019-0036  

   Bendel, Christopher P.; Nakano, Daniel K.; Pillen, Cornelius; Sobaje, Paul (November 2019, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract In this paper the authors produce a projective indecomposable module for the Frobenius kernel of a simple algebraic group in characteristic p that is not the restriction of an indecomposable tilting module. This yields a counterexample to Donkin’s longstanding Tilting Module Conjecture. The authors also produce a Weyl module that does not admit a p -Weyl filtration. This answers an old question of Jantzen, and also provides a counterexample to the {(p,r)} -Filtration Conjecture. 

   more » « less
4. A counterexample to the HK-conjecture that is principal

   https://doi.org/10.1017/etds.2022.25  

   DEELEY, ROBIN J. (June 2023, Ergodic Theory and Dynamical Systems)

   Abstract Scarparo has constructed counterexamples to Matui’s HK-conjecture. These counterexamples and other known counterexamples are essentially principal but not principal. In the present paper, a counterexample to the HK-conjecture that is principal is given. Like Scarparo’s original counterexample, our counterexample is the transformation groupoid associated to a particular odometer. However, the relevant group is the fundamental group of a flat manifold (and hence is torsion-free) and the associated odometer action is free. The examples discussed here do satisfy the rational version of the HK-conjecture. 

   more » « less
5. Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique

   Bresler, Guy; Jiang, Tianze (July 2023, Proceedings of Thirty Sixth Conference on Learning Theory)

   Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or re- covery, appear to have different computational limits. A detection-recovery gap for PDS was sub- stantiated in the form of a precise conjecture given by Chen and Xu (2014) (based on the parameter values for which a convexified MLE succeeds), and then shown to hold for low-degree polynomial algorithms by Schramm and Wein (2022) and for MCMC algorithms for Ben Arous et al. (2020). In this paper we demonstrate that a slight variation of the Planted Clique Hypothesis with secret leakage (introduced in Brennan and Bresler (2020)), implies a detection-recovery gap for PDS. In the same vein, we also obtain a sharp lower bound for refutation, yielding a detection-refutation gap. Our methods build on the framework of Brennan and Bresler (2020) to construct average-case reductions mapping secret leakage Planted Clique to appropriate target problems. 

   more » « less