skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
Award ID(s):
2023495
PAR ID:
10440583
Author(s) / Creator(s):
Date Published:
Journal Name:
Annual Symposium on Foundations of Computer Science
ISSN:
0272-5428
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We identify the universal mechanism behind the thermalization of (1+1)d QFTs at high and low temperatures. Viewing these theories as CFTs perturbed by relevant or irrelevant deformations, we show that conformal perturbation theory in the thermal state breaks down at late times allowing for the emergence of hydrodynamics. This breakdown occurs universally due to the unsuppressed exchange of stress tensors near the lightcone. Furthermore, for theories with central chargec→∞ c we solve for the emergent hydrodynamic theory to all orders in the gradient expansion by arguing that all transport parameters appearing in two-point functions have universal expressions in terms of the scaling dimension\Delta Δ of the perturbation. The radius of convergence of the hydrodynamic dispersion relations provides an early time cutoff for hydrodynamics, which agrees with the time scale at which conformal perturbation theory breaks down. 
    more » « less
  2. Monotonicity testing of Boolean functions on the hypergrid, $$f:[n]^d \to \{0,1\}$$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $$n$$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $$\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$$. This complexity is independent of $$n$$, but has a suboptimal dependence on $$d$$. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $$\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$$ and $$\widetilde{O}(\varepsilon^{-2} n\sqrt{d})$$-query testers, respectively. These testers have an almost optimal dependence on $$d$$, but a suboptimal polynomial dependence on $$n$$. \smallskip In this paper, we describe a non-adaptive, one-sided monotonicity tester with query complexity $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$, \emph{independent} of $$n$$. Up to the $$d^{o(1)}$$-factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $$n$$ yields a non-adaptive, one-sided $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$-query monotonicity tester for Boolean functions $$f:\mathbb{R}^d \to \{0,1\}$$ associated with an arbitrary product measure. 
    more » « less
  3. We study the gauging of a global U(1) symmetry in a gapped system in(2+1)d. The gauging procedure has been well-understood for a finiteglobal symmetry group, which leads to a new gapped phase with emergentgauge structure and can be described algebraically using themathematical framework of modular tensor category (MTC). We develop acategorical description of U(1) gauging in a MTC, taking into accountthe dynamics of U(1) gauge field absent in the finite group case. Whenthe ungauged system has a non-zero Hall conductance, the gauged theoryremains gapped and we determine the complete set of anyon data for thegauged theory. On the other hand, when the Hall conductance vanishes, weargue that gauging has the same effect of condensing a special Abeliananyon nucleated by inserting 2\pi 2 π U(1) flux. We apply our procedure to theSU(2) _k k MTCs and derive the full MTC data for the \mathbb{Z}_k ℤ k parafermion MTCs. We also discuss a dual U(1) symmetry that emergesafter the original U(1) symmetry of an MTC is gauged. 
    more » « less