Why is it so hard to prove P != NP, or even to prove
super-linear circuit lower bounds? While we often blame a lack of
combinatorial ingenuity, the bottleneck might be more fundamental:
the logical strength of our mathematical tools.
Hilbert, motivating his list of 23 problems, mentions the
arithmetical formulation of the concept of the continuum in the
works of Cauchy, Bolzano and Cantor, and the discovery of
non-Euclidean geometry by Gauss, Bolyai and Lobachevsky, as...
We present a general framework for derandomizing random linear
codes with respect to a broad class of properties, known as local
properties, which encompass several standard notions such as
minimum distance, list-decoding, list-recovery, and perfect...
Inflation may have occurred at energies up to 10^16 GeV, far
beyond any terrestrial collider. The "cosmological collider"
program aims to extract the mass spectrum and spin content of
particles present during inflation from non-Gaussian
correlators...
