More Like this

1. An Obsession with Definitions

   https://doi.org/10.1007/978-3-030-25283-0_1  

   Rogaway, Phillip (July 2019, Progress in Cryptology – LATINCRYPT 2017)

   Lange, Tanja; Dunkelman, Orr (Ed.)

   Many people seem to think that cryptography is all about creating and analyzing cryptographic schemes. This view ignores the centrality of definitions in shaping the character of the field. More than schemes or their analysis, it is definitions that most occupy my thoughts. In this paper, written to accompany an invited talk at Latincrypt 2017, I try to explain my own fascination with definitions. I outline a few of the definitions I’ve recently worked on—garbling schemes, online AE, and onion encryption—and provide some general advice and comments about the definitional enterprise. 

   more » « less
2. Certification with an NP oracle

   Guy Blanc; Caleb Koch; Lange, Jane; Strassle, Carmen Tan (January 2023, Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023))

   In the certification problem, the algorithm is given a function f with certificate complexity k and an input x^⋆, and the goal is to find a certificate of size ≤ poly(k) for f’s value at x^⋆. This problem is in NP^NP, and assuming 𝖯 ≠ NP, is not in 𝖯. Prior works, dating back to Valiant in 1984, have therefore sought to design efficient algorithms by imposing assumptions on f such as monotonicity. Our first result is a BPP^NP algorithm for the general problem. The key ingredient is a new notion of the balanced influence of variables, a natural variant of influence that corrects for the bias of the function. Balanced influences can be accurately estimated via uniform generation, and classic BPP^NP algorithms are known for the latter task. We then consider certification with stricter instance-wise guarantees: for each x^⋆, find a certificate whose size scales with that of the smallest certificate for x^⋆. In sharp contrast with our first result, we show that this problem is NP^NP-hard even to approximate. We obtain an optimal inapproximability ratio, adding to a small handful of problems in the higher levels of the polynomial hierarchy for which optimal inapproximability is known. Our proof involves the novel use of bit-fixing dispersers for gap amplification. 

   more » « less
3. An optical lattice with sound

   https://doi.org/10.1038/s41586-021-03945-x  

   Guo, Yudan; Kroeze, Ronen M.; Marsh, Brendan P.; Gopalakrishnan, Sarang; Keeling, Jonathan; Lev, Benjamin L. (November 2021, Nature)
4. Cubic fourfolds with an involution

   https://doi.org/10.1090/tran/8811  

   Marquand, Lisa (December 2022, Transactions of the American Mathematical Society)

   There are three types of involutions on a cubic fourfold; two of anti-symplectic type, and one symplectic. Here we show that cubics with involutions exhibit the full range of behaviour in relation to rationality conjectures. Namely, we show a general cubic fourfold with a symplectic involution has no associated $K3$surface and is conjecturely irrational. In contrast, a cubic fourfold with a particular anti-symplectic involution has an associated $K3$, and is in fact rational. We show such a cubic is contained in the intersection of all non-empty Hassett divisors; we call such a cubic Hassett maximal. We study the algebraic and transcendental lattices for cubics with an involution both lattice theoretically and geometrically. 

   more » « less
5. Reflections on running an REU (with an eye towards equity)

   Krishna, Siddhi; Loving, Marissa (February 2022, Notices of the American Mathematical Society)