Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Lower Bound on Circuit Complexity of Vector Function in U 2

  • Conference paper
Computer Science – Theory and Applications (CSR 2012)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7353))

Included in the following conference series:

  • 512 Accesses

Abstract

In 1973, Lamagna and Savage proved the following result. If f j : {0,1}n → {0,1} for 1 ≤ j ≤ m depends on at least two variables and if for i ≠ j, f i  ≠ f j and \(f_i \neq \bar{f_j}\), then for any binary basis Ω,

$$C_{\Omega}(f_1, \ldots f_m) \geq \min\limits_j C_{\Omega}(f_j) + m -1,$$

where C Ω(f) is the minimal size of a circuit computing f in the basis Ω.

The main purpose of this paper is to give a better lower bound for the following case. Let f : {0,1}n → {0,1} and f i  = f ⊕ x i for 1 ≤ i ≤ n. Assume that f is not a constant after any three substitutions x i  = c i for different variables. Then

$$C_{U_2}(f_1, \ldots f_n) \geq \min\limits_{i \neq j, c_i, c_j } C_{U_2}(f\mid_{x_i = c_i, x_j = c_j})+2n-O(1),$$

where U 2 = B 2 ∖ { ⊕ , ≡ }. This implies a 7n lower bound on the circuit complexity over U 2 of f 1, …, f n if f has circuit complexity at least 5n.

The author is supported in part by RFBR (grant 11-01-12135) and Computer Science Club scholarship.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell System Technical Journal 28, 59–98 (1949)

    MathSciNet  Google Scholar 

  2. Blum, N.: A Boolean function requiring 3n network size. Theoretical Computer Science 28, 337–345 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  3. Demenkov, E., Kulikov, A.S.: An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 256–265. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  4. Iwama, K., Morizumi, H.: An Explicit Lower Bound of 5n − o(n) for Boolean Circuits. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 353–364. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  5. Lamagna, E., Savage, J.: On the logical complexity of symmetric switching functions in monotone and complete bases. Discrete Optimization, Technical report, Brown University, Rhode Island (1973)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. St. Petersburg State University, Russia

    Evgeny Demenkov

Authors
  1. Evgeny Demenkov
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Steklov Institute of Mathematics at St.Petersburg, 191023, St. Petersburg, Russia

    Edward A. Hirsch

  2. University of Turku, 20014, Turku, Finland

    Juhani Karhumäki  & Arto Lepistö  & 

  3. Lobachevky State University of Nizhni Novgorod, 603950, Niszhi Novgorod, Russia

    Michail Prilutskii

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Demenkov, E. (2012). A Lower Bound on Circuit Complexity of Vector Function in U 2 . In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds) Computer Science – Theory and Applications. CSR 2012. Lecture Notes in Computer Science, vol 7353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30642-6_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-30642-6_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-30641-9

  • Online ISBN: 978-3-642-30642-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation