Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Conference Paper

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: 10/09/2016 - 10/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:
https://doi.org/10.1109/FOCS.2016.19

Supplemental Material:
Preprint (pdf)

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

Topics

Security and Privacy

cryptography

Technologies

circuits, complexity