The library
What my talks point to: papers, videos, things to play with, and tools.
Shaded: things I wrote or worked on.
Showing 348 of 348
Nothing matches these filters.
- Book
Parameterized Algorithms (textbook, free PDF on the companion site)
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
The standard textbook, free to download: kernels, branching, iterative compression, treewidth and lower bounds.
In On the Infeasibility of Polynomial Kernelization Connected Dominating Set and Short Cycles Expansions for Reductions Iterative Compression On the Kernelization Complexity of Colorful Motifs From FVS to Planar F-Deletion Kernelization Separators with Non-Hereditary Properties Cheat Sheets for Hard Problems Parameterized Algorithms using Matroids Parameterized Complexity school lectures An Introduction to Parameterized Algorithms Protrusion Reduction Techniques Algorithmic Aspects of Firefighting
- Interactive
The Evolution of Trust
Nicky Case
The game-theory explorable behind the icebreaker: play it to see how trust is built and lost.
In Being a Successful Grad Student Explorable Explanations: Interactive Essays The Evolution of Trust The Games We Play Career Opportunities for Women in Computing From Puzzles to Problems: Fun with STEM Programming Beyond Block Coding Building Joyful Interactives
- Survey
Fair Division of Indivisible Goods: Recent Progress and Open Questions
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, Xiaowei Wu
Survey of fair division with indivisible goods with a long list of open questions.
In Current Research Directions in Fair Division The Games We Play On Fair Division with Binary Valuations Respecting Social Networks Envy-Free and Efficient Allocations for Graphical Valuations The Math of Cutting Cake and Dividing Candy Algorithmic Fairness in Resource Allocation On Fairness with Graphical Valuations
- Book
Handbook of Computational Social Choice
F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia (eds.)
The standard reference, free as a PDF: voting, fair allocation, matching and more, by leading researchers.
In An Introduction to Computational Social Choice Efficient Algorithms for Hard Problems on Structured Electorates Elicitation for Preferences Single Peaked on Trees A Parameterized Perspective on Protecting and Attacking Elections Current Research Directions in Fair Division Parameterized Approaches to Kemeny Rank Aggregation
- Interactive
The Magic of the Thirds (27-card trick)
Interactive linked in Neeldhara's slides
Play the 27-card trick on screen, then work out why three rounds of dealing always find the card.
In Some Algorithmic Excursions A Few Algorithmic Puzzles (and Why You Should Care) Recreational Math and Science: In the Classrooms and Beyond From Puzzles to Problems: Fun with STEM Programming Beyond Block Coding Magical Mathematics
- Book
Kernelization: Theory of Parameterized Preprocessing
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
The standard textbook on kernels; Part III treats lower bounds via distillation and composition.
In Efficient Simplification Expansions for Reductions Lower Bounds on Kernelization From FVS to Planar F-Deletion Kernels for F-Deletion
- Paper
Lower Bounds on Kernelization, which I wrote or worked on
Neeldhara Misra, Venkatesh Raman, Saket Saurabh
My companion survey on proving that small kernels are unlikely to exist.
PDF of Lower Bounds on Kernelization
In On the Infeasibility of Polynomial Kernelization Efficient Simplification Lower Bounds on Kernelization Kernelization Parameterized Complexity school lectures
- Paper
Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms, which I wrote or worked on
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh
FOCS 2012
In From FVS to Planar F-Deletion Kernels for F-Deletion Parameterized Graph Modification: A Modern Perspective Algorithms for Planar F-Deletion and Satisfiability Protrusion Reduction Techniques
- Paper
Hitting Forbidden Minors: Approximation and Kernelization, which I wrote or worked on
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, Saket Saurabh
The paper with the q-expansion lemma and the polynomial kernels for hitting θc minors.
In Expansions for Reductions From FVS to Planar F-Deletion Kernels for F-Deletion Protrusion Reduction Techniques
- Paper
On Fair Division with Binary Valuations Respecting Social Networks, which I wrote or worked on
Neeldhara Misra, Debanuj Nayak
CALDAM 2022
In The Games We Play On Fair Division with Binary Valuations Respecting Social Networks The Math of Cutting Cake and Dividing Candy On Fairness with Graphical Valuations
- Interactive
Binary magic cards: guess the number, which I wrote or worked on
Neeldhara Misra
Five yes/no questions pin down any number from 1 to 31; a hands-on look at binary representation.
In Some Algorithmic Excursions From Puzzles to Problems: Fun with STEM Programming Beyond Block Coding
- Reference
De Bruijn sequence
Wikipedia
Cyclic strings in which every block of a given length appears exactly once, with constructions via Euler tours.
In Problem Solving with Python Two Tricks Magical Mathematics
- Video
Domain Restrictions and Multiwinner Elections (ACM Summer School on Algorithmic Game Theory 2019), which I wrote or worked on
Neeldhara Misra
My own summer-school lecture on restricted domains and committee elections, at a gentler pace.
In Efficient Algorithms for Hard Problems on Structured Electorates Chamberlin–Courant on Restricted Domains Multiwinner Voting
- Paper
Envy-Free and Efficient Allocations for Graphical Valuations, which I wrote or worked on
Neeldhara Misra, Aditi Sethia
Recent work on when envy-free, efficient allocations can be found for graph-structured valuations.
In Envy-Free and Efficient Allocations for Graphical Valuations The Math of Cutting Cake and Dividing Candy On Fairness with Graphical Valuations
- Video
Fairness Notions for Indivisible Goods (ACM Summer School on Algorithmic Game Theory 2019)
Siddharth Barman
Summer-school lecture on fairness notions for indivisible goods, from the school where I also taught.
In On Fair Division with Binary Valuations Respecting Social Networks Envy-Free and Efficient Allocations for Graphical Valuations Algorithmic Fairness in Resource Allocation
- Paper
Kernelization – Preprocessing with a Guarantee, which I wrote or worked on
Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh
PDF of Kernelization – Preprocessing with a Guarantee
In Efficient Simplification Kernelization Parameterized Complexity school lectures
- Course
Parameterized Algorithms (NPTEL course playlist), which I wrote or worked on
Neeldhara Misra and Saket Saurabh (NPTEL)
My full online course for anyone who wants to learn the techniques properly.
In Cheat Sheets for Hard Problems Parameterized Complexity school lectures An Introduction to Parameterized Algorithms
- Book
Parameterized Algorithms (textbook)
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
The standard textbook, free to download: kernels, branching, iterative compression, treewidth and lower bounds.
In An FPT Algorithm for Maximum Edge Coloring Hardness of r-Dominating Set on Graphs of Diameter (r+1) Max q-Colorable Induced Subgraph on Perfect Graphs
- Paper
Saving Critical Nodes with Firefighters is FPT, which I wrote or worked on
Jayesh Choudhari, Anirban Dasgupta, Neeldhara Misra, M. S. Ramanujan
Firefighting is FPT in the number of firefighters, via important separators.
In Algorithmic Aspects of Firefighting The Games We Play Games of Pursuit and Evasion
- Interactive
Spliddit
Ariel Procaccia and collaborators
Free website that splits rent, goods, tasks and credit with provable fairness guarantees; try it yourself.
In Current Research Directions in Fair Division On Fair Division with Binary Valuations Respecting Social Networks Algorithmic Fairness in Resource Allocation
- Survey
Structured Preferences (Trends in Computational Social Choice, ch. 10)
Edith Elkind, Martin Lackner, Dominik Peters
Free book chapter on single-peaked, single-crossing and tree-based domains and what they make tractable.
In Efficient Algorithms for Hard Problems on Structured Electorates Elicitation for Preferences Single Peaked on Trees Chamberlin–Courant on Restricted Domains
- Paper
(Meta) Kernelization
H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, D. M. Thilikos
Where protrusion replacement was developed, the tool the thesis adapts to general graphs.
- Paper
A Characterization of Spartan Graphs and New Lower Bounds for Eternal Vertex Cover, which I wrote or worked on
Neeldhara Misra, Saraswati Girish Nanoti
König graphs, new lower bounds and a matching-based characterization of all such graphs.
In Games of Pursuit and Evasion Eternal Versions of Vertex Cover and Dominating Set
- Article
Advice for the budding theorist
Boaz Barak (Windows On Theory)
Five candid tips on grad school and research life, linked from the 2023 deck.
In Being a Successful Grad Student Early Career Researcher Presentation
- Article
Card Colm
Colm Mulcahy
Home of Colm Mulcahy, author of Mathematical Card Magic, with columns on self-working, mathematics-based card tricks.
In Recreational Math and Science: In the Classrooms and Beyond Magical Mathematics
- Video
Conversation with Neeldhara Misra: Journey of a Computer Scientist
Pratidhvani podcast
A two-hour conversation about my path from literature and mathematics to computer science.
- Course
CS Unplugged
Computer Science Education Research Group, University of Canterbury
Free activities that teach computer science through games and puzzles with cards, string and crayons, no computer needed.
In Some Algorithmic Excursions From Puzzles to Problems: Fun with STEM
- Reference
Dominating set
Wikipedia
Background on the problem, including its parameterized complexity and its many variants.
In Hardness of r-Dominating Set on Graphs of Diameter (r+1) Parameterized Algorithms for Variants of Dominating Set
- Paper
Efficient Fair Division with Minimal Sharing
Fedor Sandomirskiy, Erel Segal-Halevi
Introduces fair division with minimal sharing and the degeneracy notion this work builds on (Operations Research, 2022).
In Fair Division is Hard even for Amicable Agents Fair Division with Minimal Sharing
- Paper
EFX Allocations on Graphs
George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa
EC 2023 paper (also titled "Fair allocation in graphs") that introduced graphical valuations and proved EFX allocations exist.
In Envy-Free and Efficient Allocations for Graphical Valuations On Fairness with Graphical Valuations
- Paper
Elicitation for Preferences Single Peaked on Trees, which I wrote or worked on
Palash Dey, Neeldhara Misra
In Efficient Algorithms for Hard Problems on Structured Electorates Elicitation for Preferences Single Peaked on Trees
- Reference
Envy-free item allocation
Wikipedia
Background on envy-freeness and its relaxations EF1 and EFX.
In Envy-Free and Efficient Allocations for Graphical Valuations On Fairness with Graphical Valuations
- Essay
Essays and Opinions
Oded Goldreich
A long-running collection of essays on research, the TCS community and academic life; on the 2013 reading list.
In A Career in Academia: Why and Why Not? Early Career Researcher Presentation
- Paper
Eternal Vertex Cover on Bipartite Graphs, which I wrote or worked on
Neeldhara Misra, Saraswati Girish Nanoti
My results on the eternal vertex cover game: hard on bipartite graphs, easy on co-bipartite ones.
In Games of Pursuit and Evasion Eternal Versions of Vertex Cover and Dominating Set
- Essay
Explorable Explanations
Bret Victor
The 2011 essay that named the idea of reactive, explorable documents.
In Explorable Explanations: Interactive Essays Building Joyful Interactives
- Paper
Fair Division Is Hard Even for Amicable Agents, which I wrote or worked on
Neeldhara Misra, Aditi Sethia
PDF of Fair Division Is Hard Even for Amicable Agents
In Fair Division is Hard even for Amicable Agents Fair Division with Minimal Sharing
- Paper
Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations
Samuel Bismuth, Ivan Bliznets, Erel Segal-Halevi
Related work on fair division when only a bounded number of goods may be shared.
In Fair Division is Hard even for Amicable Agents Fair Division with Minimal Sharing
- Video
Fold and Cut Theorem - Numberphile
Katie Steckles, Numberphile
A ten-minute demonstration of cutting letters and shapes from folded paper with one cut.
In Recreational Math and Science: In the Classrooms and Beyond Geometric Puzzles: Fold and Cut
- Reference
Graph Modification Problems (Dagstuhl Seminar 14071), Dagstuhl Reports 4(2)
Hans L. Bodlaender, Pinar Heggernes, Daniel Lokshtanov (eds.)
Talk abstracts and a list of open problems from the 2014 seminar.
In Max q-Colorable Induced Subgraph on Perfect Graphs Parameterized Graph Modification: A Modern Perspective
- Paper
Hardness of r-dominating set on Graphs of Diameter (r + 1), which I wrote or worked on
Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, M. S. Ramanujan, Saket Saurabh
IPEC 2013
In Hardness of r-Dominating Set on Graphs of Diameter (r+1) Parameterized Algorithms for Variants of Dominating Set
- Survey
Having a Hard Time? Explore Parameterized Complexity! (Trends in Computational Social Choice, ch. 11)
Britta Dorn, Ildikó Schlotter
Friendly introduction to parameterized complexity and kernelization for social choice problems.
In A Parameterized Perspective on Protecting and Attacking Elections On the Parameterized Complexity of Party Nominations
- Article
How to give a great research talk
Simon Peyton Jones
A video and slides with guidelines for research talks that make people want to read the paper.
In Being a Successful Grad Student Technical Presentation Skills vs Interpersonal Skills
- Interactive
Interactives, which I wrote or worked on
Neeldhara Misra
Games, puzzles and mathematical explorations I build, for a hands-on taste of playful computing.
- Reference
Kernelization (Wikipedia)
Wikipedia
Good short introduction to kernels and their equivalence with fixed-parameter tractability.
- Paper
Kernelization, Planar F-Deletion, which I wrote or worked on
Neeldhara Misra
My short encyclopedia entry on the problem and its kernels.
In From FVS to Planar F-Deletion Protrusion Reduction Techniques
- Video
Kernelization: High Degree Rule (NPTEL Parameterized Algorithms, mod01lec03), which I wrote or worked on
NPTEL course by Neeldhara Misra and Saket Saurabh
Opens the kernelization module of my NPTEL course (Point Line Cover, Edge Clique Cover, Vertex Cover); later lectures cover d-Hitting Set, crowns and the expansion lemma.
- Paper
Kernels for the F-Deletion Problem (PhD thesis, IMSc repository), which I wrote or worked on
Neeldhara Misra
My PhD thesis, free to download; part of it studies Colorful Motifs.
In On the Kernelization Complexity of Colorful Motifs Kernels for F-Deletion
- Lecture notes
Lecture Notes on Fair Division
Ulle Endriss
Short, readable lecture notes covering cake cutting and indivisible goods.
In Current Research Directions in Fair Division Algorithmic Fairness in Resource Allocation
- Book
Multi-Winner Voting with Approval Preferences
Martin Lackner, Piotr Skowron
Open-access book on approval-based committee rules and proportionality.
- Course
NPTEL course: Parameterized Algorithms, which I wrote or worked on
Neeldhara Misra and Saket Saurabh
Full online course with lectures on kernels and much more.
In Efficient Simplification Algorithms for Planar F-Deletion and Satisfiability
- Paper
On Problems without Polynomial Kernels (technical report)
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin
Where compositions and distillations were introduced.
In On the Infeasibility of Polynomial Kernelization Lower Bounds on Kernelization
- Paper
On the Complexity of Chamberlin-Courant on Almost Structured Profiles, which I wrote or worked on
Neeldhara Misra, Chinmay Sonar, P. R. Vaidyanathan
In Efficient Algorithms for Hard Problems on Structured Electorates Chamberlin–Courant on Restricted Domains
- Paper
On the Complexity of Two Dots for Narrow Boards and Few Colors, which I wrote or worked on
Davide Bilò, Luciano Gualà, Stefano Leucci, Neeldhara Misra
Follow-up: still hard with only 3 colours or 2 columns, but easy on one column with few goals.
- Paper
On the Complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules, which I wrote or worked on
Chinmay Sonar, Palash Dey, Neeldhara Misra
In Chamberlin–Courant on Restricted Domains Multiwinner Voting
- Paper
On the Kernelization Complexity of Colorful Motifs, which I wrote or worked on
Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chintan Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, M. S. Ramanujan
IPEC 2010
In On the Kernelization Complexity of Colorful Motifs Kernels for F-Deletion
- Paper
On the Structure of EFX Orientations on Graphs
Jinghan A. Zeng, Ruta Mehta
Which graphs always admit EFX orientations.
In Envy-Free and Efficient Allocations for Graphical Valuations On Fairness with Graphical Valuations
- Reference
Parameterized complexity
Wikipedia
Solid overview of fixed-parameter tractability and the W-hierarchy.
In Cheat Sheets for Hard Problems An Introduction to Parameterized Algorithms
- Paper
Preference Elicitation For Single Crossing Domain, which I wrote or worked on
Palash Dey, Neeldhara Misra
In Efficient Algorithms for Hard Problems on Structured Electorates Elicitation for Preferences Single Peaked on Trees
- Survey
Protecting a Graph with Mobile Guards
William F. Klostermeyer, Christina M. Mynhardt
A survey of eternal domination and eternal vertex cover.
In Games of Pursuit and Evasion Eternal Versions of Vertex Cover and Dominating Set
- Video
Reductions: Problems as Hard as Clique (Dominating Set, Set Cover) (NPTEL Parameterized Algorithms, Week 12), which I wrote or worked on
NPTEL Parameterized Algorithms course (Neeldhara Misra and Saket Saurabh)
Why Dominating Set resists parameterization by solution size, via parameterized reductions.
In Hardness of r-Dominating Set on Graphs of Diameter (r+1) Parameterized Algorithms for Variants of Dominating Set
- Talk
Saket Saurabh: Parametrized Algorithms and possible future directions
Saket Saurabh (Hausdorff Center for Mathematics)
Linked from the 2023 slides: an overview of where parameterized complexity research is heading.
In Cheat Sheets for Hard Problems An Introduction to Parameterized Algorithms
- Paper
Short Cycles make W-hard problems hard: FPT algorithms for W-hard Problems in Graphs with no short Cycles
Venkatesh Raman, Saket Saurabh
Dominating Set and variants become FPT without short cycles, but stay W[2]-hard on bipartite and split graphs.
In Hardness of r-Dominating Set on Graphs of Diameter (r+1) Parameterized Algorithms for Variants of Dominating Set
- Paper
Spartan Bipartite Graphs Are Essentially Elementary, which I wrote or worked on
Neeldhara Misra, Saraswati Girish Nanoti
Which bipartite graphs can be guarded with no more guards than a minimum vertex cover.
In Games of Pursuit and Evasion Eternal Versions of Vertex Cover and Dominating Set
- Video
Stable Marriage Problem - Numberphile
Numberphile
An eight-minute, very watchable introduction to the problem and the proposal algorithm.
In On Stable Matchings Manipulation with(out) Money in Matching Markets
- Video
The Cops and Robbers Theorem | Infinite Series
Kelsey Houston-Edwards, PBS Infinite Series
A ten-minute visual introduction to cop-win graphs and why some graphs need more cops.
- Reference
The Fold-and-Cut Problem (Erik Demaine)
Erik Demaine
Erik Demaine's hub for the problem: history, the theorem, papers, and printable shapes to try.
In Recreational Math and Science: In the Classrooms and Beyond Geometric Puzzles: Fold and Cut
- Game
The Game of Sim (playable)
Embedded in Neeldhara's slides
Two players colour lines between six dots; whoever completes a triangle in their own colour loses.
- Essay
The illustrated guide to a Ph.D.
Matt Might
What a PhD adds to the circle of human knowledge, in pictures.
In Being a Successful Grad Student Career Opportunities for Women in Computing
- Video
The impossible chessboard puzzle
3Blue1Brown
The 64-square version of the rigged-bits trick, solved with XOR and a colouring of the hypercube.
- Paper
The Kernelization Complexity of Connected Domination in Graphs with (no) Small Cycles, which I wrote or worked on
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh
In Connected Dominating Set and Short Cycles Parameterized Algorithms for Variants of Dominating Set
- Article
The Prize in Economic Sciences 2012: Popular information
Royal Swedish Academy of Sciences (NobelPrize.org)
Popular account of the prize to Roth and Shapley: stable allocations in theory and market design in practice.
In On Stable Matchings Manipulation with(out) Money in Matching Markets
- Article
The United States and India: How Does Women’s Participation in Computing Differ?
NCWIT
Two qualitative studies on why women's share of computing degrees rose in India while it fell in the US.
In Gender Disparities in Programming Competence in India Career Opportunities for Women in Computing
- Survey
Tournaments in Computational Social Choice: Recent Developments
Warut Suksompong
A short IJCAI survey of tournament solutions and single-elimination tournaments.
In An Introduction to Tournaments How Many Matches Does It Take to Find a Champion?
- Paper
Two Dots is NP-complete, which I wrote or worked on
Neeldhara Misra
The open-access paper with the full reduction.
- Essay
You and Your Research (transcript)
Richard Hamming
The classic 1986 Bell Labs talk on why some researchers do great work, transcribed in full.
In Being a Successful Grad Student Early Career Researcher Presentation
- Video
33 Miniatures Reading Group (recorded sessions), which I wrote or worked on
Neeldhara Misra
My 2023 reading group working through Matoušek's book one miniature at a time, in nearly thirty recorded sessions.
- Course
6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2014)
Erik Demaine (MIT)
A full course, with lecture videos, on proving games and puzzles hard; the toolkit behind results like this one.
- Video
A Constant-Factor Approximate Kernelization for Planar Vertex Deletion (STOC 2022 talk)
Bart M. P. Jansen and Michał Włodarczyk
Recent progress on the open direction of dropping planarity, for the case of planarization.
- Paper
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
Haris Aziz, Simon Mackenzie
The 2016 breakthrough mentioned in the talk: a bounded envy-free protocol for any number of people.
- Video
A New Kernel for Feedback Vertex Set (WorKer 2019)
Yoichi Iwata
A later talk at the kernelization workshop series on newer FVS kernels.
- Paper
A Parameterized Perspective on Attacking and Defending Elections, which I wrote or worked on
Kishen N. Gowda, Neeldhara Misra, Vraj Patel
In A Parameterized Perspective on Protecting and Attacking Elections
- Paper
A Parameterized Perspective on Protecting Elections, which I wrote or worked on
Palash Dey, Neeldhara Misra, Swaprava Nath, Garima Shakya
In A Parameterized Perspective on Protecting and Attacking Elections
- Preprint
A short proof of the first selection lemma and weak 1/r-nets for moving points
Alexandre Rok, Shakhar Smorodinsky
A short, readable proof of the classical first selection lemma for simplices.
- Video
A Simple Randomized FPT Algorithm for FVS (NPTEL Parameterized Algorithms, mod04lec16), which I wrote or worked on
NPTEL course by Neeldhara Misra and Saket Saurabh
Lecture on the random-edge algorithm for Feedback Vertex Set that the talk starts from.
- Survey
A survey of parameterized algorithms and the complexity of edge modification
Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach
Comprehensive later survey of edge modification problems.
- Video
A world from a sheet of paper - Tadashi Tokieda
Tadashi Tokieda, Oxford Mathematics
A public lecture full of surprising paper toys and the mathematics inside them.
In Recreational Math and Science: In the Classrooms and Beyond
- Code
abcvoting
Martin Lackner and contributors
Python library implementing approval-based committee rules; handy for experiments.
- Reference
Academia Stack Exchange
Stack Exchange community
Questions and answers on every stage of an academic career; on the 2013 reading list.
- Reference
ACM-W India
ACM India
Mentoring programmes for women in computing in India, including the annual Grad Cohort workshop.
- Lecture notes
ADFOCS 2013 lecture material: Parameterized Algorithms using Matroids
Saket Saurabh (ADFOCS 2013)
Slides and exercise sheets from the ADFOCS 2013 course of the same name: matroid basics, representative sets, advanced applications.
- Preprint
Algorithmic and Hardness Results for the Colorful Components Problems
Anna Adamaszek, Alexandru Popa
Classical complexity and approximability of three colorful-components objectives.
- Course
Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT 6.890)
Erik Demaine (MIT OpenCourseWare)
Full video course on proving games and puzzles NP-hard and PSPACE-hard.
- Book
Algorithms
Jeff Erickson
A free, rigorous textbook for turning puzzle-solving instincts into algorithm design.
- Preprint
An algebraic proof of the Erdős–Ko–Rado theorem for intersecting families of perfect matchings
Chris Godsil, Karen Meagher
An algebraic proof for perfect matchings (r = n), the case the talk's theorem leaves out.
- Paper
An Erdős–Ko–Rado theorem for matchings in the complete graph, which I wrote or worked on
Vikram Kamat, Neeldhara Misra
The paper behind the talk: a short, self-contained proof via Baranyai partitions and a Katona-style count.
- Video
An Introduction to Cake-Cutting (ACM Summer School on Algorithmic Game Theory 2019)
Siddharth Barman
Summer-school lecture introducing cake cutting, a natural next step after this talk.
- Preprint
An Optimal Algorithm for Finding Champions in Tournament Graphs
Lorenzo Beretta, Franco Maria Nardini, Roberto Trani, Rossano Venturini
Related recent work: finding the Copeland winner of a round-robin while playing few matches.
- Tool
Anatomy: a skill for Claude Code
Ryan (wheresryan.sh)
Turns a one-line prompt into an interactive isometric machine; the talk's example of AI-built explorables.
- Tool
Apache DataSketches
Apache Software Foundation
Open-source library of production streaming sketches (HLL, KLL quantiles, frequent items), mentioned in the talk.
- Preprint
Approximating Maximum Edge 2-Coloring by Normalizing Graphs
Tobias Mömke, Alexandru Popa, Aida Roshany-Tabrizi, Michael Ruderer, Roland Vincze
Recent approximation results: ratio 1.625 for graphs with a perfect matching, and 1.5 for claw-free or subcubic graphs.
- Paper
Backdoors into Heterogeneous Classes of SAT and CSP, which I wrote or worked on
Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, Stanislav Živný
Backdoors whose assignments may land in different tractable classes.
- Survey
Backdoors to Satisfaction
Serge Gaspers, Stefan Szeider
Readable survey of backdoor sets for SAT from the parameterized point of view.
- Video
Backdoors to Typical Case Complexity (Beyond Worst Case Analysis workshop, 2011)
Ryan Williams
One of the originators of backdoors explains how they may account for the success of SAT solvers.
- Reference
Baranyai's theorem
Wikipedia
Its r = 2 case, splitting the edges of K2n into perfect matchings, is the 'Baranyai partition' the proof builds its cycles from.
- Interactive
Bartosz Ciechanowski
Bartosz Ciechanowski
Long-form interactive articles on how everyday things work.
- Survey
Beyond the Worst-Case Analysis of Algorithms (Introduction)
Tim Roughgarden
Introduction to the book that surveys alternatives to worst-case analysis, the 'beyond' of the talk's title.
- Paper
Bidimensionality and Kernels
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos
Linear kernels for many bidimensional problems on graphs excluding a fixed minor, via protrusion-style reductions.
- Preprint
Branch-and-cut algorithms for colorful components problems
Claudia Archetti, Martina Cerulli, Carmine Sorgente
Exact integer-programming methods for these problems, with computational experiments.
- Paper
Bribery and Control in Stable Marriage
Niclas Boehmer, Robert Bredereck, Klaus Heeger, Rolf Niedermeier
Closely related study of bribery and control in stable marriage, with parameterized results.
- Lecture notes
Cake Cutting (Harvard CS 1360, Lecture 10 notes)
Ariel Procaccia (scribes Rhea Acharya, Jakob de Raaij)
Clear lecture notes on cake-cutting algorithms and their complexity.
- Reference
Cantor set
Wikipedia
Remove middle thirds forever: a set with no length that is still as large as the real line.
In Recreational Math and Science: In the Classrooms and Beyond
- Paper
Chess Is Hard Even for a Single Player, which I wrote or worked on
N. R. Aravind, Neeldhara Misra, Harshil Mittal
The paper behind the Solo Chess segment: the generalized puzzle is NP-complete.
- Video
Chromatic Coding for Feedback Arc Set on Tournaments (NPTEL Parameterized Algorithms, Week 4), which I wrote or worked on
NPTEL Parameterized Algorithms course (Neeldhara Misra and Saket Saurabh)
A 46-minute lecture on the same material: the FAST kernel and chromatic coding.
In Random Explorations in Algorithms for Feedback Set Problems on Tournaments
- Video
Color Coding for Longest Path (NPTEL Parameterized Algorithms, Week 4), which I wrote or worked on
NPTEL Parameterized Algorithms course (Neeldhara Misra and Saket Saurabh)
The randomized technique behind the talk's kO(k) algorithm for MEC.
- Talk
Color Coding: Variations and Applications (AofA 2010 slides)
Noga Alon
Slides by a co-inventor of chromatic coding, placing FAST within the color-coding family.
In Random Explorations in Algorithms for Feedback Set Problems on Tournaments
- Paper
Combination Can Be Hard: Approximability of the Unique Coverage Problem
Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour
The approximation side of Unique Coverage: maximize the number of elements covered exactly once.
- Tool
Combinatorial Game Suite (CGSuite)
Aaron Siegel and contributors
Free software for exploring and computing values of combinatorial games such as Hackenbush and Domineering.
- Lecture notes
Combinatorial Games, Theory and Applications
Brit C. A. Milvang-Jensen
A thesis-length introduction to Nim, Domineering, Sprague–Grundy and games as numbers.
- Reference
Complexity of Games (CoG) compendium
Complexity of Games project
Open, community-maintained index of known hardness results for games and puzzles.
- Paper
Computational Boundaries for Escaping Rectangles (ESA 2026)
Akanksha Agrawal, Pradeesha Ashok, Matthias Bentert, Satyabrata Jana, Abhishek Sahu, Saket Saurabh, Kushal Singanporia
Recent work settling several open complexity questions about Rectangle Escape and its restricted-direction variants.
- Video
Computational Social Choice (lecture series)
Felix Brandt
A full recorded course from TU Munich, from voting rules and axioms to strategic manipulation; a free book draft accompanies it.
- Video
Computational Social Choice Lecture 8 (Top Cycle)
Felix Brandt
Course lecture whose segments from 8:52 cover 'The Many Faces of Kemeny's Rule' and 'Computing Kemeny Rankings'.
- Article
Computer Scientists Invent an Efficient New Way to Count
Steve Nadis (Quanta Magazine)
Popular account of the CVM algorithm, explained by counting the distinct words in Hamlet with a whiteboard and coin flips.
- Reference
COMSOC Video Seminar
COMSOC Video Seminar organisers
Seminar home page; its archive lists the 22 May 2020 rump session with all ten speakers and the video.
- Reference
Connected dominating set (Wikipedia)
Wikipedia
Definitions, complementarity with max-leaf spanning trees, and applications.
- Reference
Cop-win graph
Wikipedia
Dismantlable graphs and why exactly these are the graphs where one cop always wins.
- Tool
Creating a Website (Quarto guide)
Quarto (Posit)
Official walkthrough for turning a folder of Markdown files into a website.
- Course
CS Research 101 (NPTEL lecture series), which I wrote or worked on
Neeldhara Misra and Shashank Srikant
A five-part live lecture series I co-ran on why and how to do CS research, for students who want more depth.
- Course
CS607: Combinatorics with Applications in Computer Science (2024), which I wrote or worked on
Neeldhara Misra
My IITGN course that leans on linear algebra methods: Oddtown and Eventown, intersecting families, two-distance sets, equiangular lines and more.
- Reference
Data Reduction and Problem Kernels (Dagstuhl Seminar 12241 report)
Michael R. Fellows, Jiong Guo, Dániel Marx, Saket Saurabh (eds.)
Report of the seminar where this talk was given, with abstracts of companion talks on Planar F-Deletion.
- Lecture notes
Data Stream Algorithms: Lecture Notes
Amit Chakrabarti
Free, regularly updated book-length notes: Misra–Gries, distinct elements, approximate counting, frequency moments and sketches.
- Article
David's de Bruijn sequence card trick
Christian Lawson-Perfect, The Aperiodical
A video of the de Bruijn card trick plus a full explanation; the trick comes from Diaconis and Graham's Magical Mathematics.
- Video
de Bruijn Card Trick
singingbanana (James Grime)
A short demonstration and explanation of a mind-reading card trick powered by a de Bruijn sequence.
In Two Tricks
- Paper
Deleting to Structured Trees, which I wrote or worked on
Pratyush Dayal, Neeldhara Misra
The full version, with both hardness reductions and the branching algorithm.
- Paper
Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets, which I wrote or worked on
Prachi Goyal, Neeldhara Misra, Fahad Panolan, Meirav Zehavi
- Talk
Distinct Elements in Streams and the Klee's Measure Problem
Sourav Chakraborty (CSA, IISc seminar)
One of the CVM authors explains the algorithm and where it came from.
- Paper
Distinct Elements in Streams: An Algorithm for the (Text) Book
Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel
The sampling-based distinct-elements algorithm at the heart of the talk, with a proof aimed at undergraduates.
- Paper
Diversity in Kemeny Rank Aggregation: A Parameterized Approach
Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf
The IJCAI 2021 paper most of the talk is based on.
- Book
Doing It in Public
Nicole van der Hoeven
A book, written in public, on learning in public, cited for documenting learning journeys.
- Paper
Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity
Sylvain Bouveret, Jérôme Lang
Classic results on the complexity of finding allocations that are both envy-free and efficient (JAIR 2008).
- Paper
Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
Fast algorithms for computing representative families, and their use for single-exponential algorithms.
- Paper
Eliciting Single-Peaked Preferences Using Comparison Queries
Vincent Conitzer
The starting point: eliciting single-peaked preferences on a line with few comparison queries (JAIR 2009).
- Video
Engineering Motif Search for Large Graphs (Simons Institute, 2015)
Petteri Kaski
How motif search algorithms are engineered to run on large real graphs.
- Paper
Envy-Free Allocations Respecting Social Networks
Robert Bredereck, Andrzej Kaczmarczyk, Rolf Niedermeier
Envy-freeness on directed social networks (AAMAS 2018, Artificial Intelligence 2022); key prior work in the talk.
In On Fair Division with Binary Valuations Respecting Social Networks
- Reference
Erdős–Ko–Rado theorem
Wikipedia
The theorem being generalized, with a clear account of Katona's cycle proof.
- Reference
Eternal dominating set
Wikipedia
Overview of eternal domination and its variants, including eternal vertex cover and grid results.
- Reference
Exact cover
Wikipedia
The classic problem, with examples from puzzles such as Sudoku and pentomino tilings.
- Paper
Exact Multi-Covering Problems with Geometric Sets, which I wrote or worked on
Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, Saket Saurabh
Journal version, extended from exact cover to covering every element an exact number of times.
- Interactive
Explorable Explanations (explorabl.es)
A community of artists, coders and educators
A hub for learning through play: explorables by subject, plus how to make your own.
- Reference
Fair cake-cutting
Wikipedia
A good map of fairness notions and procedures, from cut-and-choose onwards.
- Reference
Fair division
Wikipedia
Broad overview of the field and its many settings.
- Paper
Fair Division via Social Comparison
Rediet Abebe, Jon Kleinberg, David Parkes
Introduced fairness defined through comparisons along a social network (AAMAS 2017).
In On Fair Division with Binary Valuations Respecting Social Networks
- Talk
Fair Division with Minimal Sharing (COMSOC Video Seminar rump session), which I wrote or worked on
Neeldhara Misra
My five-minute rump-session talk where this result was first previewed.
- Reference
Fair item allocation
Wikipedia
Well-maintained overview of fairness notions and algorithms for indivisible items.
- Paper
Fast FAST (ICALP 2009)
Noga Alon, Daniel Lokshtanov, Saket Saurabh
Introduces chromatic coding and the subexponential algorithm for feedback arc set in tournaments that the talk presents.
In Random Explorations in Algorithms for Feedback Set Problems on Tournaments
- Paper
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
Marek Karpinski, Warren Schudy
Subexponential parameterized algorithms for Kemeny aggregation and feedback arc set in tournaments, cited in the talk.
- Paper
Faster Deterministic Algorithms for r-Dimensional Matching Using Representative Sets, which I wrote or worked on
Prachi Goyal, Neeldhara Misra, Fahad Panolan
My open-access paper combining dynamic programming with representative families for faster deterministic matching algorithms.
- Preprint
Faster FAST (Feedback Arc Set in Tournaments)
Uriel Feige
Removes the log factor: an nO(1) 2O(√k) algorithm.
In Random Explorations in Algorithms for Feedback Set Problems on Tournaments
- Reference
Feedback arc set
Wikipedia
Good article on the problem, including ranking from tournaments and parameterized algorithms.
In Random Explorations in Algorithms for Feedback Set Problems on Tournaments
- Reference
Feedback vertex set
Wikipedia
The classic problem this talk varies.
- Preprint
Finding and counting vertex-colored subtrees
Sylvain Guillemot, Florian Sikora
The O*(2k) algorithm for colorful motifs cited in the talk.
- Preprint
Finding small separators in linear time via treewidth reduction
Dániel Marx, Barry O'Sullivan, Igor Razgon
The FPT results for connected and independent separators that this work generalizes.
- Video
Fixed-Parameter Algorithms (MIT 6.046J, Lecture 18)
Erik Demaine
Clear classroom introduction to FPT algorithms and kernels, using Vertex Cover.
- Paper
Folding and Cutting Paper
Erik D. Demaine, Martin L. Demaine, Anna Lubiw
The paper behind the straight-skeleton method for finding the folds.
- Reference
Fully proportional representation
Wikipedia
Overview of the Chamberlin–Courant and Monroe rules and their complexity.
- Book
Games, Puzzles, and Computation
Robert A. Hearn, Erik D. Demaine
The book on the computational complexity of games and puzzles, built around constraint logic.
- Code
GCJ in Picat
picat-lang.org (includes solutions by Dymchenko and Mykhailova)
Google Code Jam problems solved in the Picat language: contest problems as a showcase for language features.
- Paper
Gender and Programming Contests: Mitigating Exclusionary Practices
Maryanne L. Fisher and Anthony Cox (2006)
Open-access study cited in the talk on why programming contests can exclude women.
- Tool
GeoGebra
GeoGebra
Free interactive geometry, graphing and calculus apps, with ready-made classroom activities.
- Course
Geometric Folding Algorithms (MIT 6.849, Fall 2012)
Erik Demaine (MIT OpenCourseWare)
Free lecture videos and notes, including the 'fold and one cut' lectures.
- Book
Geometric Folding Algorithms: Linkages, Origami, Polyhedra
Erik D. Demaine, Joseph O'Rourke
The book cited in the talk; covers fold-and-cut alongside linkages, origami and polyhedra.
- Course
Getting Started with Competitive Programming (NPTEL), which I wrote or worked on
Neeldhara Misra
My free online course on contest problem solving, with lecture videos and worked problems.
- Tool
GitHub Pages documentation
GitHub
Free hosting for a static site straight from a repository.
- Paper
Graph Modification Problems: A Modern Perspective, which I wrote or worked on
Fedor V. Fomin, Saket Saurabh, Neeldhara Misra
My survey with Fedor Fomin and Saket Saurabh, with nearly the same title as the talk.
- Video
GS: Cheating Strategies for Men (ACM Summer School on Algorithmic Game Theory 2019)
Prajakta Nimbhorkar
How individual agents can manipulate Gale–Shapley, the classic counterpart to manipulation by a central agency.
- Video
HACKENBUSH: a window to a new world of math
Owen Maitzen
An animated hour on Hackenbush and how its positions behave like numbers.
- Video
High-Degree Branching for FVS (NPTEL Parameterized Algorithms, Week 2), which I wrote or worked on
NPTEL Parameterized Algorithms course (Neeldhara Misra and Saket Saurabh)
How branching gives an FPT algorithm for Feedback Vertex Set, background for the talk’s FPT result.
- Article
History of the Fold and Cut Problem
wild.maths.org
From Kan Chu Sen's 1721 puzzle to Betsy Ross's star and Houdini's Paper Magic.
- Preprint
Hitting and Harvesting Pumpkins
Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, Stéphan Thomassé
Related work on hitting and packing θc minors (pumpkins), including approximation and FPT results.
- Paper
Hitting and Piercing Rectangles Induced by a Point Set, which I wrote or worked on
Ninad Rajgopal, Pradeesha Ashok, Sathish Govindarajan, Abhijit Khopkar, Neeldhara Misra
The paper behind the talk.
- Paper
How Hard Is It for a Party to Nominate an Election Winner?
Piotr Faliszewski, Laurent Gourvès, Jérôme Lang, Julien Lesca, Jérôme Monnot
IJCAI 2016 paper that introduced the party nomination problems for plurality elections.
- Video
How to Speak
Patrick Winston (MIT OpenCourseWare)
The annual MIT lecture: an hour of practical heuristics for talks, slides and job talks.
- Video
How to Write a Great Research Paper
Simon Peyton Jones
Seven concrete suggestions for writing papers, starting before the research is done.
- Video
Important Separators - I (Parameterized Complexity Workshop, IIT Gandhinagar)
Dániel Marx
Lecture on the separator techniques that power many FPT algorithms for cut problems.
- Paper
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
Hao Huang
A celebrated 2019 paper whose core argument fits in about two pages: a cleverly signed matrix and eigenvalue interlacing settle a decades-old question.
- Paper
Infeasibility of Instance Compression and Succinct PCPs for NP (ECCC TR07-096)
Lance Fortnow, Rahul Santhanam
The complexity result that makes distillation imply a collapse of the polynomial hierarchy.
- Reference
Iterative compression
Wikipedia
Short overview of the technique, its origin in Reed, Smith and Vetta's Odd Cycle Transversal algorithm, and later uses.
- Video
Iterative Compression I: Setting Up the Method, which I wrote or worked on
Neeldhara Misra and Saket Saurabh (NPTEL)
First of four lectures in my NPTEL course, continuing to Vertex Cover, Feedback Vertex Set, 3-Hitting Set and Odd Cycle Transversal.
- Reference
Kemeny method
Wikipedia
Definition, properties and history of the rule.
- Video
Kernel Lower Bounds (Parameterized Complexity Workshop, IIT Gandhinagar)
Petr Golovach
A recorded lecture on compositions and kernel lower bounds.
- Video
Kernel lower bounds I (parameterized complexity school lecture)
Michał Pilipczuk
Lecture on OR- and AND-compositions and ruling out polynomial kernels.
- Preprint
Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves
Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, Yngve Villanger
The 'many polynomial kernels' result that the talk discusses as a way around the barrier.
- Video
Kernelization 3: Sunflower Lemma and Dominating Set in Ki,j-free graphs (IMSc lecture)
IMSc Chennai lecture series (matsciencechannel)
Lecture on kernelizing Dominating Set on graphs that exclude a fixed biclique Ki,j.
- Preprint
Kernelization Lower Bounds By Cross-Composition
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
The later, more flexible framework that most lower-bound proofs now use.
- Video
Kernelization: Nemhauser-Trotter and Expansion Lemma (NPTEL Parameterized Algorithms, mod01lec06), which I wrote or worked on
NPTEL course by Neeldhara Misra and Saket Saurabh
Lecture introducing the expansion lemma and using it in a kernel.
- Preprint
Kernels for Feedback Arc Set In Tournaments
Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, Stéphan Thomassé
Improves the talk's quadratic kernel to a linear vertex kernel.
In Random Explorations in Algorithms for Feedback Set Problems on Tournaments
- Lecture notes
Lecture 10: Extremal set theory, part 2 (Erdős–Ko–Rado and Katona's proof)
Hong Liu
A written version of Katona's double-counting proof, short enough to read before the talk.
- Book
Lectures on Discrete Geometry
Jiří Matoušek
The standard text; its chapter on geometric selection theorems covers the first and second selection lemmas.
- Preprint
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
Bart M. P. Jansen, Michał Włodarczyk
Later progress on Planarization, which the talk lists as wide open for kernels.
- Survey
Lower bounds based on the Exponential Time Hypothesis
Daniel Lokshtanov, Dániel Marx, Saket Saurabh
Readable survey of lower bounds from ETH and SETH in exact and parameterized algorithms.
- Paper
m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs, which I wrote or worked on
Tiziana Calamoneri, Federico Corò, Neeldhara Misra, Saraswati Girish Nanoti, Giacomo Paesani
Hardness results and tight bounds on square, octagonal, hexagonal and triangular grids, the second half of the talk.
- Video
Magical Mathematics Reading Group, which I wrote or worked on
Neeldhara Misra
My recorded reading group on Diaconis and Graham's book, with several sessions on de Bruijn-based tricks.
In Two Tricks
- Book
Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks
Persi Diaconis, Ron Graham
The mathematics behind card tricks of this kind, de Bruijn sequences included, by a mathematician-magician duo.
In Two Tricks
- Paper
Manipulation With(out) Money in Matching Market
Sushmita Gupta, Pallavi Jain
The ADT 2024 paper this talk presents.
- Video
Math Encounters - Fair Division: How to Cut Cakes (and other things) Fairly
Francis Su, National Museum of Mathematics
A public lecture by Francis Su on envy-free ways to cut cakes and share other things fairly.
- Video
Matroids: Representative Sets, which I wrote or worked on
Neeldhara Misra and Saket Saurabh (NPTEL)
First of four lectures on representative sets in my NPTEL course, continuing to their computation and to paths and kernels.
- Tool
Mentimeter
Mentimeter
The live polling tool used for audience interaction in the talk.
- Video
Method of Equal Shares explained in 5 minutes
Piotr Skowron
A quick explainer by one of the method's inventors.
- Reference
Method of Equal Shares for Participatory Budgeting
Dominik Peters, Piotr Skowron
The website the talk borrows from: explanations, benefits and elections that used the method.
- Interactive
Method of Equal Shares: Online Computation Tool
Dominik Peters, Piotr Skowron (equalshares.net)
Compute Method of Equal Shares outcomes online for your own instances.
- Article
More math for six-year-olds: Win at Nim!
Joel David Hamkins
A lovely account of teaching Nim strategy to young children, step by step.
- Survey
Multivariate stable polynomials: theory and applications
David G. Wagner
Survey of the theory of multivariate stable polynomials and its uses in combinatorics, probability and matrix theory.
- Reference
Multiwinner voting
Wikipedia
Overview of committee elections and the main rules.
- Survey
Multiwinner Voting: A New Challenge for Social Choice Theory (Trends in Computational Social Choice, ch. 2)
Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon
Free book chapter surveying multiwinner rules, their axioms and their complexity.
- Code
ncase/trust
Nicky Case
The source code of The Evolution of Trust, for anyone who wants to remix or extend it.
- Preprint
Necessary President in Elections with Parties
Katarína Cechlárová, Ildikó Schlotter
Recent work focused on the Necessary President problem.
- Code
neeldhara/quartosite, which I wrote or worked on
Neeldhara Misra
The full Quarto source of neeldhara.com, to borrow structure, listings and styling from.
- Talk
New Developments in Exact Algorithms and Lower Bounds (pre-FSTTCS 2014 workshop)
Venkatesh Raman and Saket Saurabh (organizers)
The workshop page, with slides of this talk and of companion talks on ETH, SETH, backdoors and kernel lower bounds.
- Reference
New Methods in Parameterized Algorithms and Complexity (PhD thesis), Chapter 6: Chromatic Coding
Daniel Lokshtanov
A careful write-up of chromatic coding for tournament feedback arc set, including kernelization and the coloring analysis.
In Random Explorations in Algorithms for Feedback Set Problems on Tournaments
- Essay
No “yes.” Either “HELL YEAH!” or “no.”
Derek Sivers
The short essay behind the deck's quote on saying no (Act III).
- Paper
On Detecting Nearly Structured Preference Profiles
Edith Elkind, Martin Lackner
AAAI 2014 paper on measuring and detecting profiles that are close to single-peaked or single-crossing.
In Efficient Algorithms for Hard Problems on Structured Electorates
- Preprint
On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide
Jasine Babu, L. Sunil Chandran, Mathew Francis, Veena Prabhakaran, Deepak Rajendraprasad, J. Nandini Warrier
Earlier work on the graphs where the two numbers agree, the question the talk takes up.
- Article
On Leonid Gurvits's proof for permanents
Monique Laurent, Alexander Schrijver
A concise, self-contained exposition of Gurvits's proof; the best first read.
- Paper
On Parameterized Independent Feedback Vertex Set, which I wrote or worked on
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh
- Paper
On Parameterized Independent Feedback Vertex Set, which I wrote or worked on
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh
- Paper
On Structural Parameterizations of Firefighting, which I wrote or worked on
Bireswar Das, Murali Krishna Enduri, Neeldhara Misra, I. Vinod Reddy
Which structural parameters make classic firefighting tractable, and which do not.
- Paper
On Structural Parameterizations of Graph Motif and Chromatic Number, which I wrote or worked on
Bireswar Das, Murali Krishna Enduri, Neeldhara Misra, I. Vinod Reddy
- Paper
On the Computation of Fully Proportional Representation
Nadja Betzler, Arkadii Slinko, Johannes Uhlmann
JAIR 2013 paper with the single-peaked algorithm for Chamberlin–Courant that the talk builds on.
- Paper
On the d-Runaway Rectangle Escape Problem (CCCG 2014), which I wrote or worked on
Aniket Basu Roy, Sathish Govindarajan, Neeldhara Misra, Shreyas Shetty
The paper behind the talk, free in the CCCG proceedings.
- Paper
On the Parameterized Complexity of Colorful Components and Related Problems, which I wrote or worked on
Neeldhara Misra
The paper behind the talk.
- Paper
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties, which I wrote or worked on
Pinar Heggernes, Pim van 't Hof, Dániel Marx, Neeldhara Misra, Yngve Villanger
- Paper
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties, which I wrote or worked on
Pinar Heggernes, Pim van 't Hof, Dániel Marx, Neeldhara Misra, Yngve Villanger
Journal version with all the results from the talk.
- Paper
On the Parameterized Complexity of Minimax Approval Voting (AAMAS 2015 PDF), which I wrote or worked on
Neeldhara Misra, Arshed Nabeel, Harman Singh
My earlier paper on multiwinner voting; the PDF is free.
- Paper
On the Parameterized Complexity of Party Nominations, which I wrote or worked on
Neeldhara Misra
- Paper
On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem, which I wrote or worked on
Prachi Goyal, Vikram Kamat, Neeldhara Misra
The paper behind the talk, with the FPT algorithm, kernels and hardness for restricted classes.
- Paper
On the Rectangle Escape Problem (CCCG 2013)
Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Sadra Yazdanbod, Hamid Zarrabi-Zadeh
The density-minimizing version and its PCB bus-routing motivation, which the talk builds on.
- Paper
On the Role of Half-Catalan Numbers and Pathwidth in Hyperbranched Polymers Synthesized by ABm Step Polymerization, which I wrote or worked on
Pratyush Dayal, Neeldhara Misra, Surbhi Khewle, Ravi Anand Singh
Where tree structures meet polymer chemistry, one of the motivations named in the talk.
- Video
Once you understand game theory, you understand the world.
Veritasium
A video tour of the repeated prisoner's dilemma and Axelrod's tournaments, the same story as the talk.
- Article
Oral Presentation Advice
Mark D. Hill
Compact advice on conference talks, with a generic talk outline and notes on job talks.
- Tool
PACE 2016: Treewidth and Feedback Vertex Set tracks
PACE challenge
Implementation challenge with benchmark instances and solvers for Feedback Vertex Set and treewidth.
- Tool
PACE Challenge (Parameterized Algorithms and Computational Experiments)
PACE organisers
Annual implementation challenge that puts parameterized algorithms to work on real instances.
- Interactive
Parable of the Polygons
Vi Hart and Nicky Case
A playable post on how small individual biases add up to segregation.
- Survey
Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges
Robert Bredereck, Jiehua Chen, Piotr Faliszewski, Jiong Guo, Rolf Niedermeier, Gerhard J. Woeginger
Research agenda for parameterized social choice, with control problems among the challenges.
In A Parameterized Perspective on Protecting and Attacking Elections
- Paper
Parameterized Algorithms and Hardness for the Maximum Edge q-Coloring Problem (FSTTCS 2024)
Rogers Mathew, Fahad Panolan, Seshikanth
Answers the talk's open question: parameterized above the maximum matching size, the problem is W[1]-hard.
- Paper
Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs, which I wrote or worked on
Neeldhara Misra, Fahad Panolan, Ashutosh Rai, Venkatesh Raman, Saket Saurabh
- Paper
Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs, which I wrote or worked on
Neeldhara Misra, Fahad Panolan, Ashutosh Rai, Venkatesh Raman, Saket Saurabh
Journal version of the paper behind the talk, with full proofs.
- Paper
Parameterized Aspects of Distinct Kemeny Rank Aggregation, which I wrote or worked on
Koustav De, Harshil Mittal, Palash Dey, Neeldhara Misra
- Preprint
Parameterized Complexity and Approximation Issues for the Colorful Components Problems
Riccardo Dondi, Florian Sikora
The earlier parameterized and approximation results for both problems that the talk improves on.
- Paper
Parameterized Complexity of Candidate Nomination for Elections Based on Positional Scoring Rules
Ildikó Schlotter, Katarína Cechlárová, Diana Trellová
Open-access follow-up (JAAMAS 2024) extending the parameterized analysis to positional scoring rules.
- Preprint
Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, Venkatesh Raman
Algorithms and lower bounds for many dominating set variants on graphs close to cluster or split graphs.
- Paper
Parameterized Complexity of Envy-Free Resource Allocation in Social Networks
Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
AAAI 2020 parameterized study of local envy-freeness, the closest prior work on parameters.
In On Fair Division with Binary Valuations Respecting Social Networks
- Course
Parameterized Complexity Summer School 2017 (programme and slides)
TU Wien (ALGO 2017)
Programme of the summer school with slides from every lecture, including advanced kernels and kernel lower bounds.
- Paper
Parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers, which I wrote or worked on
Palash Dey, Neeldhara Misra, Y. Narahari
- Article
Participatory Budgeting in Pune, India
Participedia
Background on the Pune participatory budgeting process mentioned in the talk.
- Video
Partitioning to Decrease Diameter - Understanding a Beautiful Proof
Jacob Von Holly
Accessible video on how the Frankl–Wilson theorem, a linear algebra bound on set systems, disproves Borsuk's conjecture.
- Paper
Paths, Trees, and Flowers
Jack Edmonds (1965)
The matching paper that argued for polynomial time as the mark of a 'good' algorithm.
- Reference
Perfect graph
Wikipedia
Good article on the graph class the talk works in, including the strong perfect graph theorem.
- Video
Perfect Graphs (Numberphile)
Numberphile, with Maria Chudnovsky
A friendly introduction to perfect graphs from one of the authors of the strong perfect graph theorem.
- Survey
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
Erik D. Demaine, Robert A. Hearn
A survey of what is known about the complexity of games and puzzles, one- and two-player.
- Survey
Preference Restrictions in Computational Social Choice: A Survey
Edith Elkind, Martin Lackner, Dominik Peters
Up-to-date survey of preference restrictions: recognition, elicitation and algorithmic uses.
In Efficient Algorithms for Hard Problems on Structured Electorates
- Tool
PrefLib: A Library for Preferences
Nicholas Mattei and Simon Rey (maintainers)
Curated real-world preference data, plus Python tools, for experimenting with voting rules.
- Reference
Prisoner's Dilemma (Stanford Encyclopedia of Philosophy)
Steven Kuhn
A thorough reference on the dilemma, its iterated version and strategies such as tit for tat.
- Video
Prof. Edith Elkind | Computational Social Choice | Day 1 | IIT Gandhinagar
Edith Elkind
A three-hour lecture by a leading researcher in the field, recorded at IIT Gandhinagar.
- Course
Programming for the Puzzled (MIT 6.S095)
Srini Devadas (MIT OpenCourseWare)
A free course that teaches Python through classic puzzles, with videos and code.
- Game
Project Euler
Project Euler
Hundreds of mathematical puzzles meant to be solved with short programs.
- Paper
Proportional Participatory Budgeting with Additive Utilities
Dominik Peters, Grzegorz Pierczyński, Piotr Skowron
The NeurIPS 2021 paper the talk is based on.
- Paper
Protecting Elections by Recounting Ballots
Edith Elkind, Jiarui Gan, Svetlana Obraztsova, Zinovi Rabinovich, Alexandros A. Voudouris
IJCAI 2019 model of ballot tampering and recounts across districts that the IWOCA 2020 paper analyses.
In A Parameterized Perspective on Protecting and Attacking Elections
- Reference
Puzzles from the TGIF Group, which I wrote or worked on
Neeldhara Misra
Puzzles from my Friday puzzle group at IITGN, tagged by theme, with a Discord to join.
- Course
Python for Everybody
Charles Severance
A free, beginner-friendly course and book for moving from blocks to Python.
- Tool
Python Tutor
Philip Guo
Step through Python, Java, C, C++ or JavaScript code and see memory change; handy for teaching programming and data structures.
- Code
pytudes
Peter Norvig
Short Python notebooks that solve puzzles and problems, a model of using code to think.
- Paper
Quadratic Upper Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles, which I wrote or worked on
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, Saket Saurabh
- Tool
Quarto
Posit (open source)
One Markdown source for slides, notes and course websites; the tool behind neeldhara.com.
- Preprint
Query Complexity of Tournament Solutions
Arnab Maiti, Palash Dey
The other source paper: how many match outcomes you must query to find Copeland, Slater, Banks and top-cycle winners (TCS 2024).
- Paper
Rank Aggregation Methods for the Web
Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar
WWW 2001 classic on rank aggregation, source of the NP-hardness for four rankings shown in the talk.
- Course
Reading Group on Combinatorial and Computational Aspects of Games (Summer 2023), which I wrote or worked on
Neeldhara Misra
My reading group page with recorded sessions, a reading list and small playable games.
- Article
Real stable polynomials and the Kadison-Singer problem
Terence Tao
Blog exposition of how real stable polynomials and interlacing helped resolve the Kadison–Singer problem.
- Video
Real Stable Polynomials, Strongly Rayleigh Distributions, and Applications, Part I-A
Shayan Oveis Gharan (Simons Institute)
Boot camp tutorial from the Geometry of Polynomials programme, with applications in algorithms.
- Interactive
Red Blob Games
Amit Patel
Interactive tutorials on algorithms for games, a model of explanation through play.
- Interactive
Redesign the Course: A Playable Teaching Essay, which I wrote or worked on
Neeldhara Misra
Redesign one course file step by step, from learning outcomes to feedback, and watch a student's experience change.
- Paper
Representative sets and irrelevant vertices: New tools for kernelization
Stefan Kratsch, Magnus Wahlström
Uses representative sets from matroid theory to get polynomial kernels, including for Almost 2-SAT.
- Video
Reservoir Sampling and Preference Elicitation (ACM Summer School on Algorithmic Game Theory 2019)
Palash Dey
Summer-school lecture by my co-author on sampling and preference elicitation.
- Paper
Robustness Among Multiwinner Voting Rules
Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Rolf Niedermeier, Piotr Skowron, Nimrod Talmon
Introduces the robustness radius that the SOFSEM 2019 paper studies on restricted domains.
- Paper
Robustness Radius for Chamberlin-Courant on Restricted Domains, which I wrote or worked on
Neeldhara Misra, Chinmay Sonar
- Reference
Selection algorithm
Wikipedia
Finding the k-th best by comparisons, with the history from Lewis Carroll's tennis complaint and Steinhaus.
- Preprint
Selection Lemmas for various geometric objects
Pradeesha Ashok, Ninad Rajgopal, Sathish Govindarajan
A longer treatment of the selection lemma results by three of the coauthors, covering more classes of objects.
- Reference
Single peaked preferences
Wikipedia
Quick reference for the central domain restriction, including single-peakedness on trees.
In Efficient Algorithms for Hard Problems on Structured Electorates
- Game
Solo Chess - Capture All the Pieces on the Board
Chess.com
Play the single-player puzzle: every move captures, and the goal is to leave one piece.
- Paper
Solving connectivity problems parameterized by treewidth in single exponential time
M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. van Rooij, J. O. Wojtaszczyk
The paper that introduced Cut & Count for connectivity problems on graphs of bounded treewidth.
- Paper
Solving d-SAT via Backdoors to Small Treewidth, which I wrote or worked on
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh
- Preprint
Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
Geevarghese Philip, Venkatesh Raman, Somnath Sikdar
Background: polynomial kernels for Dominating Set on graphs excluding a fixed Ki,j, closely related to the girth setting of the talk.
- Reference
Sprague–Grundy theorem
Wikipedia
Why every impartial game is equivalent to a single Nim heap.
- Reference
Stable matching problem
Wikipedia
Good overview of the problem, the algorithm, its properties and its applications.
- Video
Stable Matchings | part I, which I wrote or worked on
Neeldhara Misra (IIT Madras BS, Advanced Algorithms)
First of my three short lectures: blocking pairs, the Gale–Shapley algorithm, and the proof that it works.
- Video
Stable matchings, part II: the Gale–Shapley algorithm, which I wrote or worked on
Neeldhara Misra
My lecture on blocking pairs and the Gale–Shapley algorithm.
- Survey
Strategic Aspects of Stable Matching Markets: A Survey
Hadi Hosseini, Shraddha Pathak
IJCAI 2024 survey of manipulation and strategic behaviour in matching markets.
- Paper
Structural Parameterizations for Eternal Vertex Cover, which I wrote or worked on
Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki
A follow-up: computing the eternal vertex cover number with structural parameters.
- Article
Students Testing Without Coercion
Brown PLT blog
On Examplar, a tool that gets students to write test cases before code; one of the education angles in the talk.
- Video
Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds (Simons Institute, 2015)
Marcin Pilipczuk
Video survey of the subexponential completion algorithms the talk mentions.
- Tool
Tangle: a JavaScript library for reactive documents
Bret Victor
A small library for building documents whose numbers readers can drag and change.
- Video
Teaching Innovations @IITGN: Ft. Prof Neeldhara Misra
IIT Gandhinagar
Eight minutes on my flipped DSA course, taught over YouTube live streams with OBS and Itempool.
- Paper
Tetris is Hard, Even to Approximate
Erik D. Demaine, Susan Hohenberger, David Liben-Nowell
The classic hardness result for Tetris, another game among the talk's projects.
- Survey
The (Computational) Social Choice Take on Indivisible Participatory Budgeting
Simon Rey, Felicia Schmidt, Jan Maly
Survey of the social choice literature on participatory budgeting.
- Article
The /now page movement
Derek Sivers
The idea behind a 'now' page, one of the workshop's content suggestions.
- Video
The almost impossible chessboard puzzle
Stand-up Maths (Matt Parker)
The companion video that poses the puzzle; I use both videos in my CS607 course.
In Two Tricks
- Paper
The CVM Algorithm for Estimating Distinct Elements in Streams
Donald E. Knuth
Knuth's own exposition and analysis of the CVM algorithm, cited in the talk.
- Paper
The Effect of Girth on the Kernelization Complexity of Connected Dominating Set, which I wrote or worked on
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh
Free full text of the paper behind the talk, with the girth trichotomy.
- Reference
The Evolution of Cooperation
Wikipedia
Robert Axelrod's book on the computer tournaments that inspired Nicky Case's explorable.
- Survey
The Firefighter Problem: A survey of results, directions and questions
Stephen Finbow, Gary MacGillivray
The standard survey of the firefighter problem (Australasian Journal of Combinatorics, 2009).
- Book
The Golden Ticket: P, NP, and the Search for the Impossible
Lance Fortnow
Popular book on P versus NP that I recommended to attendees of the 2013 talk.
- Paper
The Graph Motif Problem Parameterized by the Structure of the Input Graph (IPEC 2015)
Édouard Bonnet, Florian Sikora
Later work on which structural parameters make Graph Motif easier.
- Essay
The Humble Programmer (EWD340)
Edsger W. Dijkstra (1972)
Dijkstra's Turing Award lecture on programming as an intellectual discipline.
- Paper
The intrinsic computational difficulty of functions
Alan Cobham (1965)
An early, independent case for polynomial time as the right notion of feasible computation.
- Talk
The Life and times of Edsger Dijkstra
Madhavan Mukund
An hour-long lecture on Dijkstra's life and work.
- Article
The Matching Algorithm (NRMP)
National Resident Matching Program
How the US residency match uses tentative matches and 'bumping', with worked examples.
- Paper
The Parameterized Complexity of Dominating Set and Friends Revisited for Structured Graphs, which I wrote or worked on
Neeldhara Misra, Piyush Rathi
Structural parameterizations of domination, efficient domination and their distance versions.
- Paper
The Parameterized Complexity of Unique Coverage and Its Variants, which I wrote or worked on
Neeldhara Misra, Hannes Moser, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
Earlier work on Unique Coverage for abstract set systems, the baseline the geometric results improve on.
- Reference
The Python Tutorial
Python Software Foundation
The official tutorial, for anyone who wants to start writing their own puzzle solvers.
- Paper
The Runaway Rectangle Escape Problem, which I wrote or worked on
Aniket Basu Roy, Anil Maheshwari, Sathish Govindarajan, Neeldhara Misra, Subhas C. Nandy, Shreyas Shetty
Expanded 26-page version of the CCCG paper.
- Video
The Silent (R)evolution of SAT
Johannes K. Fichte, Daniel Le Berre, Markus Hecher, Stefan Szeider (VCLA)
A three-minute video on why practical SAT solving works so well.
- Book
Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra
Jiří Matoušek
Short, self-contained gems of the linear algebra method; the author's page links a free preliminary version.
- Interactive
To Build a Better Ballot
Nicky Case
Playable explainer comparing voting systems with simulated voters.
- Video
Topics in Combinatorics lecture 2.0: Intersecting families
Timothy Gowers
A lecture on Katona's proof of Erdős–Ko–Rado, the method the talk adapts.
- Book
Topics on Tournaments
John W. Moon
The classic monograph on the graph theory of tournaments, free on Project Gutenberg.
- Reference
Tournament (graph theory)
Wikipedia
Definitions and basic facts: paths and cycles, transitivity, score sequences, and majority relations from voting.
- Video
Tournament Fixing and Superkings, which I wrote or worked on
Neeldhara Misra (ACM Summer School on Algorithmic Game Theory 2019, NPTEL)
My 2019 summer-school lecture on rigging knockout tournaments and the role of kings.
- Lecture notes
Tournaments in Computational Social Choice (IJCAI 2024 Tutorial)
Warut Suksompong
A tutorial on choosing winners from pairwise comparisons, including single-elimination (knockout) tournaments.
- Preprint
Tree Deletion Set has a Polynomial Kernel (but no OPTO(1) approximation)
Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, Ondrej Suchý
A close cousin from the talk's related-work slides: delete vertices so that what remains is a tree.
- Game
Two Dots - Connect the Colors (App Store)
Playdots, Inc.
Play the game itself.
- Paper
Unique Covering Problems with Geometric Sets, which I wrote or worked on
Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, Saket Saurabh
- Paper
UNO Gets Easier for a Single Player, which I wrote or worked on
Palash Dey, Prachi Goyal, Neeldhara Misra
- Paper
Upper and Lower Bounds for Weak Backdoor Set Detection, which I wrote or worked on
Neeldhara Misra, Sebastian Ordyniak, Venkatesh Raman, Stefan Szeider
- Paper
Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all
Leonid Gurvits
The original paper: one inequality for stable homogeneous polynomials that implies van der Waerden-type bounds.
- Reference
Vapnik–Chervonenkis dimension
Wikipedia
Lines and hyperplanes have bounded VC-dimension, a theme in the talk's table of results.
- Paper
Variations on the Tournament Problem
Fabrizio Luccio, Linda Pagli, Nicola Santoro
One of the two papers the talk draws on: finding the top t with k-way races (FUN 2024).
- Reference
Vertex separator (Wikipedia)
Wikipedia
Definitions of s–t separators and minimal separators.
- Article
Visualising Sorting Algorithms
Aldo Cortesi
The essay behind the 'glob of porridge' critique of animations, and its static alternative.
- Interactive
Visualizing quaternions
Grant Sanderson and Ben Eater
An explorable video series where you can grab the objects the narrator is talking about.
- Video
W6_L6.3: Iterative compression, feedback vertex set, which I wrote or worked on
Neeldhara Misra (IIT Madras BS, Advanced Algorithms)
My hour-long lecture applying the method to Feedback Vertex Set, after a warm-up on Vertex Cover in the previous video.
- Reference
Web Content Accessibility Guidelines (WCAG) 2.1
W3C
The standard behind the accessibility checklist in the workshop: alt text, contrast, resizable text.
- Talk
What Computers Can't Do - with Kevin Buzzard
Kevin Buzzard (Royal Institution)
A Royal Institution public lecture on P versus NP, the central open question about the limits of efficient computation.
- Essay
Why I want to be a Professor
Dheeraj Sanghi
The 'why' side, from an Indian computer science professor.
- Essay
Why I'm leaving Harvard
Matt Welsh
The 'why not' side: a tenured professor explains leaving for industry.
- Reference
Women in Tech: The Facts
NCWIT
The data report the talk cites on the gender gap in computing careers.
- Interactive
XOR trick (interactive), which I wrote or worked on
Neeldhara Misra
Toggle 16 bits and compute f, the XOR of the positions of the 1s; try steering it to any value with one flip.
In Two Tricks
- Essay
Y. Dinitz's talk at S. Even's Party (2003)
Yefim Dinitz
First-hand account of algorithms research in the USSR and of how Dinitz's max-flow algorithm reached the West through Shimon Even.
- Video
You and Your Research (1995 lecture)
Richard Hamming
Hamming's classic talk on choosing important problems and working on them; a natural companion to the balancing acts.
- Survey
Zeros of Polynomials and their Applications to Theory: A Primer
Nisheeth K. Vishnoi
A 2013 primer on proving that polynomials have no zeros in a region, opening with the permanent lower bound.