More Like this

1. Pseudorandomness for Unordered Branching Programs through Local Monotonicity

   Chattopadhyay, Eshan; Hatami, Pooya; Reingold, Omer; Tal, Avishay (June 2018, Proceedings of the annual ACM Symposium on Theory of Computing)

   We present an explicit pseudorandom generator with seed length tildeO((log n)w+1) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length n^{1/2+o(1)}. A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width w read-once, oblivious branching program B : {0, 1}^n -> {0, 1}, any k in {1,2,...,n}, Sum_{S subseteq [n];|S|=k} |\hat{B}(S)| leq O(log n)^{wk}. This settles a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM'13). Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs. 

   more » « less
2. Dihedral twist liquid models from emergent Majorana fermions

   https://doi.org/10.22331/q-2023-03-30-967  

   Teo, Jeffrey C.; Hu, Yichen (March 2023, Quantum)

   We present a family of electron-based coupled-wire models of bosonic orbifold topological phases, referred to as twist liquids, in two spatial dimensions. All local fermion degrees of freedom are gapped and removed from the topological order by many-body interactions. Bosonic chiral spin liquids and anyonic superconductors are constructed on an array of interacting wires, each supports emergent massless Majorana fermions that are non-local (fractional) and constitute the S O ( N ) Kac-Moody Wess-Zumino-Witten algebra at level 1. We focus on the dihedral D k symmetry of S O ( 2 n ) 1 , and its promotion to a gauge symmetry by manipulating the locality of fermion pairs. Gauging the symmetry (sub)group generates the C / G twist liquids, where G = Z 2 for C = U ( 1 ) l , S U ( n ) 1 , and G = Z 2 , Z k , D k for C = S O ( 2 n ) 1 . We construct exactly solvable models for all of these topological states. We prove the presence of a bulk excitation energy gap and demonstrate the appearance of edge orbifold conformal field theories corresponding to the twist liquid topological orders. We analyze the statistical properties of the anyon excitations, including the non-Abelian metaplectic anyons and a new class of quasiparticles referred to as Ising-fluxons. We show an eight-fold periodic gauging pattern in S O ( 2 n ) 1 / G by identifying the non-chiral components of the twist liquids with discrete gauge theories. 

   more » « less
3. A Simple Algorithm for kNN Sampling in General Metrics

   Gardner, Kirk P.; Sheehy, Donald R. (January 2020, Proceedings of the 32nd Canadian Conference on Computational Geometry)

   Keil, Mark; Mondal, Debajyoti (Ed.)

   Finding the kth nearest neighbor to a query point is a ubiquitous operation in many types of metric computations, especially those in unsupervised machine learning. In many such cases, the distance to k sample points is used as an estimate of the local density of the sample. In this paper, we give an algorithm that takes a finite metric (P,d) and an integer k and produces a subset S ⊆ P with the property that for any q ∈ P, the distance to the second nearest point of S to q is a constant factor approximation to the distance to the kth nearest point of P to q. Thus, the sample S may be used in lieu of P. In addition to being much smaller than P, the distance queries on S only require finding the second nearest neighbor instead of the kth nearest neighbor. This is a significant improvement, especially because theoretical guarantees on kth nearest neighbor methods often require k to grow as a function of the input size n. 

   more » « less
4. Higher semiadditive Grothendieck-Witt theory and the 𝐾(1)-local sphere

   https://doi.org/10.1090/cams/17  

   Carmeli, Shachar; Yuan, Allen (March 2023, Communications of the American Mathematical Society)

   We develop a higher semiadditive version of Grothendieck-Witt theory. We then apply the theory in the case of a finite field to study the higher semiadditive structure of the $K\left(1\right)$-local sphere ${\mathbb{S}}_{K\left(1\right)}$at the prime $2$, in particular realizing the non- $2$-adic rational element $1+\mathrm{\epsilon <\#comment/>}\in <\#comment/>{\mathrm{\pi <\#comment/>}}_0{\mathbb{S}}_{K\left(1\right)}$as a “semiadditive cardinality.” As a further application, we compute and clarify certain power operations in ${\mathrm{\pi <\#comment/>}}_0{\mathbb{S}}_{K\left(1\right)}$. 

   more » « less
5. Detection of Near-infrared Water Ice at the Surface of the (Pre)Transitional Disk of AB Aur: Informing Icy Grain Abundance, Composition, and Size

   https://doi.org/10.3847/1538-3881/ac4d9b  

   Betti, S. K.; Follette, K.; Jorquera, S.; Duchêne, G.; Mazoyer, J.; Bonnefoy, M.; Chauvin, G.; Pérez, L. M.; Boccaletti, A.; Pinte, C.; et al (March 2022, The Astronomical Journal)

   Abstract We present near-infrared Large Binocular Telescope LMIRCam imagery of the disk around the Herbig Ae/Be star AB Aurigae. A comparison of the surface brightness at K s (2.16 μ m), H 2 O narrowband (3.08 μ m), and L ′ (3.7 μ m) allows us to probe the presence of icy grains in this (pre)transitional disk environment. By applying reference differential imaging point-spread function subtraction, we detect the disk at high signal-to-noise ratios in all three bands. We find strong morphological differences between the bands, including asymmetries consistent with the observed spiral arms within 100 au in L ′ . An apparent deficit of scattered light at 3.08 μ m relative to the bracketing wavelengths ( K s and L ′ ) is evocative of ice absorption at the disk surface layer. However, the Δ( K s − H 2 O) color is consistent with grains with little to no ice (0%–5% by mass). The Δ ( H 2 O − L ′ ) color, conversely, suggests grains with a much higher ice mass fraction (∼0.68), and the two colors cannot be reconciled under a single grain population model. Additionally, we find that the extremely red Δ ( K s − L ′ ) disk color cannot be reproduced under conventional scattered light modeling with any combination of grain parameters or reasonable local extinction values. We hypothesize that the scattering surfaces at the three wavelengths are not colocated, and that the optical depth effects in each wavelength result from probing the grain population at different disk surface depths. The morphological similarity between K s and H 2 O suggests that their scattering surfaces are near one another, lending credence to the Δ( K s − H 2 O) disk color constraint of <5% ice mass fraction for the outermost scattering disk layer. 

   more » « less