More Like this

1. Point-hyperplane Incidence Geometry and the Log-rank Conjecture

   https://doi.org/10.1145/3543684  

   Singer, Noah ; Sudan, Madhu ( June 2022 , ACM Transactions on Computation Theory)

   We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in ℝ d that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., 2 –polylog( d ) ) fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the point-hyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank- d matrix containing at most O (1) distinct entries in each column contains a submatrix of fractional size 2 –polylog( d ) , in which each column is constant. We prove that our conjecture is equivalent to the log-rank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel k -partitions to bounds for parallel ( k -1)-partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e.,more »the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density Ω (ε 2 d / d ) in any d -dimensional configuration with incidence density ε, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upper-bound construction of Apfelbaum and Sharir [ 2 ], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is Ω (1/√ d ). Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density Ω (1) and complete bipartite subgraph density 2 -Ω (√ d ) , and pose several questions for this special case in the alternative language of extremal set combinatorics. Our framework and results may help shed light on the difficulty of improving Lovett’s Õ(√ rank( f )) bound [ 20 ] for the log-rank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel 3-partitioned configurations which beat our generic bounds for unstructured configurations.« less
2. Communication Complexity of Inner Product in Symmetric Normed Spaces

   Andoni, Alexandr ; Blasiok, Jaroslaw ; Filtser, Arnold ( January 2023 , Leibniz international proceedings in informatics)

   Tauman Kalai, Yael (Ed.)

   We introduce and study the communication complexity of computing the inner product of two vectors, where the input is restricted w.r.t. a norm N on the space ℝⁿ. Here, Alice and Bob hold two vectors v,u such that ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1, where N^* is the dual norm. The goal is to compute their inner product ⟨v,u⟩ up to an ε additive term. The problem is denoted by IP_N, and generalizes important previously studied problems, such as: (1) Computing the expectation 𝔼_{x∼𝒟}[f(x)] when Alice holds 𝒟 and Bob holds f is equivalent to IP_{𝓁₁}. (2) Computing v^TAv where Alice has a symmetric matrix with bounded operator norm (denoted S_∞) and Bob has a vector v where ‖v‖₂ = 1. This problem is complete for quantum communication complexity and is equivalent to IP_{S_∞}. We systematically study IP_N, showing the following results, near tight in most cases: 1) For any symmetric norm N, given ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1 there is a randomized protocol using 𝒪̃(ε^{-6} log n) bits of communication that returns a value in ⟨u,v⟩±ε with probability 2/3 - we will denote this by ℛ_{ε,1/3}(IP_N) ≤ 𝒪̃(ε^{-6} log n). In a special case where Nmore »= 𝓁_p and N^* = 𝓁_q for p^{-1} + q^{-1} = 1, we obtain an improved bound ℛ_{ε,1/3}(IP_{𝓁_p}) ≤ 𝒪(ε^{-2} log n), nearly matching the lower bound ℛ_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(min(n, ε^{-2})). 2) One way communication complexity ℛ^{→}_{ε,δ}(IP_{𝓁_p}) ≤ 𝒪(ε^{-max(2,p)}⋅ log n/ε), and a nearly matching lower bound ℛ^{→}_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(ε^{-max(2,p)}) for ε^{-max(2,p)} ≪ n. 3) One way communication complexity ℛ^{→}_{ε,δ}(N) for a symmetric norm N is governed by the distortion of the embedding 𝓁_∞^k into N. Specifically, while a small distortion embedding easily implies a lower bound Ω(k), we show that, conversely, non-existence of such an embedding implies protocol with communication k^𝒪(log log k) log² n. 4) For arbitrary origin symmetric convex polytope P, we show ℛ_{ε,1/3}(IP_{N}) ≤ 𝒪(ε^{-2} log xc(P)), where N is the unique norm for which P is a unit ball, and xc(P) is the extension complexity of P (i.e. the smallest number of inequalities describing some polytope P' s.t. P is projection of P').« less
