Oleg Borisovich Lupanov was a Soviet and Russian mathematician, born in Leningrad in 1932, regarded as a founder of the Soviet school of mathematical cybernetics. He is known for establishing an asymptotically optimal method of Boolean circuit synthesis, the Lupanov representation of Boolean functions, and for describing what became known as the Shannon effect in circuit complexity in 1970. He served as dean of the Faculty of Mechanics and Mathematics at Moscow State University from 1980 until his death in 2006, and received the Lenin Prize in 1966.
Facts
AwardMikhail Lomonosov Award 1 AwardOrder of the Red Banner of Labour 1 AwardOrder of Friendship of Peoples 1 AwardOrder of the Badge of Honour 1 FAQs
What is the Shannon effect that Oleg Lupanov is credited with proving?
Almost all Boolean functions need nearly as large a circuit as the hardest one. Shannon conjectured it and Lupanov proved it.
The Shannon effect is the observation that almost all Boolean functions have nearly the same circuit complexity as the hardest function, so most Boolean functions are almost as complicated as any can be. Claude Shannon conjectured it, and a 2025 conference talk on the effect credits Lupanov with proving it and later naming it.
Connections
In Field
Source Oleg Lupanov (Wikipedia)
In the Other Atlases
Nationality
Also in Geography Atlas: the nationality of this subject.
Sources
1. Wikidata: Oleg Lupanov
- Wikidata Q3710046, resolved via en.wikipedia pageprops (wave rule R-L)
- Wikidata Q3710046 P569 (date of birth)
View the SourceOleg Lupanov (Wikipedia)
In Field: Algorithms and Complexity Theory, Lead sectionQuote, In Field: Algorithms and Complexity Theory, Lead section
synthesis and complexity of Boolean circuits
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.