1 of 45

CS 786: Randomized ALGORITHMS�LECTURE 1 (04 Jan)

INTRODUCTION

https://sites.google.com/view/kumarakash/teaching/cs-786-randomized-algorithms

2 of 45

Logistics

​

Philosophy

​

Vignette

3 of 45

TEACHING STAFF

Instructor: Akash Kumar

akash@cse.iitb.ac.in

​

Teaching Assistants:

TBD

​

Office Hours:

CC 219, Monday 4-5

4 of 45

GRADE

AA: max{80%, 5th highest}

AB: ≥ 7/8 * cutoff for AA.

BB: ≥ 6/8 * cutoff for AA.

BC: ≥ 5/8 * cutoff for AA.

CC: ≥ 4/8 * cutoff for AA.

5 of 45

COURSEWORK

30%: 4 psets, roughly once / 2 weeks (*)

20%: Final Exam (*)

20%: Course project

20%: Scribing

10%: Class participation

​

(*) Conditioned on getting a TA

6 of 45

PARTICIPATION

Participation = engagement during lectures and in discussions on WhastApp group

​

Please stop me and ask questions during lectures!

If you’re confused about something / can’t read my handwriting, odds are you’re not the only one

7 of 45

SCRIBING

Signup sheet will be posted end of today on course webpage

    • Sign up for 1 slot by Tomorrow.
    • First come first serve
    • Link to official scribing template and instructions will also be posted

8 of 45

FINAL PROJECT

Two options

    • Original research
    • Expository survey

​

List of (optional) suggested topics/readings will be posted in the first few weeks of semester

​

Timing:

    • Last pset will be due ~end of March
    • Submit project idea by first week of April (details to follow)

​

Group projects (of up to 3) strongly encouraged.

9 of 45

Logistics

​

Philosophy

​

Vignette

10 of 45

THIS COURSE

We will focus on algorithms with provable guarantees.

Key Message: Randomness ≠ Chaos.

Can domesticate randomness to obtain algorithmic mileage.

You do this daily

  • Personalized Search Results on eg, Google.
  • When you use chat-gpt or any LLM.
  • Drug Design and synthesis
  • Any corollary of second law of thermodynamics
  • Any application of quantum field theory.
  • CGI for Marvel Movies, Bahubali, John Wick…
  • …. And more

11 of 45

Where all will I encounter randomness in this class?

  • Everywhere.

​

​

Problem

Input Instance

Algorithm

Output

12 of 45

Randomness in the Natural Sciences (Eg in Physics, Biology, Social Sciences etc)

13 of 45

Source: Aleph 0 video on Navier-Stokes

14 of 45

Papadimitriou et al – Fudamentals of Neuroscience

  • Computation

+

​

​

​

Use randomness to model neural pathways.

A simple enough randomized model already explains the response of our brain to many complex stimuli.

Theory still in infancy – likely falsifiable.

May reveal mysteries

15 of 45

Pearson’s Analysis of Species of Crabs

16 of 45

Pearson 1894 – The man, the myth, the legend

​

​

​

​

​

​

​

  • Picture stolen from Ankur Moitra’s talk on Disentangling Gaussians

17 of 45

Pearson 1894 – The man, the myth, the legend

​

​

​

​

​

​

​

  • Picture stolen from Ankur Moitra’s talk on Disentangling Gaussians

Features of crabs seen seem to come from blue curve.

​

Mystery, why is this not bell shaped?

​

Resolution – there are two different species of

crabs in the area

18 of 45

Random Optimization Problems

  • Physical models often assume that some phenomena is a result of some optimization problem nature solves.
  • The relevant optimization problem has some randomized parameters. Useful perspective in Statistical Physics, spin glasses, study of ferromagnetic substances, etc.

19 of 45

Random Optimization Problems

  • Physical models often assume that some phenomena is a result of some optimization problem nature solves.
  • The relevant optimization problem has some randomized parameters. Useful perspective in Statistical Physics, spin glasses, study of ferromagnetic substances, etc.
  • Breakthroughs like Parisi’s Formula – Physics Nobel Prize 2021.

20 of 45

Diffraction limit and Airy Disks

Point source of light

Circular aperture

Imaging plane

Lens 1

Lens 2

Airy disk

Slide stolen from Sitan Chen

21 of 45

Suppose I image two stars and get this

Can I always tell the two stars apart?

​

Eg in First two figures looks like we can but in the last maybe not?

​

Conventional wisdom: If two Airy disks are too close, the blur makes it impossible to distinguish them

​

Slide stolen from Sitan Chen

22 of 45

Suppose I image two stars and get this

Physical Obstacle?

​

Physicists thought maybe physics of diffraction poses limits to resolution.

​

Conventional wisdom: If two Airy disks are too close, the blur makes it impossible to distinguish them

​

Slide stolen from Sitan Chen

23 of 45

A >150 years long debate begins

Abbe

Rayleigh

Sparrow

Houston

Dawes

Buxton

Schuster

 

”Rayleigh criterion”: Resolution becomes impossible as soon as the center of one disk touches the first ring of another

 

