On the complexity of finite random functions

DOI10.1016/0020-0190(92)90102-2MaRDI QIDQ1209362zbMATH OpenOpenAlexFDO

Authors Uriel Feige

Publication date 16 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90102-2

zbMATH Keywords

Boolean functionsnoisy Boolean decision treesrandom functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the distribution function of the complexity of finite sequences
• scientific article; zbMATH DE number 4096475
• On the complexity of computing a random Boolean function over the reals
• On randomized complexity of functions approximating the majority function
• Randomized complexity
• Compositions of random functions on a finite set
• On the Complexity of the First-order Random Theory
• scientific article; zbMATH DE number 1775407
• scientific article; zbMATH DE number 7650940
• On the complexity of functions for random access machines

Cited in

(8)

• Random problems
• The randomized complexity of initial value problems
• On randomized complexity of functions approximating the majority function
• A nonapproximability result for finite function generation
• The complexity of distributions
• Algorithmically Random Functions and Effective Capacities
• Average-Case Lower Bounds for Noisy Boolean Decision Trees
• Some notes on Rissanen's stochastic complexity

This page was built for publication: On the complexity of finite random functions

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