Cover Image

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Gamarnik, David
Format:	Preprint
Published:	2025
Subjects:	Probability Statistical Mechanics Computational Complexity Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Queues with service resetting
by: Bonomo, Ofek Lauber, et al.
Published: (2023)

Target search optimization by threshold resetting
by: Biswas, Arup, et al.
Published: (2025)

Optimal threshold resetting in collective diffusive search
by: Biswas, Arup, et al.
Published: (2026)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
by: Gamarnik, David, et al.
Published: (2023)

Queues with resetting: a perspective
by: Roy, Reshmi, et al.
Published: (2024)

Empirical universality and non-universality of local dynamics in the Sherrington-Kirkpatrick model
by: Liu, Grace, et al.
Published: (2025)

Bootstrapping Nonequilibrium Stochastic Processes
by: Cho, Minjae
Published: (2025)

Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees
by: Boche, Holger, et al.
Published: (2025)

Coupling of radial multiple SLE with Gaussian free field, and the hydrodynamic limit
by: Katori, Makoto, et al.
Published: (2025)

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
by: Asadi, Ali, et al.
Published: (2025)

Optimal distributions for randomized unbiased estimators with an infinite horizon and an adaptive algorithm
by: Zheng, Chao, et al.
Published: (2023)

Stochastic thermodynamics of computation
by: Wolpert, David H.
Published: (2019)

Model order reduction for the TASEP Master equation
by: Pioch, Kilian, et al.
Published: (2024)

Non-asymptotic convergence bounds for modified tamed unadjusted Langevin algorithm in non-convex setting
by: Neufeld, Ariel, et al.
Published: (2022)

Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization
by: Yuan, Haomu, et al.
Published: (2026)

Learning complexity of gradient descent and conjugate gradient algorithms
by: Jiao, Xianqi, et al.
Published: (2024)

Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems
by: Kanai, Hiroshi, et al.
Published: (2024)

Large Deviations in Safety-Critical Systems with Probabilistic Initial Conditions
by: Gomez, Aitor R., et al.
Published: (2024)

Dynamic Pedestrian Traffic Assignment with Link Transmission Model for Bidirectional Sidewalk Networks
by: Lilasathapornkit, Tanapon, et al.
Published: (2024)

Effect of constraint relaxation on dynamic critical phenomena in minimum vertex cover problem
by: Dote, Aki, et al.
Published: (2024)

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
by: Ketkov, Sergey S., et al.
Published: (2024)

The stochastic block model has the overlap graph property for modularity
by: Bhamidi, Shankar, et al.
Published: (2026)

Sum-of-Squares & Gaussian Processes I: Certification
by: Sandhu, Juspreet Singh, et al.
Published: (2024)

Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
by: Dote, Aki, et al.
Published: (2023)

Filters reveal emergent structure in computational morphogenesis
by: Aliahmadi, Hazhir, et al.
Published: (2025)

Transforming Design Spaces Using Pareto-Laplace Filters
by: Aliahmadi, Hazhir, et al.
Published: (2024)

Statistical Mechanics of Dynamical System Identification
by: Klishin, Andrei A., et al.
Published: (2024)

Sharp Rates of MMD Empirical Estimation with Power Kernels
by: Colasanto, Francesco, et al.
Published: (2026)

Central limit theorems for vector-valued composite functionals with smoothing and applications
by: Chen, Huihui, et al.
Published: (2024)

Wasserstein Distributionally Robust Optimization with Heterogeneous Data Sources
by: Rychener, Yves, et al.
Published: (2024)

Optimal transport and Wasserstein distances for causal models
by: Cheridito, Patrick, et al.
Published: (2023)

Quantum advantage from measurement-induced entanglement in random shallow circuits
by: Watts, Adam Bene, et al.
Published: (2024)

A unified perspective on exponential tilt and bridge algorithms for rare trajectories of discrete Markov processes
by: Aguilar, Javier, et al.
Published: (2023)

Two-dimensional Parallel Tempering for Constrained Optimization
by: Delacour, Corentin, et al.
Published: (2025)

Convergence rate of random scan Coordinate Ascent Variational Inference under log-concavity
by: Lavenant, Hugo, et al.
Published: (2024)

Thermodynamic Algorithms for Quadratic Programming
by: Bartosik, Patryk-Lipka, et al.
Published: (2024)

On the numerical integration of the Fokker-Planck equation driven by a mechanical force and the Bismut-Elworthy-Li formula
by: Sanders, Julia, et al.
Published: (2024)

Minimal work protocols for inertial particles in non-harmonic traps
by: Sanders, Julia, et al.
Published: (2024)

Optimal Control of Underdamped Systems: An Analytic Approach
by: Sanders, Julia, et al.
Published: (2024)

Consensus-based Distributed Optimization for Multi-agent Systems over Multiplex Networks
by: Rodríguez-Camargo, C. D., et al.
Published: (2023)