Slide stolen from Sitan Chen

24 of 45

A >150 years long debate begins

Abbe

Rayleigh

Sparrow

Houston

Dawes

Buxton

Schuster

 

”Feynman and others argue differently”: With more measurements, maybe you can tell the stars apart.

 

Slide stolen from Sitan Chen

25 of 45

A >150 years long debate begins

”Feynman and others argue differently”: With more measurements, maybe you can tell the stars apart.

 

Slide stolen from Sitan Chen

26 of 45

A >150 years long debate begins

 

Slide stolen from Sitan Chen

”[Chen-Moitra 20]”: Resolved at long last. Among many other things, makes heavy use of probabilistic arguments.

27 of 45

Randomness in Computer Science

          • Get that pillow ready, long list incoming.

28 of 45

29 of 45

30 of 45

31 of 45

An interlude: The Average Salary Puzzle

  • I want to know average salary of us all.
  • None of us want to reveal our salary though.
  • Any help?
  • Hint: Use randomness

32 of 45

An interlude: The Average Salary Puzzle

  • I want to know average salary of us all.
  • None of us want to reveal our salary though.
  • Any help?
  • Hint: Use randomness

s1

s2

s3

s4

s5

R0

R1 = R0 + s1

R2 = R1 + s2

R3 = R2 + s3

R4 = R3 + s4

R5 = R4 + s5

33 of 45

Interlude Continued: The Millionaire Problem

  • Adani and Ambani are both millionaires.
  • They have a problem.
  • They want to find out who is richer but don’t want to reveal their net worth to the other.
  • Any help?
  • Hint: Use randomness.

​

34 of 45

Interlude Continued: The Millionaire Problem

  • Adani and Ambani are both millionaires.
  • They have a problem.
  • They want to find out who is richer but don’t want to reveal their net worth to the other.
  • Any help?
  • Hint: Use randomness. A 3-step recipe
  • Preparation
  • More Preparation
  • Wrap-up

35 of 45

Interlude Continued: A magical primitive

1-out-of-2 oblivious transfer

Preparation – Oblivious Transfer.

b

x0, x1

b

x0, x1

xb

Client

Server

36 of 45

Interlude Continued: A magical primitive

More Preparation – t-Repeated Oblivious Transfer.

bi

xb

1-out-of-2t oblivious transfer

b1, b2,…, bt

Client

Server

x0, x1

1

1

x0, x1

2

2

x0, x1

t

t

x0, x1

i

i

i

37 of 45

Interlude Continued: Finally, the resolution

Use 1-out-of-2t oblivious transfer in an ingenious way [Yao 1982].

Adani

Rs W1

Ambani

Rs W2

1: B wins

2: B wins

3: B wins

*

*

W2: B wins

W2+1: A wins

W2+2: A wins

*

*

2*W2: A wins

​

Send me W1-th entry in table using oblivious transfer.

38 of 45

Killer Apps of Randomized Computation in CS

Cryptography

PCPs and Blockchains

Complexity Theory and Lower Bounds

Computer Vision

Natural Language Processing

Estimation Algorithms

Sublinear time Algorithms

Computer Graphics

Machine Learning

Markov Chain and Monte Carlo

Quantum Computing

Mechanism Design and Auction Design

Streaming Algorithms

Dynamic Algorithms

MPC and big data algorithms

Distributed Computing

Parallel Computing

Online Algorithms

Optimization

39 of 45

Logistics

​

Philosophy

​

Vignette

40 of 45

Estimation Algorithms

  • Who will win the next election?
  • Suppose two-party election
  • Winner gets 10% more votes than the loser.

​

  • Estimate the average of a huge list
  • Is this always possible?
  • Okay, suppose all the numbers lie in a small range. What now?

41 of 45

Sublinear Time Algorithms(!) – You are kidding, right?

  • No.
  • Recall the voting example.
  • An outrageous phenomena?
  • CLT zindabaad.
  • Concentration inequalities are probability theory’s gift to CS.

42 of 45

Complexity Theory

Too much to say.

So, let’s just say this.

​

Can you derandomize every randomized algorithm?

  • Talk to Rohit Gurjar and take his class on Pseudorandomness
  • Derandomization algorithms for max-cut

43 of 45

Complexity Theory

Too much to say.

So, let’s just say this.

​

Can you derandomize every randomized algorithm?

  • Talk to Rohit Gurjar and take his class on Pseudorandomness
  • Derandomization algorithms for max-cut

44 of 45

Complexity Theory

Too much to say.

So, let’s just say this, and let’s add this as well.

​

Randomized methods are instrumental in approaching separations of complexity classes.

​

  • Parity not in AC0
  • Separation of BQP and PH relative to random oracles.
  • PCP inspired separations eg MIP* ≠ RE.

45 of 45

Randomized Computation in Engineering and Elsewhere

  • Vaccine Testing.
  • Airplane Design.
  • Autombile Design.
  • Chip Design.
  • Financial Trading and stock markets.
  • Control Theory and stable flight trajectories.
  • And unimaginably more.