Randomness

From ResearchWiki

Contents 1 Analyzing Randomized Algorithms 1.1 When independence breaks down 2 Using Randomization as a tool 3 How powerful is randomness ? 4 Where does it come from ? 5 How can we get rid of it 6 Randomness and Quantum Computing 7 Project Ideas

Analyzing Randomized Algorithms

• Upper bounds
  • Simple tail bounds
  • martingales, MOBD
  • medians

When independence breaks down

• Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM J. Discrete Math., 8(2):223–250, 1995.
• Positive influence and negative dependence
• Balls and bins: a study in negative dependence
• Chernoff and beyond: a survey
• Course on concentration of measure (and surveys by McDiarmid, Lugosi and Talagrand)

Lower Bounds

• Minimax and Game Trees

Using Randomization as a tool

• Probabilistic Method
  • Lovasz Local Lemma
• Randomized Incremental Constructions (and markov incremental constructions)
• Hashing (be random to confuse adversary)

• Randomized Rounding

• Approximate Counting (luca's post on expansion and cheeger constants)

• markov chains and expanders

• random projections
• random sampling

How powerful is randomness ?

• RP,BPP,ZPP
• Hardness via Randomness
• Interactive Proofs
  • Arthur Merlin Games
• RNC vs NC:

Where does it come from ?

• Pseudorandom generators, expanders
• Physical sources of randomness ? (Brian Hayes article)

How can we get rid of it

• Derandomization (pseudorandomness)
• Discrepancy (quasi-randomess)

Randomness and Quantum Computing

• Bell's paradox, and exponentially large probability distributions.

Project Ideas

• A taxonomy of tail bounds (given a situation, which tail bounds make sense)
• Classification of expanders, extractors, concentrators and the like
• A review of the natural proofs idea (in elementary form)
• Where does randomization give strict improvements ? (volume estimation, communication complexity)