Source coding by efficient selection of ground states clusters [PDF]
, 2004 In this letter, we show how the Survey Propagation algorithm can be generalized to include external forcing messages, and used to address selectively an exponential number of glassy ground states. These capabilities can be used to explore efficiently the
Battaglia, Demian +3 more
core +3 more sources
Pyramid-BERT: Reducing Complexity via Successive Core-set based Token Selection [PDF]
Annual Meeting of the Association for Computational Linguistics, 2022 Transformer-based language models such as BERT (CITATION) have achieved the state-of-the-art performance on various NLP tasks, but are computationally prohibitive.
Xin Huang +3 more
semanticscholar +1 more source
Leanness Computation: Small Values and Special Graph Classes [PDF]
Discrete Mathematics & Theoretical Computer ScienceLet u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k.
David Coudert +2 more
doaj +1 more source
Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains [PDF]
, 2013 In this paper we study the computational complexity of the (extended) minimum cost homomorphism problem (Min-Cost-Hom) as a function of a constraint language, i.e.
Uppman, Hannes
core +2 more sources
Quantifying Shannon's Work Function for Cryptanalytic Attacks [PDF]
, 2010 Attacks on cryptographic systems are limited by the available computational resources. A theoretical understanding of these resource limitations is needed to evaluate the security of cryptographic primitives and procedures.
van Son, R. J. J. H.
core +11 more sources
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
Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces [PDF]
Foundations of Computational Mathematics, 2021 We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks.
P. Grohs, F. Voigtlaender
semanticscholar +1 more source
Survey-propagation decimation through distributed local computations [PDF]
, 2005 We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm.
Achlioptas D Ricci-Tersenghi F +11 more
core +2 more sources
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
Quantum Zero-Error Algorithms Cannot be Composed [PDF]
, 2002 We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-error. This shows that quantum zero-error algorithms cannot be composed. In
Buhrman, Harry, de Wolf, Ronald
core +4 more sources