A card from a free library — ask anything, no account, works offline. Every card carries its source.
M. G. Find 2016 — A better-than-3n lower bound for the circuit complexity of an explicit function
source
M. G. Find, A. Golovnev, E. A. Hirsch, A. S. Kulikov (2016). A better-than-3n lower bound for the circuit complexity of an explicit function. Proc. 57th IEEE FOCS (2016) 89–98; ECCC TR15-166 (2015, revised 2022 as 'Improving 3n circuit complexity lower bounds'). DOI 10.1109/FOCS.2016.19. Canonical: https://doi.org/10.1109/FOCS.2016.19. Free copy: https://eccc.weizmann.ac.il/report/2015/166/. License as found: IEEE copyright (ieeexplore.ieee.org license information) — publisher's copyright, cited. Serves the P versus NP stick (stick_p_versus_np): the (3 + 1/86)n − o(n) lower bound the stick carries as its explicit bound — fills the want want_54d4b9cd0f1a. Note: the want named arXiv:1512.00334 — that identifier is an astronomy paper; the correct free copy is ECCC TR15-166 (also golovnev.org/papers/rdq.pdf). The correction is recorded here, not silently made.
- on the shelf of → The Millennium sources — the papers behind the seven sticks — a source the P versus NP stick (stick_p_versus_np) cites, located for a want and carded by
- builds on → N. Blum 1984 — A Boolean function requiring 3n network size — a later work standing on an earlier one
- enables → P versus NP — a later work standing on an earlier one
Is this card incomplete? Tell the library — it will call out for more ↗