↓ Skip to main content

Mathematical Foundations of Computer Science 2008

Overview of attention for book
Cover of 'Mathematical Foundations of Computer Science 2008'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 One Useful Logic That Defines Its Own Truth
  3. Altmetric Badge
    Chapter 2 On Synchronous and Asynchronous Interaction in Distributed Systems
  4. Altmetric Badge
    Chapter 3 A Robust Class of Regular Languages
  5. Altmetric Badge
    Chapter 4 Deterministic Models of Communication Faults
  6. Altmetric Badge
    Chapter 5 Algebraic Graph Algorithms
  7. Altmetric Badge
    Chapter 6 Question/Answer Games on Towers and Pyramids
  8. Altmetric Badge
    Chapter 7 The Maximum Independent Set Problem in Planar Graphs
  9. Altmetric Badge
    Chapter 8 When Ignorance Helps: Graphical Multicast Cost Sharing Games
  10. Altmetric Badge
    Chapter 9 Shortest Synchronizing Strings for Huffman Codes
  11. Altmetric Badge
    Chapter 10 Optimizing Conjunctive Queries over Trees Using Schema Information
  12. Altmetric Badge
    Chapter 11 Clustering with Partial Information
  13. Altmetric Badge
    Chapter 12 Reoptimization of the Metric Deadline TSP
  14. Altmetric Badge
    Chapter 13 On the Shortest Linear Straight-Line Program for Computing Linear Forms
  15. Altmetric Badge
    Chapter 14 Flip Algorithm for Segment Triangulations
  16. Altmetric Badge
    Chapter 15 Computing Sharp 2-Factors in Claw-Free Graphs
  17. Altmetric Badge
    Chapter 16 A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
  18. Altmetric Badge
    Chapter 17 Positional Strategies for Higher-Order Pushdown Parity Games
  19. Altmetric Badge
    Chapter 18 Arthur and Merlin as Oracles
  20. Altmetric Badge
    Chapter 19 A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
  21. Altmetric Badge
    Chapter 20 Regional Languages and Tiling: A Unifying Approach to Picture Grammars
  22. Altmetric Badge
    Chapter 21 On a Special Class of Primitive Words
  23. Altmetric Badge
    Chapter 22 Complexity of Data Tree Patterns over XML Documents
  24. Altmetric Badge
    Chapter 23 A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
  25. Altmetric Badge
    Chapter 24 Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
  26. Altmetric Badge
    Chapter 25 Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
  27. Altmetric Badge
    Chapter 26 Reversal-Bounded Counter Machines Revisited
  28. Altmetric Badge
    Chapter 27 Iterative Compression and Exact Algorithms
  29. Altmetric Badge
    Chapter 28 Complexity and Limiting Ratio of Boolean Functions over Implication
  30. Altmetric Badge
    Chapter 29 Succinctness of Regular Expressions with Interleaving, Intersection and Counting
  31. Altmetric Badge
    Chapter 30 Nilpotency and Limit Sets of Cellular Automata
  32. Altmetric Badge
    Chapter 31 A Note on k -Colorability of P 5 -Free Graphs
  33. Altmetric Badge
    Chapter 32 Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations
  34. Altmetric Badge
    Chapter 33 Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
  35. Altmetric Badge
    Chapter 34 Periodicity and Immortality in Reversible Computing
  36. Altmetric Badge
    Chapter 35 Step-Out Ring Signatures
  37. Altmetric Badge
    Chapter 36 The Height of Factorization Forests
  38. Altmetric Badge
    Chapter 37 Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
  39. Altmetric Badge
    Chapter 38 Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
  40. Altmetric Badge
    Chapter 39 From λ -Calculus to Universal Algebra and Back
  41. Altmetric Badge
    Chapter 40 A Complete Axiomatic System for a Process-Based Spatial Logic
  42. Altmetric Badge
    Chapter 41 Voronoi Games on Cycle Graphs
  43. Altmetric Badge
    Chapter 42 Colouring Random Empire Trees
  44. Altmetric Badge
    Chapter 43 A Random Oracle Does Not Help Extract the Mutual Information
  45. Altmetric Badge
    Chapter 44 Approximating Independent Set and Coloring in Random Uniform Hypergraphs
  46. Altmetric Badge
    Chapter 45 A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
  47. Altmetric Badge
    Chapter 46 Directed Percolation Arising in Stochastic Cellular Automata Analysis
  48. Altmetric Badge
    Chapter 47 Resolution Width and Cutting Plane Rank Are Incomparable
  49. Altmetric Badge
    Chapter 48 On the Decidability of Bounded Valuedness for Transducers
  50. Altmetric Badge
    Chapter 49 Monadic Second Order Logic on Graphs with Local Cardinality Constraints
  51. Altmetric Badge
    Chapter 50 Short Proofs of Strong Normalization
Attention for Chapter 43: A Random Oracle Does Not Help Extract the Mutual Information
Altmetric Badge

Citations

dimensions_citation
7 Dimensions

Readers on

mendeley
4 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Chapter title
A Random Oracle Does Not Help Extract the Mutual Information
Chapter number 43
Book title
Mathematical Foundations of Computer Science 2008
Published by
Springer, Berlin, Heidelberg, August 2008
DOI 10.1007/978-3-540-85238-4_43
Book ISBNs
978-3-54-085237-7, 978-3-54-085238-4
Authors

Andrei Muchnik, Andrei Romashchenko

Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 4 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Unknown 4 100%

Demographic breakdown

Readers by professional status Count As %
Professor 1 25%
Professor > Associate Professor 1 25%
Researcher 1 25%
Unknown 1 25%
Readers by discipline Count As %
Mathematics 1 25%
Computer Science 1 25%
Unknown 2 50%