Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

DOI10.1007/978-3-662-47672-7_22zbMath1402.68083arXiv1311.1616OpenAlexW1776408431MaRDI QIDQ3448791

Justin Thaler, Mark Bun

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Related Items (13)

Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ Unnamed Item ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities

Cites Work

• Reliable agnostic learning
• On the computational power of Boolean decision lists
• On the computational power of depth-2 circuits with threshold and modulo gates
• On the degree of Boolean functions as real polynomials
• Perceptrons, PP, and the polynomial hierarchy
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• The Pattern Matrix Method
• Quantum lower bounds for the collision and the element distinctness problems
• Agnostically Learning Halfspaces
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• The Intersection of Two Halfspaces Has High Threshold Degree
• Breaking the minsky-papert barrier for constant-depth circuits
• The multiparty communication complexity of set disjointness
• Quantum lower bounds by polynomials
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• New degree bounds for polynomial threshold functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hardness Amplification and the Approximate Degree of Constant-Depth Circuits