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

random functionsBoolean functionsnoisy Boolean decision trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the distribution function of the complexity of finite sequences
• Publication:3822914
• 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
• Publication:4542540
• Publication:5874332
• On the complexity of functions for random access machines

Cited in

(7)

• On randomized complexity of functions approximating the majority function
• Some notes on Rissanen's stochastic complexity
• Algorithmically Random Functions and Effective Capacities
• A nonapproximability result for finite function generation
• The randomized complexity of initial value problems
• Random problems
• The complexity of distributions

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)