↓ 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 Sporadic Solutions to Zero-One Exclusion Tasks
  3. Altmetric Badge
    Chapter 2 Verifying and Synthesizing Software with Recursive Functions
  4. Altmetric Badge
    Chapter 3 Weak Parity
  5. Altmetric Badge
    Chapter 4 Consequences of Faster Alignment of Sequences
  6. Altmetric Badge
    Chapter 5 Distance Labels with Optimal Local Stretch
  7. Altmetric Badge
    Chapter 6 Time-Expanded Packings
  8. Altmetric Badge
    Chapter 7 Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
  9. Altmetric Badge
    Chapter 8 The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average
  10. Altmetric Badge
    Chapter 9 Tighter Relations between Sensitivity and Other Complexity Measures
  11. Altmetric Badge
    Chapter 10 On Hardness of Jumbled Indexing
  12. Altmetric Badge
    Chapter 11 Morphing Planar Graph Drawings Optimally
  13. Altmetric Badge
    Chapter 12 Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
  14. Altmetric Badge
    Chapter 13 On the Role of Shared Randomness in Simultaneous Communication
  15. Altmetric Badge
    Chapter 14 Short PCPs with Projection Queries
  16. Altmetric Badge
    Chapter 15 Star Partitions of Perfect Graphs
  17. Altmetric Badge
    Chapter 16 Coordination Mechanisms for Selfish Routing over Time on a Tree
  18. Altmetric Badge
    Chapter 17 On Area-Optimal Planar Graph Drawings
  19. Altmetric Badge
    Chapter 18 Shortest Two Disjoint Paths in Polynomial Time
  20. Altmetric Badge
    Chapter 19 Listing Triangles
  21. Altmetric Badge
    Chapter 20 On DNF Approximators for Monotone Boolean Functions
  22. Altmetric Badge
    Chapter 21 Internal DLA: Efficient Simulation of a Physical Growth Model
  23. Altmetric Badge
    Chapter 22 Lower Bounds for Approximate LDCs
  24. Altmetric Badge
    Chapter 23 Holographic Algorithms Beyond Matchgates
  25. Altmetric Badge
    Chapter 24 Testing Probability Distributions Underlying Aggregated Data
  26. Altmetric Badge
    Chapter 25 Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
  27. Altmetric Badge
    Chapter 26 The Bose-Hubbard model is QMA-complete
  28. Altmetric Badge
    Chapter 27 Characterization of Binary Constraint System Games
  29. Altmetric Badge
    Chapter 28 Fast Algorithms for Constructing Maximum Entropy Summary Trees
  30. Altmetric Badge
    Chapter 29 Thorp Shuffling, Butterflies, and Non-Markovian Couplings
  31. Altmetric Badge
    Chapter 30 Dynamic Complexity of Directed Reachability and Other Problems
  32. Altmetric Badge
    Chapter 31 One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
  33. Altmetric Badge
    Chapter 32 Canadians Should Travel Randomly
  34. Altmetric Badge
    Chapter 33 Efficiency Guarantees in Auctions with Budgets
  35. Altmetric Badge
    Chapter 34 Parameterized Complexity of Bandwidth on Trees
  36. Altmetric Badge
    Chapter 35 Testing Equivalence of Polynomials under Shifts
  37. Altmetric Badge
    Chapter 36 Optimal Analysis of Best Fit Bin Packing
  38. Altmetric Badge
    Chapter 37 Light Spanners
  39. Altmetric Badge
    Chapter 38 Semi-Streaming Set Cover
  40. Altmetric Badge
    Chapter 39 Online Stochastic Reordering Buffer Scheduling
  41. Altmetric Badge
    Chapter 40 Demand Queries with Preprocessing
  42. Altmetric Badge
    Chapter 41 Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
  43. Altmetric Badge
    Chapter 42 Public vs Private Coin in Bounded-Round Information
  44. Altmetric Badge
    Chapter 43 En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
  45. Altmetric Badge
    Chapter 44 Improved Submatrix Maximum Queries in Monge Matrices
  46. Altmetric Badge
    Chapter 45 For-All Sparse Recovery in Near-Optimal Time
  47. Altmetric Badge
    Chapter 46 Families with Infants: A General Approach to Solve Hard Partition Problems
  48. Altmetric Badge
    Chapter 47 Changing Bases: Multistage Optimization for Matroids and Matchings
  49. Altmetric Badge
    Chapter 48 Automata, Languages, and Programming
  50. Altmetric Badge
    Chapter 49 Nearly Linear-Time Model-Based Compressive Sensing
  51. Altmetric Badge
    Chapter 50 Breaking the PPSZ Barrier for Unique 3-SAT
  52. Altmetric Badge
    Chapter 51 Privately Solving Linear Programs
  53. Altmetric Badge
    Chapter 52 How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions
  54. Altmetric Badge
    Chapter 53 Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not
  55. Altmetric Badge
    Chapter 54 Partial Garbling Schemes and Their Applications
  56. Altmetric Badge
    Chapter 55 On the Complexity of Trial and Error for Constraint Satisfaction Problems
  57. Altmetric Badge
    Chapter 56 Information Theoretical Cryptogenography
  58. Altmetric Badge
    Chapter 57 The Complexity of Somewhat Approximation Resistant Predicates
  59. Altmetric Badge
    Chapter 58 Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound
  60. Altmetric Badge
    Chapter 59 Distance Oracles for Time-Dependent Networks
  61. Altmetric Badge
    Chapter 60 Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
  62. Altmetric Badge
    Chapter 61 Coloring Relatives of Interval Overlap Graphs via On-line Games
  63. Altmetric Badge
    Chapter 62 Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
  64. Altmetric Badge
    Chapter 63 Testing Forest-Isomorphism in the Adjacency List Model
  65. Altmetric Badge
    Chapter 64 Parameterized Approximation Schemes Using Graph Widths
  66. Altmetric Badge
    Chapter 65 FPTAS for Weighted Fibonacci Gates and Its Applications
  67. Altmetric Badge
    Chapter 66 Parameterized Algorithms to Preserve Connectivity
  68. Altmetric Badge
    Chapter 67 Nonuniform Graph Partitioning with Unrelated Weights
  69. Altmetric Badge
    Chapter 68 Automata, Languages, and Programming
  70. Altmetric Badge
    Chapter 69 Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability
  71. Altmetric Badge
    Chapter 70 QCSP on Semicomplete Digraphs
  72. Altmetric Badge
    Chapter 71 Fast Pseudorandomness for Independence and Load Balancing
  73. Altmetric Badge
    Chapter 72 Determining Majority in Networks with Local Interactions and Very Small Local Memory
  74. Altmetric Badge
    Chapter 73 Lower Bounds for Oblivious Subspace Embeddings
  75. Altmetric Badge
    Chapter 74 On Input Indistinguishable Proof Systems
  76. Altmetric Badge
    Chapter 75 Secure Computation Using Leaky Tokens
  77. Altmetric Badge
    Chapter 76 An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
  78. Altmetric Badge
    Chapter 77 A Faster Parameterized Algorithm for Treedepth
  79. Altmetric Badge
    Chapter 78 Pseudorandom Graphs in Data Structures
  80. Altmetric Badge
    Chapter 79 Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications
  81. Altmetric Badge
    Chapter 80 The Mondshein Sequence
  82. Altmetric Badge
    Chapter 81 Balanced Allocations: A Simple Proof for the Heavily Loaded Case
  83. Altmetric Badge
    Chapter 82 Close to Uniform Prime Number Generation With Fewer Random Bits
  84. Altmetric Badge
    Chapter 83 Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs
  85. Altmetric Badge
    Chapter 84 Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem
  86. Altmetric Badge
    Chapter 85 On Learning, Lower Bounds and (un)Keeping Promises
  87. Altmetric Badge
    Chapter 86 Certificates in Data Structures
  88. Altmetric Badge
    Chapter 87 Optimal Query Complexity for Estimating the Trace of a Matrix
  89. Altmetric Badge
    Chapter 88 Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles
  90. Altmetric Badge
    Chapter 89 Spatial Mixing of Coloring Random Graphs
Attention for Chapter 78: Pseudorandom Graphs in Data Structures
Altmetric Badge

Citations

dimensions_citation
4 Dimensions

Readers on

mendeley
15 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
Pseudorandom Graphs in Data Structures
Chapter number 78
Book title
Automata, Languages, and Programming
Published by
Springer, Berlin, Heidelberg, July 2014
DOI 10.1007/978-3-662-43948-7_78
Book ISBNs
978-3-66-243947-0, 978-3-66-243948-7
Authors

Omer Reingold, Ron D. Rothblum, Udi Wieder, Reingold, Omer, Rothblum, Ron D., Wieder, Udi

Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
Unknown 15 100%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 5 33%
Student > Master 3 20%
Researcher 2 13%
Professor 1 7%
Lecturer 1 7%
Other 1 7%
Unknown 2 13%
Readers by discipline Count As %
Computer Science 12 80%
Physics and Astronomy 1 7%
Unknown 2 13%