Approximate Degree, Secret Sharing, and Concentration Phenomena

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.71OpenAlexW2956137306MaRDI QIDQ5875531

Justin Thaler, Andrej Bogdanov, Christopher Williamson, Nikhil S. Mande

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1906.00326

zbMATH Keywords

polynomial approximationsecret sharingpseudorandomnessapproximate degreedual polynomial

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Approximate Degree in Classical and Quantum Computing

Uses Software

• MathOverflow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the degree of Boolean functions as real polynomials
• Inclusion-exclusion: exact and approximate
• A characterization of the \(\mathbb Z^ n\) lattice
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities
• On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
• Faster private release of marginals on small databases
• Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
• Faster Algorithms via Approximation Theory
• The polynomial method strikes back: tight quantum query bounds via dual polynomials

This page was built for publication: Approximate Degree, Secret Sharing, and Concentration Phenomena