The computational complexity of linear optics [PDF]
Theory of Computing, 2010 We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers.
S. Aaronson, Alexei Y. Arkhipov
semanticscholar +1 more source
Holonomic equations and efficient random generation of binary trees [PDF]
Discrete Mathematics & Theoretical Computer ScienceHolonomic equations are recursive equations which allow computing efficiently numbers of combinatoric objects. Rémy showed that the holonomic equation associated with binary trees yields an efficient linear random generator of binary trees.
Pierre Lescanne
doaj +1 more source
Computational complexity and black hole horizons [PDF]
, 2014 Computational complexity is essential to understanding the properties of black hole horizons. The problem of Alice creating a firewall behind the horizon of Bob's black hole is a problem of computational complexity. In general we find that while creating
L. Susskind
semanticscholar +1 more source
Computational Complexity of Natural Morphology Revisited
Transactions of the Association for Computational LinguisticsThis paper revisits a classical, yet fundamental, discussion of theoretical computational linguistics: the computational complexity of natural languages.
Hajime Senuma, Akiko Aizawa
semanticscholar +1 more source
Computational complexity reduction techniques for quadrature Kalman filters
IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2015 Nonlinear filtering is a major problem in statistical signal processing applications and numerous techniques have been proposed in the literature. Since the seminal work that led to the Kalman filter to the more advanced particle filters, the goal has ...
P. Closas +2 more
semanticscholar +1 more source
Frontal cellular automata for modelling microstructure evolution: Computational complexity analysis
Computational materials science, 2023 D. Svyetlichnyy
semanticscholar +1 more source
Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation
Computational Complexity and Property Testing, 2020 Oded Goldreich, E. Bertino, A. Wigderson
semanticscholar +1 more source
High-order time stepping for the Navier-Stokes equations with minimal computational complexity [PDF]
Journal of Computational and Applied Mathematics, 2016 J. Guermond, P. Minev
semanticscholar +1 more source
On the Computational Complexity of Problems Related to Distinguishability Sets
Workshop on Descriptional Complexity of Formal Systems, 2015 M. Holzer, Sebastian Jakobi
semanticscholar +1 more source
Computational complexity and an integer programming model of Shakashaka
Canadian Conference on Computational Geometry, 2013 E. Demaine +3 more
semanticscholar +1 more source