3. Overconvergent modular forms are highest-weight vectors in the Hodge-Tate weight zero part of completed cohomology

   https://doi.org/10.1017/fms.2021.16  

   Howe, Sean ( January 2021 , Forum of Mathematics, Sigma)

   Abstract We construct a $(\mathfrak {gl}_2, B(\mathbb {Q}_p))$ and Hecke-equivariant cup product pairing between overconvergent modular forms and the local cohomology at $0$ of a sheaf on $\mathbb {P}^1$ , landing in the compactly supported completed $\mathbb {C}_p$ -cohomology of the modular curve. The local cohomology group is a highest-weight Verma module, and the cup product is non-trivial on a highest-weight vector for any overconvergent modular form of infinitesimal weight not equal to $1$ . For classical weight $k\geq 2$ , the Verma has an algebraic quotient $H^1(\mathbb {P}^1, \mathcal {O}(-k))$ , and on classical forms, the pairing factors through this quotient, giving a geometric description of ‘half’ of the locally algebraic vectors in completed cohomology; the other half is described by a pairing with the roles of $H^1$ and $H^0$ reversed between the modular curve and $\mathbb {P}^1$ . Under minor assumptions, we deduce a conjecture of Gouvea on the Hodge-Tate-Sen weights of Galois representations attached to overconvergent modular forms. Our main results are essentially a strict subset of those obtained independently by Lue Pan, but the perspective here is different, and the proofs are short and use simple tools: a Mayer-Vietoris cover, a cup product, and a boundarymore »map in group cohomology.« less
4. Quiver varieties and symmetric pairs

   https://doi.org/10.1090/ert/522  

   Li, Yiqiang ( January 2019 , Representation theory)

   We study fixed-point loci of Nakajima varieties under symplectomorphisms and their antisymplectic cousins, which are compositions of a diagram isomorphism, a reflection functor, and a transpose defined by certain bilinear forms. These subvarieties provide a natural home for geometric representation theory of symmetric pairs. In particular, the cohomology of a Steinberg-type variety of the symplectic fixed-point subvarieties is conjecturally related to the universal enveloping algebra of the subalgebra in a symmetric pair. The latter symplectic subvarieties are further used to geometrically construct an action of a twisted Yangian on a torus equivariant cohomology of Nakajima varieties. In the type A case, these subvarieties provide a quiver model for partial Springer resolutions of nilpotent Slodowy slices of classical groups and associated symmetric spaces, which leads to a rectangular symmetry and a refinement of Kraft-Procesi row/column removal reductions.
5. Entropic independence: optimal mixing of down-up random walks

   https://doi.org/10.1145/3519935.3520048  

   Anari, Nima ; Jain, Vishesh ; Koehler, Frederic ; Pham, Huy Tuan ; Vuong, Thuy-Duong ( June 2022 , Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)

   We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background distribution $\mu$ on $k$-sized subsets of a ground set of elements says that for any (possibly randomly chosen) set $S$, the relative entropy of a single element of $S$ drawn uniformly at random carries at most $O(1/k)$ fraction of the relative entropy of $S$. Entropic independence is the analog of the notion of spectral independence, if one replaces variance by entropy. We use entropic independence to derive tight mixing time bounds, overcoming the lossy nature of spectral analysis of Markov chains on exponential-sized state spaces. In our main technical result, we show a general way of deriving entropy contraction, a.k.a. modified log-Sobolev inequalities, for down-up random walks from spectral notions. We show that spectral independence of a distribution under arbitrary external fields automatically implies entropic independence. We furthermore extend our theory to the case where spectral independence does not hold under arbitrary external fields. To do this, we introduce a framework for obtaining tight mixing time bounds for Markov chains based on what we call restricted modified log-Sobolev inequalities, which guarantee entropy contraction not for allmore »distributions, but for those in a sufficiently large neighborhood of the stationary distribution. To derive our results, we relate entropic independence to properties of polynomials: $\mu$ is entropically independent exactly when a transformed version of the generating polynomial of $\mu$ is upper bounded by its linear tangent; this property is implied by concavity of the said transformation, which was shown by prior work to be locally equivalent to spectral independence. We apply our results to obtain (1) tight modified log-Sobolev inequalities and mixing times for multi-step down-up walks on fractionally log-concave distributions, (2) the tight mixing time of $O(n\log n)$ for Glauber dynamics on Ising models whose interaction matrix has eigenspectrum lying within an interval of length smaller than $1$, improving upon the prior quadratic dependence on $n$, and (3) nearly-linear time $\widetilde O_{\delta}(n)$ samplers for the hardcore and Ising models on $n$-node graphs that have $\delta$-relative gap to the tree-uniqueness threshold. In the last application, our bound on the running time does not depend on the maximum degree $\Delta$ of the graph, and is therefore optimal even for high-degree graphs, and in fact, is sublinear in the size of the graph for high-degree graphs.« less