Bounds on Negations in Boolean Circuits and Formulas

negation limited formulas n.w
1 / 24
Embed
Share

Explore the limitations and bounds of negations in Boolean circuits and formulas, uncovering mysteries and extending monotone results. Discover how constraints on negations impact circuit and formula sizes in computational theory.

  • Negations
  • Bounds
  • Boolean Circuits
  • Formulas
  • Computational Theory
rayaanacharya
mas_cor Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Negation-Limited Formulas Siyao Guo Ilan Komargodski New York University Weizman Institute of Science

  2. Boolean Circuits and Formulas Circuit: directed acyclic graph. Gates labeled by ???, ?? and ??? operations. Fan-out 2. Formula: a circuit with fan fan- -out 1 out 1. output wire Size ? = # of gates. input wires ?1 ?2 ?1

  3. Monotone vs. Non Monotone Computation Monotone computation: no ??? gates. Monotone (? log ?)1/3[RH00] bound 2 (?/log(?))[GP14] Formula size lower bound General 5? [ILMR01] Circuit size lower 2 ?3 ?(1)[Tal14] The effect of negation gates on circuit size remains to a large extent a mystery , Stasys Jukna

  4. Bound the # of Negations Circuits [Markov 58,Fischer 75,BNT98]: size: ?, negations: ? size: 2? + ?(? log ?), negations: log ? + 1 Formulas [Nechiporuk 62,Morizumi 09]: size: ?, negations: ? ? 2 size: ? ?6.4, negations: # of negations above is tight. The size is not known to be tight. ? is the input size of the functions.

  5. Bound the # of Negations [Markov 58,Fischer 75] log ? 0 # of negations in a circuit [Nechiporuk 62,Morizumi 09] ? 2 0 # of negations in a formula ? is the input size of the functions.

  6. Bound the # of Negations [Markov 58,Fischer 75] ???? log ? 0 # of negations in a circuit [Nechiporuk 62,Morizumi 09] ???? ? 2 0 # of negations in a formula ? is the input size of the functions.

  7. Extending Monotone Results [AM05,Ros15] (size lower bounds), [BCOST15] (learning), [GMOR15] (crypto) [Markov 58,Fischer 75] ?? log ? 0 # of negations in a circuit [Nechiporuk 62,Morizumi 09] ???? ? 2 0 # of negations in a formula IDEA: Decompose the ?-negation circuit into ??monotone parts and What about negation-limited formulas? ? is the input size of the functions. apply the known results on them (in a smart way).

  8. What about Negation-Limited Formulas? [AM05,Ros15] (size lower bounds), [BCOST15] (learning), [GMOR15] (crypto) [Markov 58,Fischer 75] ?? log ? 0 # of negations in a circuit Trivial [Nechiporuk 62,Morizumi 09] ???? ? 2 0 # of negations in a formula ? is the input size of the functions.

  9. What about Negation-Limited Formulas? [AM05,Ros15] (size lower bounds), [BCOST15] (learning), [GMOR15] (crypto) [Markov 58,Fischer 75] ?? log ? 0 # of negations in a circuit This Work [Nechiporuk 62,Morizumi 09] ?? ? 2 0 # of negations in a formula IDEA: Decompose the ?-negation formula into ? monotone parts and apply the known results on them (in a ? is the input size of the functions. smart way).

  10. Our Decomposition Theorem Every formula ? of size ? and ? negations can be rewritten as a formula of size 2? of the form ? ? ?1? , ,??? , where ? = ?(?) ? is a read-once formula every ??is a monotone formula. ?(?) inputs ? Monotone Pushing NOTs to the top ? ?1 ?2 ??

  11. Application 1 Formulas to Circuits Circuit size: ? negations: ? Formula size: 2? negations: 2? Known Circuit size: ? negations: ? Formula size: ? negations: ? Trivial Is this the best we can do?

  12. Application 1 Formulas to Circuits Theorem 1: Formula, size: ?, negations: ?, depth: ? circuit, size: 2? + ? ? log ? , negations: log ? + ? 1 , depth ? + ? log ? . Result for negation-limited circuits non-trivial result for negation-limited formulas Circuit size: Formula size: ? negations: ? This Work 2? + ?(? log ?) negations: log ? + ?(1)

  13. Average-Case Lower Bound Extension Theorem [Ros15]: For any ?>0, there exists an explicit function f which is + o(1) hard for NC1 circuits with 1 2 ? log ? negation gates under uniform distribution. Corollary: For any ?>0, there exists an explicit function f which is + o(1) hard for polynomial size formulas with ? 12 ?negation gates under uniform distribution.

  14. Proof of Theorem 1 Theorem 1: Formula, size: ?, negations: ?, depth: ? circuit, size: 2? + ? ? log ? , negations: log ? + ? 1 , depth ? + ? log ? . Apply [BNT98] theorem Decomposition Theorem ? ? ? ?1 ?2 ?1 ?2 ?? ?? ? is a circuit with log ? + ?(1) negations ? is a View ? as a circuit with O(?) inputs formula with O(?) inputs

  15. Application 2 Shrinkage of Formulas Definition: ?|?is ? where each input is fixed w.p 1 ? to a uniformly random bit. What happens to ? ?|?; the size of ?|??? Applications to PRGs, lower bounds, Fourier results, #SAT algorithms, etc. Definition: is the largest constant s.t. formula F E?? ?|? = ? ? ? ? + 1 Trivial: 1

  16. Application 2 Shrinkage of Formulas = 2 - shrinkage exponent of formulas [Tal14]. Open: 0- shrinkage exponent of monotone formulas (conjecture =3.27). ?- shrinkage exponent of formulas with ? negations. ?3.27 0=? Conj. [PZ93] = 2 ?=? [Subb 61,...,Tal 14] ? 0 # of negations

  17. Application 2 Shrinkage of Formulas Definition: ?is the largest constant s.t. formula F that contains ? negations E?? ?|? = ? ? ? ? ? + 1 Theorem 2: Let ? be a formula with ? > 0 negations E?? ?|? = ? ? 0 ? ? + ? Corollary: If ? = 1 , then ?= 0

  18. Proof of Theorem 2 Theorem 2: Let ? be a formula with ? > 0 negations E? ??? ?|? = ? ? 0 ? ? + ? Restrict each ??with ? Decomposition Theorem ? ? ? ?1 ?2 ?1 ?2 ?? ?? Each ??is monotone ??shrinks at rate 0 There are ?(?) ?? s

  19. Proof of Decomposition Pushing NOTs to the top Statement: ???? ???? ? ? ??? ?? ??? ?2 ??? ?1 size: S <= 2s, T <= max{5t-2,1} size: s, negations: t Proof: Induction on t. - Base case: t=0. - Induction hypothesis: holds for < t (t>=1). ? ?

  20. Induction Step (NOT Root) Pushing NOTs to the top Statement: ???? ???? ? ? ??? ?? ??? ?2 ??? ?1 size: S <= 2s, T <= max{5t-2,1} size: s, negations: t Proof: Decompose F by IH ?? H ? ??? ??1 s <=s, t = t-1 size: S <= 2s, T = T <= max{5(t-1)-2,1}

  21. Induction Step (AND/OR Root) Pushing NOTs to the top Statement: ???? ???? ? ? ??? ?? ??? ?2 ??? ?1 size: S <= 2s, T <= max{5t-2,1} size: s, negations: t / Proof: Decompose F1, F2by IH / ?? H2 ?? H1 Require: t1,t2<t ?2 ?1 ?? 1 ?? ? ???1 ??1 s1+s2=s, t1+t2= t S1+S2<= 2s, T1+T2<= 5t-4

  22. Induction Step (Overall) Pushing NOTs to the top Statement: ???? ???? ? ? ??? ?? ??? ?2 ??? ?1 size: S <= 2s, T <= max{5t-2,1} size: s, negations: t F : t =t, each subformula of F has < t negations Proof: Decompose F (previous slides) F is monotone ? ? ?? H ?? H ? ? ? ??? ??1 ??? ??1 T <= 5t-4 1 0 s +s =s, t = t s + s + 2s <= 2s, T = T +2 <= 5t-2

  23. Summary Efficient decomposition theorem for negation-limited formulas Extending results to negation limited formulas from: Negation limited circuits (size lower bounds, learning, crypto, etc). Generic, exp. improvement. Monotone formulas (shrinkage) This Work [Nechiporuk 62,Morizumi 09] Thanks! # of negations ?? ? 2 0

  24. Circuits to Formulas ?-negation formula ?-negation circuit 12 ? 12 ? log ? Average-case lower bound for NC1 ? PRF (log ?) (?) ??(2? ?/?) Learning ??(? ?/?) b

Related


No related presentations.

More Related Content