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.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: SIGACT News Complexity Theory Column 117: Thirty Years of Complexity Theory (Columns)
It has been a tremendous treat being the SIGACT News Complexity Theory Column editor for these past thirty years. I thought about what to say here, and realized it is pretty simple: Thank you.  more » « less
Award ID(s):
2006496
PAR ID:
10422842
Author(s) / Creator(s):
Date Published:
Journal Name:
ACM SIGACT News
Volume:
54
Issue:
1
ISSN:
0163-5700
Page Range / eLocation ID:
82 to 89
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. (, ACM SIGACT News)
    null (Ed.)
    Warmest thanks to Rafael Pass and Muthu Venkitasubramaniam for this issue's guest column, "Average-Case Complexity Through the Lens of Interactive Puzzles." When I mentioned to them that my introduction would have a section on Alan Selman's passing, they immediately wrote back that they were very sorry to hear of Alan's passing, and mentioned (as you will see discussed in the second page of their article), "The main problem that we are addressing actually goes back to a paper of Even, Selman, and Yacobi from 1984: "The Complexity of Promise Problems with Applications to Public-Key Cryptography'." It is beautiful, and a tribute to the lasting influence of Alan's research, that in the 2020s his work from many decades earlier is helping shape the field's dialogue. 
    more » « less
  2. ; ; (, Fortschritte der Physik)
    Abstract Quantum circuit complexity has played a central role in recent advances in holography and many‐body physics. Within quantum field theory, it has typically been studied in a Lorentzian (real‐time) framework. In a departure from standard treatments, we aim to quantify the complexity of the Euclidean path integral. In this setting, there is no clear separation between space and time, and the notion of unitary evolution on a fixed Hilbert space no longer applies. As a proof of concept, we argue that the pants decomposition provides a natural notion of circuit complexity within the category of 2‐dimensional bordisms and use it to formulate the circuit complexity of states and operators in 2‐dimensional topological quantum field theory. We comment on analogies between our formalism and others in quantum mechanics, such as tensor networks and second quantization. 
    more » « less
  3. ; ; (, Asterisque)
    In this paper, we introduce a property of topological dynamical systems that we call finite dynamical complexity. For systems with this property, one can in principle compute the K-theory of the associated crossed product C*-algebra by splitting it up into simpler pieces and using the methods of controlled K-theory. The main part of the paper illustrates this idea by giving a new proof of the Baum-Connes conjecture for actions with finite dynamical complexity. We have tried to keep the paper as self-contained as possible: we hope the main part will be accessible to someone with the equivalent of a first course in operator K-theory. In particular, we do not assume prior knowledge of controlled K-theory, and use a new and concrete model for the Baum-Connes conjecture with coefficients that requires no bivariant K-theory to set up. 
    more » « less
  4. ; ; (, Asterisque)
    In this paper, we introduce a property of topological dynamical systems that we call finite dynamical complexity. For systems with this property, one can in principle compute the K-theory of the associated crossed product C*-algebra by splitting it up into simpler pieces and using the methods of controlled K-theory. The main part of the paper illustrates this idea by giving a new proof of the Baum-Connes conjecture for actions with finite dynamical complexity. We have tried to keep the paper as self-contained as possible: we hope the main part will be accessible to someone with the equivalent of a first course in operator K-theory. In particular, we do not assume prior knowledge of controlled K-theory, and use a new and concrete model for the Baum-Connes conjecture with coefficients that requires no bivariant K-theory to set up. 
    more » « less
  5. (, Foundations and Trends® in Theoretical Computer Science)
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email