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 $2{\mathbf{n}}^2-{\text{log}}_2({\mathbf{n}})-1$ lower bound for the border rank of matrix multiplication
Award ID(s):
1405348
PAR ID:
10094859
Author(s) / Creator(s):
;
Date Published:
Journal Name:
International Mathematics Research Notices
Volume:
2018
Issue:
15
ISSN:
1073-7928
Page Range / eLocation ID:
4722 to 4733
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Abstract The hybrid design of the Pierre Auger Observatory allows for the measurement of the properties of extensive air showers initiated by ultra-high energy cosmic rays with unprecedented precision. By using an array of prototype underground muon detectors, we have performed the first direct measurement, by the Auger Collaboration, of the muon content of air showers between $$2\times 10^{17}$$ 2 × 10 17 and $$2\times 10^{18}$$ 2 × 10 18 eV. We have studied the energy evolution of the attenuation-corrected muon density, and compared it to predictions from air shower simulations. The observed densities are found to be larger than those predicted by models. We quantify this discrepancy by combining the measurements from the muon detector with those from the Auger fluorescence detector at $$10^{{17.5}}\, {\mathrm{eV}} $$ 10 17.5 eV and $$10^{{18}}\, {\mathrm{eV}} $$ 10 18 eV . We find that, for the models to explain the data, an increase in the muon density of $$38\%$$ 38 % $$\pm 4\% (12\%)$$ ± 4 % ( 12 % ) $$\pm {}^{21\%}_{18\%}$$ ± 18 % 21 % for EPOS-LHC , and of $$50\% (53\%)$$ 50 % ( 53 % ) $$\pm 4\% (13\%)$$ ± 4 % ( 13 % ) $$\pm {}^{23\%}_{20\%}$$ ± 20 % 23 % for QGSJetII-04 , is respectively needed. 
    more » « less
  2. Megow, Nicole; Smith, Adam (Ed.)
    A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) n-input Subset Sum problem that runs in time 2^{(1/2 - c)n} for some constant c > 0. In this paper we give a Subset Sum algorithm with worst-case running time O(2^{n/2} ⋅ n^{-γ}) for a constant γ > 0.5023 in standard word RAM or circuit RAM models. To the best of our knowledge, this is the first improvement on the classical "meet-in-the-middle" algorithm for worst-case Subset Sum, due to Horowitz and Sahni, which can be implemented in time O(2^{n/2}) in these memory models [Horowitz and Sahni, 1974]. Our algorithm combines a number of different techniques, including the "representation method" introduced by Howgrave-Graham and Joux [Howgrave-Graham and Joux, 2010] and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof [Austrin et al., 2016], and Nederlof and Węgrzycki [Jesper Nederlof and Karol Wegrzycki, 2021], and "bit-packing" techniques used in the work of Baran, Demaine, and Pǎtraşcu [Baran et al., 2005] on subquadratic algorithms for 3SUM. 
    more » « less