Skip to main content
SpringerLink
Log in
Book cover

Entropy, Search, Complexity

  • Book
  • © 2007

Overview

Editors:
  1. Imre Csiszár

    1. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Gyula O. H. Katona

    1. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Gábor Tardos

    1. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Gábor Wiener

    1. Budapest University of Technology and Economics, Budapest, Hungary

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Bolyai Society Mathematical Studies (BSMS, volume 16)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (10 chapters)

  1. Front Matter

    Pages 1-8
    Download chapter PDF

  2. Two Colors and More

    • Martin Aigner
    Pages 9-26

  3. Coding with Feedback and Searching with Lies

    • Christian Deppe
    Pages 27-70

  4. Nonadaptive and Trivial Two-Stage Group Testing with Error-Correcting d e-Disjunct Inclusion Matrices

    • Arkadii G. D’Yachkov, Anthony J. Macula, Pavel A. Vilenkin
    Pages 71-83

  5. Model Identification Using Search Linear Models and Search Designs

    • S. Ghosh, T. Shirakura, J. N. Srivastava
    Pages 85-112

  6. Information Topologies with Applications

    • Peter Harremoës
    Pages 113-150

  7. Reinforced Random Walk

    • Michael Keane
    Pages 151-158

  8. Quantum Source Coding and Data Compression

    • Dénes Petz
    Pages 159-178

  9. Information Theory at the Service of Science

    • Flemming Topsøe
    Pages 179-207

  10. Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)

    • Paul Vitányi
    Pages 209-232

  11. Recognition Problems in Combinatorial Search

    • Gábor Wiener
    Pages 233-264
Back to top

Keywords

About this book

The present volume is a collection of survey papers in the ?elds given in the title. They summarize the latest developments in their respective areas. More than half of the papers belong to search theory which lies on the borderline of mathematics and computer science, information theory and combinatorics, respectively. The volume is slightly related to the twin conferences “Search And Communication Complexity” and “Information Theory In Mathematics” held at Balatonlelle, Hungary in 2000. These conferences led us to believe that there is a need for such a collection of papers. The paper written by Martin Aigner starts with the following relatively new search problem. Given n boolean variables as input one has to ?nd one of them whose value is in majority. The goal is to minimize the number of tests needed for this where one test is to compare two input variables for equality. The paper surveys the large set of problems and results which grew out of this one. In the traditional search model an unknown element is sought in a ?nite set, based on the information that the unknown element is or is not in some (asked) subsets. A variant is when a 0,1 function is given on the underlying set, and only the values of this function at the unknown element x is sought rather than x itself. This is called the recognition problem.

Editors and Affiliations

  • Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary

    Imre Csiszár, Gyula O. H. Katona, Gábor Tardos

  • Budapest University of Technology and Economics, Budapest, Hungary

    Gábor Wiener

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation