Recent Progress in Information-Based Complexity

TitleRecent Progress in Information-Based Complexity
Publication TypeTechnical Report
Year of Publication1993
AuthorsTraub, J. F., & Wozniakowski H.
Other Numbers840

This is an invited article for the Structural Complexity Column, edited by Juris Hartmanis, which will appear in the Bulletin EATCS in October 1993. The scope of the article is indicated in the following list of Sections:1. Overview of Information-Based Complexity2. Breaking Intractability3. Verification4. Combinatorial Complexity5. Similarities and Differences with Discrete Complexity6. Brief History7. Appendix8. References

Bibliographic Notes

ICSI Technical Report TR-93-052

Abbreviated Authors

J. F. Traub and H. Woznaikowski

ICSI Research Group


ICSI Publication Type

Technical Report