More Like this

1. A ZPP ^NP[1] Lifting Theorem

   https://doi.org/10.1145/3428673  

   Watson, Thomas (December 2020, ACM Transactions on Computation Theory)

   null (Ed.)

   The complexity class ZPP NP[1] (corresponding to zero-error randomized algorithms with access to one NP oracle query) is known to have a number of curious properties. We further explore this class in the settings of time complexity, query complexity, and communication complexity. • For starters, we provide a new characterization: ZPP NP[1] equals the restriction of BPP NP[1] where the algorithm is only allowed to err when it forgoes the opportunity to make an NP oracle query. • Using the above characterization, we prove a query-to-communication lifting theorem , which translates any ZPP NP[1] decision tree lower bound for a function f into a ZPP NP[1] communication lower bound for a two-party version of f . • As an application, we use the above lifting theorem to prove that the ZPP NP[1] communication lower bound technique introduced by Göös, Pitassi, and Watson (ICALP 2016) is not tight. We also provide a “primal” characterization of this lower bound technique as a complexity class. 

   more » « less
2. From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory

   https://doi.org/10.3390/e20100782  

   Papadimitriou, Christos; Piliouras, Georgios (October 2018, Entropy)

   In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer’s (or, in another version Kakutani’s) fixed point theorem, the most sophisticated result in his era’s topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of “the outcome of the game”—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games. 

   more » « less
3. Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation

   Yashvanth Kondi and abhi shelat (December 2022, ASIACRYPT'2022)

   The goal of this paper is to improve the efficiency and applicability of straightline extraction techniques in the random oracle model. Straightline extraction in the random oracle model refers to the existence of an extractor, which given the random oracle queries made by a prover on some theorem, is able to produce a witness for with roughly the same probability that produces a verifying proof. This notion applies to both zero-knowledge protocols and verifiable computation where the goal is compressing a proof. Pass (CRYPTO '03) first showed how to achieve this property for NP using a cut-and-choose technique which incurred a -bit overhead in communication where is a security parameter. Fischlin (CRYPTO '05) presented a more efficient technique based on ``proofs of work'' that sheds this cost, but only applies to a limited class of Sigma Protocols with a ``quasi-unique response'' property, which for example, does not necessarily include the standard OR composition for Sigma protocols. With Schnorr/EdDSA signature aggregation as a motivating application, we develop new techniques to improve the computation cost of straight-line extractable proofs. Our improvements to the state of the art range from 70X--200X for the best compression parameters. This is due to a uniquely suited polynomial evaluation algorithm, and the insight that a proof-of-work that relies on multicollisions and the birthday paradox is faster to solve than inverting a fixed target. Our collision based proof-of-work more generally improves the Prover's random oracle query complexity when applied in the NIZK setting as well. In addition to reducing the query complexity of Fischlin's Prover, for a special class of Sigma protocols we can for the first time closely match a new lower bound we present. Finally we extend Fischlin's technique so that it applies to a more general class of strongly-sound Sigma protocols, which includes the OR composition. We achieve this by carefully randomizing Fischlin's technique---we show that its current deterministic nature prevents its application to certain multi-witness languages. 

   more » « less
4. Stratified Noncommutative Geometry

   https://doi.org/10.1090/memo/1485  

   Ayala, David; Mazel-Gee, Aaron; Rozenblyum, Nick (May 2024, Memoirs of the American Mathematical Society)

   We introduce a theory of stratifications of noncommutative stacks (i.e., presentable stable $\mathrm{\infty <\#comment/>}$-categories), and we prove a reconstruction theorem that expresses them in terms of their strata and gluing data. This reconstruction theorem is compatible with symmetric monoidal structures, and with more general operadic structures such as ${\mathbb{E}}_n$-monoidal structures. We also provide a suite of fundamental operations for constructing new stratifications from old ones: restriction, pullback, quotient, pushforward, and refinement. Moreover, we establish a dual form of reconstruction; this is closely related to Verdier duality and reflection functors, and gives a categorification of Möbius inversion. Our main application is to equivariant stable homotopy theory: for any compact Lie group $G$, we give a symmetric monoidal stratification of genuine $G$-spectra. In the case that $G$is finite, this expresses genuine $G$-spectra in terms of their geometric fixedpoints (as homotopy-equivariant spectra) and gluing data therebetween (which are given by proper Tate constructions). We also prove an adelic reconstruction theorem; this applies not just to ordinary schemes but in the more general context of tensor-triangular geometry, where we obtain a symmetric monoidal stratification over the Balmer spectrum. We discuss the particular example of chromatic homotopy theory. 

   more » « less
5. Quantum entropy and central limit theorem

   https://doi.org/10.1073/pnas.2304589120  

   Bu, Kaifeng; Gu, Weichen; Jaffe, Arthur (June 2023, Proceedings of the National Academy of Sciences)

   We introduce a framework to study discrete-variable (DV) quantum systems based on qudits. It relies on notions of a mean state (MS), a minimal stabilizer-projection state (MSPS), and a new convolution. Some interesting consequences are: The MS is the closest MSPS to a given state with respect to the relative entropy; the MS is extremal with respect to the von Neumann entropy, demonstrating a “maximal entropy principle in DV systems.” We obtain a series of inequalities for quantum entropies and for Fisher information based on convolution, giving a “second law of thermodynamics for quantum convolutions.” We show that the convolution of two stabilizer states is a stabilizer state. We establish a central limit theorem, based on iterating the convolution of a zero-mean quantum state, and show this converges to its MS. The rate of convergence is characterized by the “magic gap,” which we define in terms of the support of the characteristic function of the state. We elaborate on two examples: the DV beam splitter and the DV amplifier. 

   more » « less