Madhu Sudan: Papers - Bibliographic Information

  1. Online algorithms for locating checkpoints.
  2. Self-testing/correcting for polynomials and for approximate functions.
  3. Connectivity properties of matroids.
  4. Self-testing polynomial functions efficiently and over rational domains.
  5. Highly resilient correctors for multivariate polynomials.
  6. Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems.
  7. Proof verification and the hardness of approximation problems.
  8. Reconstructing algebraic functions from mixed data.
  9. Efficient routing in optical networks.
  10. Improved non-approximability results.
  11. The minimum latency problem.
  12. Computing roots of graphs is hard.
  13. On syntactic versus computational views of approximability.
  14. Priority encoding transmission.
  15. Motion planning on a graph.
  16. Approximate graph coloring by semidefinite programming.
  17. On the role of algebra in the efficient verification of proofs.
  18. Some improvements to total degree tests.
  19. Guaranteeing fair service to persistent dependent tasks.
  20. Approximating minimum feedback sets and multicuts in directed graphs.
  21. A geometric approach to betweenness.
  22. Linearity testing over characteristic two.
  23. Free bits, PCP and non-approximability - towards tight results.
  24. Learning polynomials with queries: The highly noisy case.
  25. Private information retrieval.
  26. The optimization complexity of constraint satisfaction problems.
  27. Robust characterizations of polynomials with applications to program testing.
  28. Adversarial queueing theory.
  29. Gadgets, approximation, and linear programming.
  30. Decoding of Reed Solomon codes beyond the error-correction bound.
  31. A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction.
  32. Improved low degree testing and its applications.
  33. Constraint satisfaction: The approximability of minimization problems.
  34. Decoding Reed-Solomon codes beyond the error-correction diameter.
  35. A statistical perspective on data mining.
  36. Algorithmic issues in coding theory.
  37. Computational indistinguishability: A sample hierarchy.
  38. Probabilistic verification of proofs.
  39. Improved decoding of Reed-Solomon codes and algebraic-geometry codes.
  40. Probabilistically checkable proofs with low amortized query complexity.
  41. A tight characterization of NP with 3-query PCPs.
  42. Pseudorandom generators without the XOR Lemma.
  43. Chinese remaindering with errors.
  44. Linear consistency testing.
  45. Hardness of approximating the minimum distance of a linear code.
  46. List decoding: Algorithms and applications.
  47. Random walks with "Back Buttons".
  48. List decoding algorithms for certain concatenated codes.
  49. List decoding: Algorithms and applications.
  50. On representations of algebraic-geometric codes.
  51. Combinatorial bounds for list decoding.
  52. Hardness of approximate hypergraph coloring.
  53. "Soft-decision" decoding of Chinese remainder codes.
  54. Small PCPs with low query complexity.
  55. Extensions to the Johnson bound.
  56. The approximability of constraint satisfaction problems.
  57. Coding theory: Tutorial & Survey.
  58. Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms.
  59. Complexity classifications of Boolean constraint satisfaction problems.
  60. Guessing secrets efficiently via list-decoding.
  61. Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.
  62. Reflections on ``Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes''.
  63. Decoding concatenated codes using soft information.
  64. A fuzzy vault scheme.
  65. Locally testable codes and PCPs of almost-linear length.
  66. Reconstructing curves in three (and higher) dimensional spaces from noisy data.
  67. Derandomizing low degree tests via epsilon-biased spaces noisy data.
  68. Bounds on 2-query codeword testing.
  69. Quick and Dirty Refereeing?
  70. Robust PCPs of proximity, shorter PCPs, and applications to coding
  71. Robust locally testable codes and products of codes
  72. From logarithmic advice to single-bit advice.
  73. Probabilistically Checkable Proofs.
  74. Optimal error-correction for computationally bounded noise.
  75. Short PCPs with Polylog Query Complexity.
  76. Derandomization of auctions.
  77. Short PCPs verifiable in polylogarithmic time.
  78. Distributed Computing with Imperfect Randomness.
  79. Local Decoding and Testing for Homomorphisms.
  80. Robust local testability of tensor products of LDPC codes.
  81. On Dinur's Proof of the PCP Theorem.
  82. Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
  83. Sparse Random Linear Codes are Locally Decodable and Testable.
  84. Universal Semantic Communication I.
  85. Algebraic Property Testing: The Role of Invariance.
  86. Decodability of Group Homomorphisms beyond the Johnson Bound.
  87. 2-Transitivity is Insufficient for Local Testability.
  88. Reliable Transmission of Information.
  89. An improved lower bound on the size of Kakeya sets over finite fields,
  90. Universal Semantic Communication II,
  91. Testing Linear-Invariant Non-Linear Properties,
  92. Probabilistically Checkable Proofs,
  93. Locally Testable Codes Require Redundant Testers.
  94. Succinct Representation of Codes with Applications to Testing.
  95. Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers.
  96. A Theory of Goal-Oriented Communication.
  97. Optimal testing of Reed-Muller codes.
  98. Kakeya-type sets in finite vector spaces.
  99. Invariance in Property Testing.
  100. Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities.
  101. The P vs. NP Problem.
  102. Limits on the rate of locally testable affine-invariant codes .
  103. Testing Linear-Invariant Non-Linear Properties: A short report.
  104. Efficient Semantic Communication via Compatible Beliefs.
  105. Property Testing via Set-Theoretic Operations.
  106. Symmetric LDPC codes are not necessarily locally testable.
  107. Compression without a common prior: An information-theoretic justification for ambiguity in language.
  108. Testing linear properties: Some general themes.
  109. Patterns hidden from simple algorithms.
  110. Optimal testing of multivariate polynomials over small prime fields.
  111. On Sums of Locally Testable Affine Invariant Properties.
  112. Delays and the Capacity of Continuous-time Channels.
  113. Physical Limits of Communication (Invited Talk).
  114. A new upper bound on the query complexity for testing generalized Reed-Muller codes.
  115. Some closure features of locally testable affine-invariant properties.
  116. Communication amid uncertainty.
  117. Sparse affine-invariant linear codes are locally testable.
  118. New affine-invariant codes from lifts.
  119. Queueing with Future Information.
  120. Deterministic compression with uncertain priors.
  121. Absolutely Sound Testing of Lifted Codes.
  122. Limits of local algorithms over sparse random graphs.
  123. Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings..
  124. Approximating matching size from random streams.
  125. Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem.
  126. List decoding group homomorphisms between supersolvable groups.
  127. Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.
  128. Streaming Lower Bounds for Approximating MAX-CUT .
  129. Communication with Imperfectly Shared Randomness.
  130. Robust testing of lifted codes with applications to low-degree testing.
  131. Communication Complexity of Permutation-Invariant Functions.
  132. Communication with Contextual Uncertainty.