Open Problems

A PDF version of the open problems is available here.

• Expanders and Extractors Workshop (Jan 30–Feb 3)
  • Partial Steiner systems of large girth, Nati Linial
  • Cliques in near Ramanujan Graphs, Noga Alon
  • On the extractable entropy from zero-fixing sources, Gil Cohen
  • Beating the expander mixing lemma for small sets, David Zuckerman
  • Spectral radius problem for free groups, Emmanuel Breuillard
  • Explicit Coding Power Series, Anup Rao
• Cryptography using Weak Sources of Randomness (Feb 6–Feb 9)
  • Interactive proofs with imperfect randomness.
  • Extraction from limited “bit-coin source”
  • Separation between encryption and extraction.
  • Is true randomness inherent for sharing schemes?
  • Beating RT-bound using computational extractor.

Feel free to send open problems to Marco Carmosino and/or Jarrod Millman.