A $2{\mathbf{n}}^2-{\text{log}}_2({\mathbf{n}})-1$ lower bound for the border rank of matrix multiplication
Authors:
;
Award ID(s):
Publication Date:
NSF-PAR ID:
10094859
Journal Name:
International Mathematics Research Notices
Volume:
2018
Issue:
15
Page Range or eLocation-ID:
4722 to 4733
ISSN:
1073-7928
1. 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\%}$$more »
In this paper, we study the convex quadratic optimization problem with indicator variables. For the$${2\times 2}$$$2×2$case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the$${2\times 2}$$$2×2$case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including the optimal perspective relaxation and the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.