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. The approximability of constraint satisfaction problems.
  56. Coding theory: Tutorial & Survey.
  57. Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms.
  58. Complexity classifications of Boolean constraint satisfaction problems.
  59. Guessing secrets efficiently via list-decoding.
  60. Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.
  61. Reflections on ``Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes''.
  62. Decoding concatenated codes using soft information.
  63. A fuzzy vault scheme.
  64. Locally testable codes and PCPs of almost-linear length.
  65. Reconstructing curves in three (and higher) dimensional spaces from noisy data.
  66. Derandomizing low degree tests via epsilon-biased spaces noisy data.
  67. Bounds on 2-query codeword testing.
  68. Robust PCPs of proximity, shorter PCPs, and applications to coding
  69. Robust locally testable codes and products of codes
  70. Optimal error-correction against computationally bounded noise.
  71. Simple PCPs with poly-logarithmic rate and query complexity.
  72. Derandomization of auctions.
  73. Short PCPs verifiable in polylogarithmic time.
  74. Reliable Transmission of Information.
  75. Local Decoding and Testing for Homomorphisms.
  76. Robust local testability of tensor products of LDPC codes.
  77. On Dinur's Proof of the PCP Theorem.
  78. Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
  79. Sparse Random Linear Codes are Locally Decodable and Testable.
  80. Universal Semantic Communication I.
  81. Algebraic Property Testing: The Role of Invariance.
  82. Decodability of Group Homomorphisms beyond the Johnson Bound.
  83. 2-Transitivity is Insufficient for Local Testability.
  84. Extensions to the Johnson bound.