scientific article; zbMATH DE number 7559056

DOI10.4230/LIPIcs.ITCS.2019.13MaRDI QIDQ5090385

Abhishek Bhrushundi, Kaave Hosseini, Sankeerth Rao, Shachar Lovett

Publication date: 18 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

polynomialslower boundscircuit complexityACC

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

Cites Work

• Unnamed Item
• Unnamed Item
• The inverse conjecture for the Gowers norm over finite fields in low characteristic
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On the degree of Boolean functions as real polynomials
• Nonuniform ACC Circuit Lower Bounds
• PP is as Hard as the Polynomial-Time Hierarchy
• The Shrinkage Exponent of de Morgan Formulas is 2
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• Every locally characterized affine-invariant property is testable
• Natural proofs

This page was built for publication: