U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

This is an archive
(replace .gov by .rip)

Conference Proceedings

A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function

Published: October 11, 2016

Author(s)

Magnus Find (NIST), Alexander Golovnev (New York University), Edward Hirsch (Steklov Institute of Mathematics at St. Petersburg), Alexander Kulikov (Steklov Institute of Mathematics at St. Petersburg)

Conference

Name: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016)
Dates: October 9-11, 2016
Location: New Brunswick, New Jersey, United States
Citation: Proceedings. 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 89-98

Abstract

Keywords

affine disperser; Boolean circuits; lower bounds
Control Families

None selected

Documentation

Publication:
Conference Proceedings (DOI)

Supplemental Material:
Preprint (pdf)

Document History:
10/11/16: Conference Proceedings (Final)

Topics

Security and Privacy
cryptography

Technologies
circuits; complexity