Algorithms (Winter 2016) by Tim Roughgarden

# click the upper-left icon to select videos from the playlist

source: Tim Roughgarden Lectures      2016年1月11日
A Second Course in Algorithms (CS261, Winter 2016)

CS261 Lecture 1(Goals/Intro to Max Flow) 1:08:17
2 (Edmonds-Karp/Dinic algorithms) 1:18:15
3 (Push-Relabel) 1:16:30
4 (Max Flow Apps) 1:22:28
5 (Min-Cost Matching) 1:21:01
6 (Generalizations) 1:17:09
7 (LP: Intro and Apps) 1:22:33
8 (LP Duality I) 1:20:40
9 (LP Duality II) 1:19:49
10 (Minimax/Simplex) 1:21:21
11 (Multiplicative Weights) 1:24:01
12 (MW/Games/LPs) 1:22:39
13 (Online Algorithms I) 1:13:24
14 (Online Algorithms II) 1:20:55
15 (Approximation Algs) 1:19:56
16 (TSP) 1:11:19
17 (LP+Approx Algs) 1:20:05
18 (Randomized Approx Algs) 1:19:23
19 (Beating Brute Force) 1:18:22
20 (Max Cut/SDP) 1:10:38

Advanced Mechanism Design (Winter 2014) by Tim Roughgarden

# click the upper-left icon to select videos from the playlist

source: Tim Roughgarden Lectures     2014年1月21日
Advanced Mechanism Design (CS364B, Winter 2014)

