A new minimax theorem for randomized algorithms

DOI10.1145/3626514MaRDI QIDQ7032001zbMATH OpenFDO

Authors Shalev Ben-David, Eric Blais

Publication date 5 February 2025

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3626514

zbMATH Keywords

circuit complexitycommunication complexityminimaxpolynomial degreequantum computationquery complexityrandomized computation

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11) Randomized algorithms (68W20) Quantum computation (81P68)

Cites work

• Around the log-rank conjecture
• Boosting and hard-core set construction
• Classical lower bounds from quantum upper bounds
• Comparing the combinational complexities of arithmetic functions
• Constant Depth Reducibility
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 836627 (Why is no real title available?)
• Information, divergence and risk for binary experiments
• Interactive Information Complexity
• Log Depth Circuits for Division and Related Problems
• Making polynomials robust to noise
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• On general minimax theorems
• On Threshold Circuits and Polynomial Computation
• Optimal separation and strong direct sum for randomized query complexity
• Quantum approximate counting, simplified
• Randomized Boolean decision trees: Several remarks
• Robust polynomials and quantum algorithms
• Some inequalities for information divergence and related measures of discrimination
• Statistical distances and their role in robustness
• Strictly Proper Scoring Rules, Prediction, and Estimation
• Strong direct product theorems for quantum communication and query complexity
• The complexity of computations by networks
• The power of many samples in query complexity
• The uniform hardcore lemma via approximate Bregman projections
• Towards proving strong direct product theorems
• Über die Genauigkeit der Annäherung stetiger Funktionen durch ganze rationale Funktionen gegebenen Grades und trigonometrische Summen gegebener Ordnung.

This page was built for publication: A new minimax theorem for randomized algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7032001)