Monte Carlo to Las Vegas for Recursively Composed Functions

• URL: http://arxiv.org/abs/2601.08073v1
• Date: Mon, 12 Jan 2026 23:34:37 GMT
• Title: Monte Carlo to Las Vegas for Recursively Composed Functions
• Authors: Bandar Al-Dhalaan, Shalev Ben-David,
• Abstract summary: We study the composition limits of general measures in query complexity.<n>We show this limit converges under reasonable assumptions about the measure.<n>We then give a surprising result regarding the composition limit of randomized query complexity.
• Score: 0.26709266817192023
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.

Related papers

• Pseudo-deterministic Quantum Algorithms [7.46931129146594]
  We show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms.<n>On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead.
  arXiv  Detail & Related papers  (2026-02-19T18:54:47Z)
• A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation [0.0]
  We propose a quantum unstructured search algorithm to find the extrema or roots of discrete functions, $f(mathbfx)$.<n>The number of operations needed to map $f(mathbfx)$ to $u(z)$ determines the accuracy of the result and the circuit depth.
  arXiv  Detail & Related papers  (2025-05-20T17:31:44Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting.<n>Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
  arXiv  Detail & Related papers  (2025-02-13T12:04:39Z)
• On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
  This paper explores a fine-grained version of the Watrous conjecture. It includes the randomized and quantum algorithms with success probabilities arbitrarily close to $1/2$.
  arXiv  Detail & Related papers  (2023-09-20T13:04:45Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.<n>Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Quantum Approximate Counting with Nonadaptive Grover Iterations [1.14219428942199]
  In the quantum setting, Approximate Counting can be done with $Oleft(sqrtN/epsilon, sqrtN/K/epsilonright)$ queries. We show that algorithms using only nonadaptive Grover iterations can achieve $Oleft(sqrtN/epsilonright)$ query complexity, which is tight.
  arXiv  Detail & Related papers  (2020-10-09T04:48:14Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.