On the average-case complexity of underdetermined functions

DOI10.1515/DMA-2018-0019MaRDI QIDQ1669577zbMATH OpenOpenAlexFDO

Authors Aleksandr V. Chashkin

Publication date 3 September 2018

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma-2018-0019

zbMATH Keywords

Boolean functionBoolean circuitaverage-case complexitystraight-line programunderdetermined function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Recommendations

• Average-case complexity of elementary Boolean functions
• Stochastic Algorithms: Foundations and Applications
• Average case complexity for finite Boolean functions
• Complexity of realization of underdetermined Boolean functions
• Bounds for the average-case complexity of monotone Boolean functions

Cites work

• scientific article; zbMATH DE number 3646782 (Why is no real title available?)
• scientific article; zbMATH DE number 1037955 (Why is no real title available?)
• scientific article; zbMATH DE number 3225719 (Why is no real title available?)
• scientific article; zbMATH DE number 3311395 (Why is no real title available?)
• scientific article; zbMATH DE number 3390666 (Why is no real title available?)
• scientific article; zbMATH DE number 3405843 (Why is no real title available?)
• Average time of computing Boolean operators
• On the complexity of Boolean matrices, graphs, and the Boolean functions corresponding to them
• On the complexity of realization of partial Boolean functions by circuits of functional elements

Cited in

(7)

• Average-case complexity of elementary Boolean functions
• Average-case bit-complexity theory of real functions
• Stochastic Algorithms: Foundations and Applications
• Average case complexity for finite Boolean functions
• On the average-case complexity of Boolean functions under binomial distribution on their domains
• scientific article; zbMATH DE number 1180007 (Why is no real title available?)
• Complexity of realization of underdetermined Boolean functions

This page was built for publication: On the average-case complexity of underdetermined functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1669577)