↓ Skip to main content

Automata, Languages and Programming

Overview of attention for book
Cover of 'Automata, Languages and Programming'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Additive Approximation for Edge-Deletion Problems (Abstract)
  3. Altmetric Badge
    Chapter 2 Testing Graph Isomorphism in Parallel by Playing a Game
  4. Altmetric Badge
    Chapter 3 The Spectral Gap of Random Graphs with Given Expected Degrees
  5. Altmetric Badge
    Chapter 4 Embedding Bounded Bandwidth Graphs into ℓ1
  6. Altmetric Badge
    Chapter 5 Automata, Languages and Programming
  7. Altmetric Badge
    Chapter 6 Fault-Tolerance Threshold for a Distance-Three Quantum Code
  8. Altmetric Badge
    Chapter 7 Lower Bounds on Matrix Rigidity Via a Quantum Argument
  9. Altmetric Badge
    Chapter 8 Self-testing of Quantum Circuits
  10. Altmetric Badge
    Chapter 9 Deterministic Extractors for Independent-Symbol Sources
  11. Altmetric Badge
    Chapter 10 Gap Amplification in PCPs Using Lazy Random Walks
  12. Altmetric Badge
    Chapter 11 Stopping Times, Metrics and Approximate Counting
  13. Altmetric Badge
    Chapter 12 Algebraic Characterization of the Finite Power Property
  14. Altmetric Badge
    Chapter 13 P-completeness of Cellular Automaton Rule 110
  15. Altmetric Badge
    Chapter 14 Small Sweeping 2NFAs Are Not Closed Under Complement
  16. Altmetric Badge
    Chapter 15 Expressive Power of Pebble Automata
  17. Altmetric Badge
    Chapter 16 Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
  18. Altmetric Badge
    Chapter 17 Better Algorithms for Minimizing Average Flow-Time on Related Machines
  19. Altmetric Badge
    Chapter 18 A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
  20. Altmetric Badge
    Chapter 19 Edge Disjoint Paths in Moderately Connected Graphs
  21. Altmetric Badge
    Chapter 20 A Robust APTAS for the Classical Bin Packing Problem
  22. Altmetric Badge
    Chapter 21 Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
  23. Altmetric Badge
    Chapter 22 Approximating the Orthogonal Knapsack Problem for Hypercubes
  24. Altmetric Badge
    Chapter 23 A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
  25. Altmetric Badge
    Chapter 24 Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
  26. Altmetric Badge
    Chapter 25 Weighted Bipartite Matching in Matrix Multiplication Time
  27. Altmetric Badge
    Chapter 26 Optimal Resilient Sorting and Searching in the Presence of Memory Faults
  28. Altmetric Badge
    Chapter 27 Reliable and Efficient Computational Geometry Via Controlled Perturbation
  29. Altmetric Badge
    Chapter 28 Tight Bounds for Selfish and Greedy Load Balancing
  30. Altmetric Badge
    Chapter 29 Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
  31. Altmetric Badge
    Chapter 30 Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
  32. Altmetric Badge
    Chapter 31 The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
  33. Altmetric Badge
    Chapter 32 Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
  34. Altmetric Badge
    Chapter 33 Optimal Lower Bounds for Rank and Select Indexes
  35. Altmetric Badge
    Chapter 34 Dynamic Interpolation Search Revisited
  36. Altmetric Badge
    Chapter 35 Dynamic Matrix Rank
  37. Altmetric Badge
    Chapter 36 Nearly Optimal Visibility Representations of Plane Graphs
  38. Altmetric Badge
    Chapter 37 Planar Crossing Numbers of Genus g Graphs
  39. Altmetric Badge
    Chapter 38 How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover
  40. Altmetric Badge
    Chapter 39 Tight Approximation Algorithm for Connectivity Augmentation Problems
  41. Altmetric Badge
    Chapter 40 On the Bipartite Unique Perfect Matching Problem
  42. Altmetric Badge
    Chapter 41 Comparing Reductions to NP-Complete Sets
  43. Altmetric Badge
    Chapter 42 Design Is as Easy as Optimization
  44. Altmetric Badge
    Chapter 43 On the Complexity of 2D Discrete Fixed Point Problem
  45. Altmetric Badge
    Chapter 44 Automata, Languages and Programming
  46. Altmetric Badge
    Chapter 45 The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
  47. Altmetric Badge
    Chapter 46 Network Games with Atomic Players
  48. Altmetric Badge
    Chapter 47 Finite-State Dimension and Real Arithmetic
  49. Altmetric Badge
    Chapter 48 Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
  50. Altmetric Badge
    Chapter 49 The Myriad Virtues of Wavelet Trees
  51. Altmetric Badge
    Chapter 50 Atomic Congestion Games Among Coalitions
  52. Altmetric Badge
    Chapter 51 Computing Equilibrium Prices in Exchange Economies with Tax Distortions
  53. Altmetric Badge
    Chapter 52 New Constructions of Mechanisms with Verification
  54. Altmetric Badge
    Chapter 53 On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
  55. Altmetric Badge
    Chapter 54 Dynamic Routing Schemes for General Graphs
  56. Altmetric Badge
    Chapter 55 Energy Complexity and Entropy of Threshold Circuits
  57. Altmetric Badge
    Chapter 56 New Algorithms for Regular Expression Matching
  58. Altmetric Badge
    Chapter 57 A Parameterized View on Matroid Optimization Problems
  59. Altmetric Badge
    Chapter 58 Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
  60. Altmetric Badge
    Chapter 59 Length-Bounded Cuts and Flows
  61. Altmetric Badge
    Chapter 60 An Adaptive Spectral Heuristic for Partitioning Random Graphs
  62. Altmetric Badge
    Chapter 61 Some Results on Matchgates and Holographic Algorithms
  63. Altmetric Badge
    Chapter 62 Weighted Popular Matchings
Attention for Chapter 10: Gap Amplification in PCPs Using Lazy Random Walks
Altmetric Badge

Mentioned by

twitter
1 X user

Citations

dimensions_citation
10 Dimensions

Readers on

mendeley
21 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
Gap Amplification in PCPs Using Lazy Random Walks
Chapter number 10
Book title
Automata, Languages and Programming
Published by
Springer, Berlin, Heidelberg, July 2006
DOI 10.1007/11786986_10
Book ISBNs
978-3-54-035904-3, 978-3-54-035905-0
Authors

Jaikumar Radhakrishnan

X Demographics

X Demographics

The data shown below were collected from the profile of 1 X user who shared this research output. Click here to find out more about how the information was compiled.
Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
Iran, Islamic Republic of 1 5%
Japan 1 5%
United States 1 5%
Unknown 18 86%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 7 33%
Student > Master 4 19%
Researcher 3 14%
Professor 2 10%
Professor > Associate Professor 2 10%
Other 1 5%
Unknown 2 10%
Readers by discipline Count As %
Computer Science 17 81%
Agricultural and Biological Sciences 1 5%
Physics and Astronomy 1 5%
Unknown 2 10%