30th Conference on Computational Complexity (CCC 2015)

DOI10.4230/LIPIcs.CCC.2015.124zbMath1388.68063OpenAlexW3136468253MaRDI QIDQ4601826

Igor C. Oliveira, Rahul Santhanam

Publication date: 24 January 2018

Full work available at URL: https://www.research.ed.ac.uk/portal/en/publications/majority-is-incompressible-by-ac0p-circuits(1e859594-56a3-49a1-ad14-264b76cec50e).html

zbMATH Keywords

compressioncircuit lower boundinteractive communication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (4)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ On polynomial approximations to AC ⋮ Depth Reduction for Composites ⋮ Unnamed Item

This page was built for publication: 30th Conference on Computational Complexity (CCC 2015)