6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova

Lecture 7 Video     [previous] [next]

Video Player is loading. Play Video PlaySkip backward 5 secondsSkip forward 5 seconds Mute Current Time 0:00 / Duration -:- Loaded: 0% 0:00 Stream Type LIVE Seek to live, currently behind liveLIVE Remaining Time --:-   1x Playback Rate 0.5x 0.6x 0.7x 0.8x 0.9x 1x, selected 1.1x 1.2x 1.3x 1.4x 1.5x 1.6x 1.7x 1.8x 1.9x 2x 2.1x 2.2x 2.3x 2.4x 2.5x 2.6x 2.7x 2.8x 2.9x 3x 3.1x 3.2x 3.3x 3.4x 3.5x 3.6x 3.7x 3.8x 3.9x 4x Chapters Chapters Descriptions descriptions off, selected Captions captions settings, opens captions settings dialog captions off English, selected Audio Track Picture-in-PictureFullscreen This is a modal window. The media could not be loaded, either because the server or network failed or because the format is not supported. Beginning of dialog window. Escape will cancel and close the window. Text ColorWhiteBlackRedGreenBlueYellowMagentaCyanOpacityOpaqueSemi-Transparent Text Background ColorBlackWhiteRedGreenBlueYellowMagentaCyanOpacityOpaqueSemi-TransparentTransparent Caption Area Background ColorBlackWhiteRedGreenBlueYellowMagentaCyanOpacityTransparentSemi-TransparentOpaque Font Size 50%75%100%125%150%175%200%300%400% Text Edge Style NoneRaisedDepressedUniformDrop shadow Font Family Proportional Sans-SerifMonospace Sans-SerifProportional SerifMonospace SerifCasualScriptSmall Caps Reset restore all settings to the default valuesDone Close Modal Dialog End of dialog window. Download Video: 360p, 720p

Handwritten notes, page 1/6 • [previous page] • [next page] • [PDF] Video times: • 0:16–7:47 Handwritten notes, page 1/6 • [previous page] • [next page] • [PDF]

Slides, page 13/28 • [previous page] • [next page] • [PDF] Video times: • 32:55–36:00 Figures 11 and 12 of http://simon.bailey.at/random/kaye.minesweeper.pdf which in turn is based on http://dx.doi.org/10.1145/1008354.1008356 Slides, page 13/28 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.