1 (Ascending Auctions) 1:16:22
2 (Unit-Demand Valuations) 1:18:26
3 (Crawford-Knoer Auction) 1:19:11
4 (Clinching Auction) 1:08:03
5 (Gross Substitutes I) 55:32
6 (Gross Substitutes II) 1:33:25
7 (Submodular Valuations) 1:19:57
8 (MIR and MIDR Mechanisms) 1:13:10
9 (Scaling Algorithms) 1:17:23
10 (Convex Rounding) 1:11:11
11 (Shrinking Auction) 1:06:43
12 (BIC Mechanisms) 1:28:18
13 (Black Box Reductions) 1:11:26
14 (POA of Simple Auctions) 1:16:21
15 (Bayes-Nash POA) 1:20:38
16 (First-Price Auctions) 1:12:53
17a (Uniform-Price Auctions) 51:14
17b (Beyond Smoothness) 45:29
18 (Revenue Maximization) 59:44
19 (Border's Theorem) 1:18:00
20 (Optimal Mechanisms) 1:00:25

Beyond Worst-Case Analysis (Fall 2014) by Tim Roughgarden at Stanford U

# click the upper-left icon to select videos from the playlist

source: Tim Roughgarden Lectures     2014年9月29日
Beyond Worst-Case Analysis (CS264, Fall 2014)
Course website, with problem sets, lecture notes, and related resources: http://theory.stanford.edu/~tim/f14/f14.html
Course description:
This course has two intertwined goals. The first goal is to survey several important computational problems for which the traditional worst-case analysis of algorithms is ill-suited, because it fails to differentiate meaningfully between different solutions, recommends an empirically "wrong" solution over the "right" one, or gives excessively pessimistic performance predictions. The second goal is to study systematically alternatives to worst-case analysis that nevertheless enable rigorous and robust guarantees on algorithm performance.
List of topics: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models.
Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, scheduling, linear programming, hashing, and auction theory.

1 (Introduction) 55:55 Three motivating examples. Pros and cons of worst-case analysis. Instance optimality.
2 (Instance Optimality) 1:11:16
3 (Resource Augmentation) 1:18:48
4 (Parameterized Paging) 1:19:15
5 (Recoverable Value) 1:14:49
6 (Stable Clustering I) 1:19:05
7 (Single-Link++) 1:13:38
8 (Recovering Graph Cuts) 1:17:08
9 (Compressive Sensing) 57:22
10 (Planted Graph Models) 1:10:14
11 (LP Decoding) 1:13:05
12 (Intro to Smoothed Analysis) 1:16:53
13 (Smoothed Local Search) 1:16:24
14 (Smoothed Pareto Curves) 1:08:47
15 (Pseudopoly = Smoothed Poly) 1:22:34
16 (Hashing + Pseudorandom Data) 1:18:26
17 (Self-Improving Algorithms) 1:25:12
18 (Pricing Using Samples) 1:12:06
19 (Random Permutations) 1:17:26
20 (From Distributions to Instance-Optimality) 1:16:44

Algorithmic Game Theory (Fall 2013) by Tim Roughgarden at Stanford U

# click the upper-left icon to select videos from the playlist

source: Tim Roughgarden Lectures     2013年9月25日
Algorithmic Game Theory (CS364A, Fall 2013)
Class description: Topics at the interface of computer science and game theory such as: algorithmic mechanism design; combinatorial auctions; computation of Nash equilibria and relevant complexity theory; congestion and potential games; cost sharing; game theory and the Internet; matching markets; network formation; online learning algorithms; price of anarchy; prior-free auctions; selfish routing; sponsored search.

Lecture 1 (Introduction) 1:09:24
Lecture 2 (Mechanism Design Basics) 1:12:02
Lecture 3 (Myerson's Lemma) 1:17:08
Lecture 4 (Algorithmic Mechanism Design) 1:16:00
Lecture 5 (Revenue-Maximizing Auctions) 1:18:06
Lecture 6 (Simple Near-Optimal Auctions) 1:14:31
Lecture 7 (VCG Mechanism) 1:16:56
Lecture 8 (Spectrum Auctions) 1:17:08
Lecture 9 (Beyond Quasi-Linearity) 1:17:31
Lecture 10 (Kidney Exchange, Stable Matching) 1:16:03
Lecture 11 (Selfish Routing and the POA) 1:20:55
Lecture 12 (Network Over-Provisioning) 1:18:16
Lecture 13 (Hierarchy of Equilibrium Concepts) 1:11:03
Lecture 14 (Smooth Games) 1:13:27
Lecture 15 (Best-Case and Strong Nash Equilibria) 1:15:21
Lecture 16 (Best Response Dynamics) 1:20:49
Lecture 17 (No-Regret Dynamics) 1:16:37
Lecture 18 (Swap Regret; Minimax) 1:14:51
Lecture 19 (Pure NE and PLS-Completeness) 1:12:59
Lecture 20 (Mixed NE and PPAD-Completeness) 1:14:02

Talks at Google (videos of March 2017)

source: Talks at Google
50:40 Beth Kobliner: "Make Your Kid A Money Genius (Even If You're Not)" | Talks at Google Many of us think we can have the “money talk” when our kids are old enough to get it…which won’t be for years, right? But get this: Research shows that even preschoolers can understand basic money ...
1:10:58 Chema Martinez: "No Pienses, Corre" | Talks at Google Chema Martinez is a Spanish athlete and medalist with a professional career that includes two Olympic Games, six World Championships and many more competitions. He also holds the record of being th...
56:41 Prof. Matthew Reynolds: "The World of Translation" | Talks at Google In this talk, we are joined by Prof. Matthew Reynolds, professor of English and Comparative Criticism, Tutorial Fellow at St. Anne's College at the University of Oxford, and author of Oxford Univer...
1:00:20 Hans Florine: "A Lifelong Obsession with Yosemite’s Most Iconic Climb" | Talks at Google Hans Florine is an American rock climber and motivational speaker. He is considered to be one of the fastest climbers in the world as he, together with Alex Honnold, holds the Speed Climb World Rec...
56:41 Jessica Bennett: "Feminist Fight Club" | Talks at Google You've likely read her articles in the New York Times -- she was the first journalist to profile Monica Lewinsky in a decade, spent time with Hillary Clinton's childhood friends, and investigated t...
1:04:09 Erika Lee: Stand Up/Speak Out: The Need for Asian American Activism Today | Talks at Google Professor Erika Lee discusses the history of Asians in America and also the importance of activism today. Lee is one of the nation's leading immigration and Asian American historians and has publis...
1:00:59 Leigh Thompson: "Stop Spending, Start Managing [...]" | Talks at Google In this interactive session, Thompson will share key insights from her book (co-authored with Dr. Tanya Menon), Stop Spending, Start Managing: Strategies to Transform Wasteful Habits.
The talk, l...
51:41 Heather Boushey: Finding Time: The Economics of Work-Life Conflict | Talks at Google Employers today are demanding more and more of employees’ time. And from campaign barbecues to the blogosphere, workers across the United States are raising the same worried question: How can I get...
1:04:57 Zach Barth: "Zachtronics: Ten Years of Terrible Games" | Talks at Google Zach Barth designed and developed Infiniminer, Spacechem, TIS-100, Shenzen I/O and other video games in a genre that has become named after him ("Zachlikes"). His company Zachtronics also developed...
1:20:03 More than a Woman: The Intersections of Gender, Race, and Sexual Orientation | Talks at Google In the words of the late essayist, Audre Lorde: “There is no thing as a single-issue struggle because we do not live single-issue lives.”
Invisibilized in conversations on cis-gender issues, women
54:25 Kerstin O'Shields: "Body Language in Business" | Talks at Google Kerstin O'Shields shows us how to use body language in everyday business situations.
With 25 years of training and performing in theater and opera, Kerstin O'Shields has acquired an in-depth knowl...
33:21 Kim Talon: "Kino Kimino: Bait is for Sissies" | Talks at Google Hear Kino Kimino perform a selection of their debut album, “Bait is for Sissies” at Google’s NY office. Afterward, lead vocalist and founding member Kim Talon discusses the band and recording with ...
43:08 Asif Saleh: "How Smarter Innovations Can Help Fight Poverty" | Talks at Google Asif Saleh transitioned from his role as an executive director at Goldman Sachs to a senior director at the world’s largest non-profit organizations, known as BRAC, based in Bangladesh. Recognized ...
28:27 Gillian Anderson & Jennifer Nadel: "We: A Manifesto for Women Everywhere" | Talks at Google Actress Gillian Anderson and journalist Jennifer Nadel, friends for more than a decade, have created the road map they wish they’d had for how to live a meaningful life.
"We: A Manifesto for Women...
55:00 Daniel Levitin: "Weaponized Lies: How to Think Critically in the Post-Truth Era" | Talks at Google From The New York Times bestselling author of THE ORGANIZED MIND (https://goo.gl/9d0AXx) and THIS IS YOUR BRAIN ON MUSIC (https://goo.gl/lWvwbe), a primer to the critical thinking that is more nece...
1:09:14 Mo Gawdat: "Solve for Happy: Engineer Your Path to Joy" | Talks at Google Mo Gawdat is a remarkable thinker and the Chief Business Officer at Google’s [X], an elite team of engineers that comprise Google’s futuristic “dream factory.” Applying his superior skills of logic...
46:46 Robert Amsterdam: "Disruption and the Weaponization of Law" | Talks at Google Over the past half century, we have been experiencing a tremendous acceleration in the velocity of history. As Arthur Schlesginer, Jr. originally wrote in the Atlantic in 1967, the present is becom...
22:10 Dax Shepard & Michael Peña: "CHiPs" | Talks at Google Dax Shepard and Michael Peña stopped by Google SF to discuss their new film CHiPs!
About CHiPs
Dax Shepard and Michael Peña star in the action comedy “CHiPs.” Shepard also directs from a script he...
51:13 Ben Ratliff: "Every Song Ever" | Talks at Google Veteran New York Times music critic Ben Ratliff comes to Google to discuss his book "Every Song Ever" and how he is reimagining the idea of music appreciation in the time of cloud streaming, when w...
57:55 Gershon Ben Keren: "Krav Maga Tactical Survival: Personal Safety in Action" | Talks at Google Gershon Ben Keren, is a 5th Degree Black Belt in Krav Maga (the fighting system of the IDF), and is a professional security consultant, with over 20 years working as both an operative and a trainer...
55:56 Alison Eyring: "Endurance Leadership" | Talks at Google Growth expert, Dr. Alison Eyring is CEO of Organisation Solutions and Adjunct Associate Professor at the National University of Singapore Business School. A global thought leader on building organi...
54:16 Nirali Shah: "Meditation for Re-Wilding the Self" | Talks at Google "Wisdom is sometimes unexpectedly found in raw human emotions.
In those parts of ourselves that we feel uncomfortable to look at.
Join us, as Nirali discusses how meditation can be a tool to unlo...
1:10:18 Ramón Arroyo: "Rendise No Es una Opción" | Talks at Google Ramón Arroyo was (and is) a normal person, married, one children, working for a multinational company when he was suddenly diagnosed with multiple sclerosis. During this talk, he shared with us his...
50:13 Prof. Virginia Berridge: "Public Health" | Talks at Google Virginia Berridge is Professor of History and a Director at the Centre for History in Public Health, at the London School of Hygiene and Tropical Medicine. She is an expert on the history of post-S...
46:45 Dr. Eusebio Leal Spengler: "Old Havana in the 21st Century" | Talks at Google As the official Historian of the City of Havana, Dr. Leal is in charge of the restoration and administration of Old Havana, a UNESCO world heritage site. Shortly after Google signed our first comme...
48:56 Andreas Weigend: "Data for the People" | Talks at Google DATA FOR THE PEOPLE: How to Make Our Post-Privacy Economy Work for You
Andreas Weigend is one of the world's foremost experts on the future of big data, social-mobile technologies, and consumer be...
47:54 Dava Sobel: "The Glass Universe" | Talks at Google Dava Sobel is a former New York Times science reporter and a repeated New York Times bestselling author. Her past books include "Longitude", "Galileo's Daughter", and "The Planets". A recipient of ...
1:28:31 Jason Phillips: "Practical Nutrition Application" | Talks at Google Talks at Google hosted nutrition coach Jason Phillips, author of Macros Explained, and co-founder of Driven Performance Labs for a talk on February 2nd, 2017.
Phillips uses audience questions and ...
55:01 Ted Slingerland: "Trying Not to Try" | Talks at Google This is the third in a series of Talks at Google by current and former fellows of the Center for Advanced Study in the Behavioral Sciences (CASBS) at Stanford University. Previous CASBS speakers ap...
30:30 Louise Gray: "Ethical Carnivore" | Talks at Google Louise Gray came into talk about her new book, The Ethical Carnivore. Fed up of friends claiming to care about where their meat comes from, Louise decided to follow the argument to its logical extr...
50:43 Diana Darke: "My House in Damascus" | Talks at Google Talks at Google was delighted to welcome Middle East cultural expert Diana Darke, author of My House in Damascus: An Inside View of the Syrian Crisis, for a timely talk on this essential subject. R...
53:28 Alex Goldman and PJ Vogt: "Gimlet's Reply All" | Talks at Google Get behind the scenes insight into Gimlet's Reply All podcast. It's a show about the internet and trained rats, time travel, celebrity dogs, lovelorn phone scammers, angry flower children, workplac...
35:55 Danny Boyle: "T2 Trainspotting" | Talks at Google Academy Award winning director Danny Boyle stops by Google to Talk T2 Trainspotting, the 21 years in the making sequel to the classic British hit.
Danny Boyle is best known for his work directing ...
57:43 Ryan Holiday: "Understanding Your Ego" | Talks at Google Ryan Holiday sits down with Jordan Thibodeau for an interview about his thoughts on philosophy, his latest book *Ego Is The Enemy*, and other topics not covered in his previous talks such as: how w...
56:11 Prof. Mark Maslin: "Climate Change" | Talks at Google Mark Maslin is Professor of Climatology at University College London and co-author of countless scientific papers, popular articles and books. His areas of scientific expertise include causes of pa...
58:50 Douglas Rushkoff: "Throwing Rocks at the Google Bus" | Talks at Google The digital economy has gone wrong. Everybody knows it, but no one knows quite how to fix it, or even how to explain the problem. Workers lose to automation, investors lose to algorithms, musicians...
56:07 Wendy Davis: "Deeds Not Words" | Talks at Google Wendy Davis, former Texas State Senator, will share her new organization and why women need to get involved in major issues like economic inequality and ending campus sexual assault.
Borrowing the...
50:47 Off-Broadway's "Evening at the Talk House" | Talks at Google Actors Matthew Broderick, Wallace Shawn, Annapurna Sriram, and Director/The New Group Artistic Director Scott Elliot join us for a rousing conversation about The New Group's "Evening at the Talk Ho...
48:47 Levi EagleFeather: "The Power of Peaceful Resistance" | Talks at Google Levi EagleFeather speaks at Google on integrating traditional Lakota culture into modern infrastructure to heal ourselves and protect Mother Earth.
Levi William EagleFeather is a Sicangu Lakota Si...
56:59 Marty Baron: "Digital Innovation at the Washington Post" | Talks at Google Join Richard Gingras, VP of News at Google, for a fireside chat with Marty Baron, Executive Editor of the Washington Post, where he has guided their ambitious journalistic efforts and been a drivin...
46:02 Jill Ebstein: "At My Pace: Ordinary Women Tell Their Extraordinary Stories" | Talks at Google Jill Ebstein is a Business Marketing Consultant who found her passion writing about topics that we all struggle with. At my pace is a book about ordinary women who share their extraordinary storie...
1:00:44 Cirque du Soleil: "LUZIA" | Talks at Google Cirque du Soleil returns to Google for a conversation about their latest touring production, LUZIA. They also perform two scenes: "Football Dance" and "Juggling".
Speaking are: * Heather Reilly,...
48:29 Yip Pin Xiu & Teresa Goh: "Singapore Paralympian Gold Winners" | Talks at Google Yip Pin Xiu and Theresa Goh have overcome significant challenges and uncertainty in their life in order to finally beat the world records and rise to the top. They are role models not only in sport...
58:11 Chuck Akre: "The Peregrinations of an English Major Trying to Solve the Investment Puzzle" Chuck discusses the following in his talk:
1. I started with zero knowledge
2. I needed to figure out what made a good investor
3. What made a good investment?
4. How do you...
1:08:20 Mary Wong: "Conceivable! Reversing a Modern-day Dilemma" | Talks at Google Mary Wong has been in practice for more than 20 years helping thousands of couples conceive. She is the founder of ALIVE Holistic Health Clinic and was an expert panel advisor to the Canadian gover...
50:44 Ron Gilbert: "From Maniac Mansion to Thimbleweed Park" | Talks at Google Veteran game designer Ron Gilbert has been making games since the 1980s, most notably as writer, programmer, and designer for LucasFilm Games / LucasArts, producing classics like Maniac Mansion, Mo...
44:40 Jose Quinonez: "Building on What's Good: A New Way to Fight Poverty" | Talks at Google José Quiñonez is the founding CEO of Mission Asset Fund (MAF), the nonprofit behind the award-winning Lending Circles program. To date, Lending Circles have helped more than 7,000 people across the...
59:37 Guillaume Brat: "Reducing the Cost Impact of V&V for Flight Critical Systems" | Talks at Google Guillaume Brat presents an overview of NASA’s recent research and development of V&V tools for flight critical software. He describes our overall approach and the tools we have introduced at differ...
49:20 Ruben Ayala: "From Hopelessness to Possibility" | Talks at Google Dr. Ruben Ayala is the Senior Vice President, Medical Affairs, Operation Smile, Inc.
Around the world, thousands of children are born with cleft lips and palates, a facial birth deformity with po...
47:03 Alan Burdick: "Why Time Flies" | Talks at Google Alan Burdick is a staff writer and former senior editor at The New Yorker. His most recent book, "Why Time Flies: A Mostly Scientific Investigation," was published in January by Simon & Schuster. Y...
1:02:56 Jad Abumrad: "Radiolab (Podcast)" | Talks at Google Get behind the scenes insight into WNYC's Radiolab podcast. WNYC's Radiolab is a show about curiosity. Where sound illuminates ideas, and the boundaries blur between science, philosophy, and human ...
1:03:05 Cecile Richards: "Technology and Healthcare Delivery" | Talks at Google Cecile Richards, President of Planned Parenthood Federation of America and Julia Paige, Google's Director of YouTube for Good, discuss Planned Parenthood’s work, the largest misconceptions and chal...
47:21 Judd Apatow & Pete Holmes: "HBO's Crashing" | Talks at Google Comedy connoisseurs Judd Apatow and Pete Holmes stop by Google to Talk about their latest show "Crashing" on HBO, and the true life events that inspired the show.
More about HBO's "Crashing" : Pet...
58:30 Michael & Jacky Recchiuti & Amanda Snouffer: "San Francisco Chocolatier..." | Talks at Google Join San Francisco chocolatier Recchiuti Confections in the teaching kitchen to celebrate Valentine's Day... and the art of chocolate truffle-making. Founders Michael and Jacky Recchiuti, and Creat...
54:46 Lauren Templeton: "Investing the Templeton Way" | Talks at Google This talk covered the subjects of value investing and behavioral finance through the lens of a practitioner. Ms. Templeton spoke on the subject with an eye towards both beginners and practitioners,...
50:47 Negotiation & Personal Branding | Talks at Google This is a power-packed panel discussion on Negotiation and Personal branding. The speakers take a leaf out of their experience to share insights on how they have built their careers.
Lakshmi Pratu...
36:56 Paul Smith: "Sell with a Story" | Talks at Google Bestselling author of Lead with a Story, Paul Smith, shares with us the ingredients to effective and persuasive storytelling, highlighting his new research found in his new book, Sell with a Story....
1:06:58 Jerry Horwath: "The Voice of the Toronto Blue Jays" | Talks at Google Jerry Horwath has been the voice of the Toronto Blue Jays since 1981. Eric Morris interviews him just before he leaves for the Jays' winter training camp in Florida. Enjoy this candid and lively ta...
58:43 Charlie Engle: "Running Man: A Memoir" | Talks at Google A compulsively readable, remarkably candid memoir from world class ultra-marathon runner Charlie Engle chronicling his globe-spanning races, his record-breaking run across the Sahara Desert, and ho...
1:43:02 "Every 28 Hours" Play and Panel Discussion | Talks at Google Every 28 Hours” is a series of one-minute plays focused on the contested statistic that every twenty­-eight hours a black person is killed by law enforcement in America. Inspired by true stories an...
56:19 Tiffany Dufu: "Join the Movement to Drop the Ball" | Talks at Google Drop the Ball shows women how to cultivate the single skill they really need in order to succeed: the ability to let go. Tiffany Dufu, author of the highly anticipated book, Drop the Ball: Achievin...
48:14 Cirque du Soleil Paramour: A Cirque du Soleil Musical | Talks at Google Join leading lady Ruby Lewis, Stage Manager Claudette Waddle, Musical Director Seth Stachowski, and strongmen/acrobats Tomasz Wilkosz and Rafal Kaszubowski for a Talks at Google event discussing Ci...