2012–2026
1,457 posts
2026 83
October 2026
- The Exponential Time Refutation
- When is it plausible that a result is optimal?
- Reading Messy Proofs
- AI, Math, the document-drop. Non-Tech Thoughts
- Complexity and Lean
- Conjectures that I thought would not be proved in my lifetime....were
- Open No More
- How many humans does it take to make tech seem human? Do you want to be one of them?
September 2026
- Does Programming Help You Understand Complexity?
- What is the point of AI-disclosure?
- The New STOC Rules for the AI Era
- I don't care about majors, minors, or honors programs. Do you?
- AI and Manufacturing Redux
- Math, AI, and the Navier-Stokes Equations
- Navier-Stokes and Lean
- Richard Stearns (1936-2026)
- What is a Computer?
August 2026
- Claude and Colorblind Questions
- The Calculator Transition
- Centaur Math
- IIT is the canary in the coalmine (Do our younger readers know what that means? Do we have younger readers?)
- Unexpected Unemployment
- Math Concepts With Funny Names
- A problematic category on Jeopardy Raises a Good Question
July 2026
- Would Erdos have been happy with the resolution of the Erdos Unit Distance Problem? How to find out?
- Complexity Class of the Week: \(L_2^P\)
- Bipartite Perfect Matching in Deterministic NC
- Herman Chernoff (1923-2026)
- 2... 1/2 THEN 3... 1/6 THEN 5 ....1/15 and so on. And So On?
- Wither/Whither the ACM
- Extreme cases of clickbait!
- The True Method
June 2026
- Guest Post by Peter Brass on the new NSF guidelines
- The Zone
- The New Result on Off-diagonal Ramsey Numbers
- The Tech of Silk Road
- mnemonic devices and pangrams that could be real sentences
- Respect the P v NP Problem
- Humans Solve Erdos Problem!!
- The Industrialization of Academic Research
- Odd Scenarios about Research Claims and Authorships
May 2026
- Authorship in the AI Age
- Two Erdős Problems on Points in the Plane and AI
- Range Avoidance
- Scott Aaronson wins Trevisan Award? Prize? Medal? Statue?
- Prediction Markets Redux
- Searches Are Weird! No they're not! Bad coding style?
- When do we know someone has died
- A few notes on Michael Rabin
April 2026
- Because It Doesn't Have To
- LEAPing into the Future of Coding
- Michael Rabin Passed Away on April 14, 2026, at the age of 94
- Machine Learning and Complexity
- Guest Post from Peter Brass, Former NSF Theory Director, on the NSF budget.
- Afterthoughs on Banach Tarski and the Miracle of loaves and Fishes
- Fun Little Solutions
- I helped the Pope's with his latest Encyclical (His Math Background Helped)
March 2026
- Fun Little Problems
- My Oxford Term
- A $100 gift card could be legit. A $1000 is obviously a Scam. What should scammers do?
- Bennett and Brassard Win the Turing Award
- For \(R^3\) the problem is open. That's too bad. We live in \(R^3\)
- Tony Hoare (1934-2026)
- How does AI do on Baseball-Brothers-Pitchers
- The Purpose of Proofs
- Goodhart's law: Ken Jennings and Types of Knowledge
February 2026
- A Probability Challenge
- ChatGPT gets an easy math problem wrong (I got it right). How is that possible?
- Joe Halpern (1953-2026)
- Assigning Open Problems in Class
- The Future of Mathematics and Mathematicians
- I used to think historians in the future will have too much to work with. I could be wrong
- Sampling the Oxford CS Library
- Before the ChatGPT-HW debate there were other ``If students use X to do their HW'' debates
January 2026
2025 98
December 2025
- Complexity Year in Review
- A Place Away From Tech
- Weird Al vs Weird AI
- Learning the Mathematical Process
- Tom Stoppard 1937-2025
- Finding Papers Before the Web
- Does ChatGPT really help programmers?
November 2025
- The Little Theorems
- Factoring Carmichael Numbers
- Test of Time Awards: A Good Idea but ....
- The Future of Teaching Assistants
- A Presidential Trivia Question, how I tried to solve it
- The Complexity Argument for Capitalism
- Did Euclid exist? Is it okay to quote people that did not exist?
October 2025
- AI and the Power of Nonuniform Circuits
- Bill's Bad Advice
- AI and Intro Theory
- Sept 16, 2025 was Pythagorean Day
- Fall Jobs Post 2025
- The Most Common Name in the World is Not Charles Lin. But It Seems That Way To Me.
- Big Bots Don't Cry
- If you use AI in your work do you brag about it or hide it?
- Computers Don't Want
September 2025
- Clyde Kruskal talks about his Father Martin on Martin's 100th birthday
- Self-Driving Cars
- We can find more papers on the web than we used to. Are we reading them?
- What is "PhD-Level Intelligence"?
- ``I'm on vacation so I won't be checking email'' will sound funny soon. Maybe it already does.
- Is the Prob Method `Just Counting'- I say no and HELL NO
- A Restless Soul
- Guest Post on Why Coding Style is Important
August 2025
- The Logical Argument
- Was the George Foreman Grill The Best Invention of the last 50 Years?
- The Phone
- A few more notes about Tom L
- Total Pixel Space
- My Tom L post inspired a mathematical definition of Rabbithole
- AI and ...
- Some thoughts on journals, refereeing, and the P vs NP problem
July 2025
- Tom Lehrer Passed Away at the Age of 97
- Answer to my GROUP ONE/GROUP TWO Prez question
- Trevisan Prize- Deadline July 31 for Notification Intent, Aug 31 for nomination.
- A Prez Question: Can AI do it? Can you? Can I?
- Turing, Wagner, Ruth
- How much money did Francis Scott Key give to have a building named after him?
- The Customers of the Academy
- The New Lower Bound on Busy Beaver of 6.
- A Professor Again
June 2025
- Two high school students have a new proof of the Pythagorean Theorem / Pythag theorem older than thought
- The Distribution of Prime Numbers: A Geometrical Perspective
- If you do well in the UMCP HS Math Competition you may win $1,000,000
- Fulbright Memories
- Lance never thought he would see a Pope who roots for the same team as him. And now...
- Defending Theory
- The New Godel Prize Winner Tastes Great and is Less Filling
- Rules vs Standards
- Complexity theory of hand-calculations
May 2025
- The Hilltop Story
- Some are Mathematicians, some are Carpenters' Wives, Some are Popes.
- The Blog of Record
- Is Satire Dangerous in the AI-Age?
- A Bittersweet Anniversary
- Random Thought on the New Pope (the actual New Pope, not the TV series). He was a math major!
- Using AI for Reviews
- My response to Scott's least controversal post ever!
April 2025
- P v NP Papers Galore
- A personal view of the NSF hot mess: My REU program
- Real People
- Eisenhower's Farewell Address
- I want an application of this application of Ramsey Theory to Semigroups
- Why Can't We Break Cryptography?
- I was invited to a Nutrition conference. Why?
- PDQ Shor (?-2025)
March 2025
- Survey's are done stupidly/A stupid question from a survey
- What Happened to MOOCS?
- Recording lectures? Posting the Recordings? Using Slides?
- A Failure to Communicate
- My Post-Covid Post
- Covid and Complexity
- Numbers that look prime but aren't
- Taking a Stand
- Karp recently turned 90 but there was no conference to celebrate that. Which numbers do we use and why?
February 2025
- You Need Much Less Memory than Time
- Why my department hopes I do not die this spring
- Tomorrow and Yesterday
- Big Breakthrough in the exciting world of sum-free sets!
- Research Then and Now
- Does Lance dislike Ramsey Theory Because he's colorblind?
January 2025
- The Situation at the NSF
- Lautemann's Beautiful Proof
- People who live through two square years
- The Fighting Temeraire
- Presidential Quiz!
- "Our Days Are Numbered"
- Random Thought on AI from someone in the REAL WORLD
- When DO Names Change? When SHOULD Names Change?
- The Betty White Award for 2024
- My Drunken Theorem
2024 102
December 2024
- Complexity Year in Review
- Information is Physical?
- Random Thoughts on AI (Human Generated)
- It's Time to Stop Using Grades
- My comments on Lance's Favorite Theorems
- Favorite Theorems: The Complete List
- Conway's Trick for Divisibility. Asking its complexity is an odd question.
November 2024
- We Will All Write Like AI
- For what d is the following true: For all 2-colorings of \(R^d\) has a mono unit square (Answering(?) the Question)
- For what d is the following true: for all 2-colorings of \(R^d\) there is a mono unit square (Asking the Question)
- Favorite Theorems: Learning from Natural Proofs
- Steven Rudich (1961-2024)
- Higher Education Under Trump
- A new Mersenne Prime Has Been Found. When will we find the next one?
October 2024
- FOCS 2024
- Random Thoughts on the Election
- Family Feud vs Pointless
- Contrast an Episode of Columbo with the recent Nobel Prizes
- Computing and the Nobels
- A Trip Down Memory Lane: Desc comp, Constant Round Sorting, Division Breakthrough, Derandomization.
- Fall Jobs Post 2024
- Emil Post Anticipated (more than anticipated) Godel and Turing
- Favorite Theorems: Gradient Descent
September 2024
- Progress on R(5). Will there be more?
- LeetCode and AI
- I thought I knew what pizza was...
- Embracing the Future of Manufacturing
- How will chatGPT affect Homework?
- Natural Proofs is Not the Barrier You Think It Is
- Very few problems are in NP intersect coNP but not known to be in P. What to make of that?
- Favorite Theorems: Parity Games
- Six degrees of separation has been proven. Really?
August 2024
- My Quantum Summer
- Whats worse for a company: being hacked or having technical difficulties? I would have thought being hacked but...
- The Levin Translation
- Request open problems in honor of Luca Trevisan
- Favorite Theorems: Random Oracles
- The combinatorics of Game Shows
- Determing which math problems are hard is a hard problem
July 2024
- In the future we will all have songs written about us, and it will be Lance's fault.
- Complexity in Michigan
- FLT solution annouement had its 31's anniv was about a month ago. Some poems about FLT NOT from ChatGPT
- The Story of Shor's Algorithm
- The Term Quantum Being Misused ... Again
- Favorite Theorems: Extracting Ramsey Graphs
- The combinatorics of picking a Vice President
- Why is called the Turing Award (revisited)?
- Technology: 1966, 2006, 2023.
June 2024
- E versus EXP
- Soliciting open problems in honore of Luca T for my Open Problems Column
- Luca Trevisan (1971-2024)
- Rethinking Heuristica
- A Trip Down Memory Lane: Eric Allender on asy lower bounds and isomorphism
- Should Prover and Verifier have been Pat and Vanna?
- Favorite Theorems: Algebraic Circuits
- CFG-Kolm-complexity is singleton sets with Lance and Bill
- The Godzilla Moment
- FOCS 2024 Test of Time Award. Call for nominations and my opinion
May 2024
- Double Digit Delights
- National BBQ day vs World Quantum Day
- Peer Review
- I don't do that well when the Jeopardy category is Math
- Jim Simons (1938-2024)
- What is Closed Form? The Horse Numbers are an illustration
- Favorite Theorems: Dichotomy
- May the fourth be with you. Too many -days?
- Our Obsession with Proofs
April 2024
- Math Thoughts Inspired by the TV show Succession
- Is Persistence an Anachronism?
- Intelligent Comments on Bill's G.H. Hardy/Avi W post that we did not post.
- Favorite Theorems: Quantum Provers
- Avi Wigderson is a counterexample to TWO stupid thoughts of G.H. Hardy
- Avi wins the Turing Award
- Rance Cleaveland passed away on March 27, 2024. He will be missed
- Answer to Question. MetaQuestion remains unsolved
- A Math Question and a Meta Question
March 2024
- The Softening of Computing Jobs: Blip or Trend?
- I know what A-B-C-D-F mean but what about V? X? HP?
- Can you feel the machine?
- Grad Student Visit Day: That was then, this is now.
- Translation in Context
- The Thrill of Seeing Your Name in Print is Gone
- Favorite Theorems: Sensitivity
- The letter to recommend John Nash was ``The Best Recomendation Letter Ever''- I do not think so.
February 2024
- A Quantum State
- When is it worth the time and effort to verify a proof FORMALLY?
- Sumchecks and Snarks
- ChatGPT thinks Graph Isomorphism has real applications. Is it right?
- Focusing on te
- Are there any REAL applications of Graph Isomorphism?
- Favorite Theorems: Graph Isomorphism
- The advantage of working on obscue things
January 2024
- University Challenges
- Certifying a Number is in a set A using Polynomials
- Learning Complexity on Your Own
- A paper that every Undergraduate should read
- Offer Timing
- A nice dice problem-Part 2
- Guest Post by Mohammad Hajiaghayi on SODA Business Meeting 2024
- A nice dice problem- Part I
- Favorite Theorems 2015-2024
- The Betty White Award for 2023: Tommy Smothers
2023 92
December 2023
- 2023 Complexity Year in Review
- Archimedes, Pi, and Pickelball
- Respect
- Where do Journals go to Die?
- Do We Need to Formalize?
- Where do Non-Primitive Recursive Functions come up NATURALLY?
November 2023
- The Engineer and The Computer Scientist
- Can I make money in the betting markets based on what i ``know'' about the Republican VP choice
- War Games
- Inverting a Function
- Forgetting your password is usually not a big deal. Unless....
- Othello. Solved.
- In the bad old days we had Punchcards. How did people deal with that?
- The Loop Graph
October 2023
- Theory that really DOES apply: Security.
- Saving Grace
- When did Math Get So Hard- Part 2
- Fall Jobs Post 2023
- Paper is a tech-free way to preserve writing. Is there a tech-free way to preserve sound (e.g., music)
- Measuring Quantum Progress
- Young Sheldon gets two things spot-on/Am I more famous than.../Might YS become TS?
- The Lyadov Lesson
September 2023
- Half-Exponential No More
- We Must Be Doing Something Right
- ACM to go paper-free! Good? Bad?
- Mr. Jaeger and The Scroll
- Asymptotics of R(4,k)- a new result!
- Books to Inspire Math
- The CONTRADICTION of Margaritaville and other songs
August 2023
- What Makes a Constructive Proof?
- Theorems and Lemmas and Proofs, Oh My!
- Transcripts for the 21st Century
- Why I have some sympathy for the Simulation Theory (We are all characters in a video game.)
- Turning Sixty
- The Acting Professor
- Permutable Primes and Compatible Primes
- The College Visits
July 2023
- Another problem with CHATgpt
- Paper Writing Before Overleaf
- "Never give AI the Nuclear Codes" Really? Have you seen Dr. Strangelove?
- More on Pseudodeterminism
- Finding and answer to a math question: 1983 vs 2023.
- Whither Twitter
- A further comment on Chernoff--- and the future of ....
- Automating Mathematicians
- Chernoff Turns 100
June 2023
- Can you put n pennies on an n x n chessboard so that all of the distances are distinct/how to look that up?
- Don't Negotiate with Logic
- Ted Kaczynski was at one time the worlds most famous living mathematician
- Randomized Acceptances
- Posting a book online with a password- that you broadcast.
- Quantifiers: To Parenthesize or not to Parenthesize? Matrix of Formula: To Bracket or not to Bracket?
May 2023
- On Nov 10, 2014 the TV show Scorpion mentions Software that is like ChatGPT for Music
- Finding Primes Pseudodeterministically
- Logic and lack of Logic of Anti Vaxers
- Community Guidelines that Ignore History
- Take a number and map it to the number of letters in its name
- Winter is Coming
- Other Ramsey's
- Breaking Ground in Isomorphism Testing: A Leap Forward for a Bottleneck Case of Group Isomorphism
- There are an infinite number of proofs that there are an infinite number of primes
April 2023
- Comic Book Alignment
- Thoughts on Gordon Moore
- Health Tech
- My Week at Simons
- Complexity and Explainable AI
- Neil Jones (1941-2023)
- Who's on April First
March 2023
- Alan Turing, The Opera
- The SIGACT Book Review column list of books it wants reviewed
- A Strange Hiring Season
- New Upper Bound on R(k). WOW!
- Identities in Computational Complexity
- Problems we assume are hard. Are they? ALSO- revised version of Demaine-Gasarch-Hajiaghayi is posted!
- Peer Review
- Goodbye Dilbert
February 2023
- I wish we had less students in a Class. Demographics says I may get my wish.
- The Virtual Grad Student
- It is more important than ever to teach your students probability (even non-stem students)
- Blurry JPEG or Frozen Concentrate
- When is a paper `Easily Available' ?
- Why Can't Little Chatty Do Math?
- After you are notified that an article is accepted...
- Responsibility
January 2023
- Why does pi come up so often? I don't know either but ...
- Back to the 90's
- The Betty White Award for 2022
- Meta-Complexity
- ChatGPT tried to write an obit for Martin Davis. What it got right, wrong, and what to make of it.
- Semantic Search for the Blog
- Martin Davis Passed Away on Jan 1, 2023
- Positional Encoding
2022 77
December 2022
- Complexity Year in Review 2022
- Voter Suppression, Harvard Style
- FinTech is Dead, Long Live FinTech
- Commercials are not logical. FTX edition.
- Harry Lewis's talk on The Birth of Binary on Dec 8 (Thats today!)
- The Future of Education is Personal
- How do we keep the community connected?
November 2022
- Would you be more productive if you didn't log on? It worked for Christopher Havens!
- A Celebration of Juris
- Fall Jobs Post 2022
- Who first thought of the notion of Polynomial Time?
- The Structure of Data and Machine Learning
- Euclidean TSP is NP-hard but not known to be in NP. Why not known?
- Should you quit Twitter and Texas?
October 2022
- What was the recent Nobel Prize in Physics really about?(Guest Post)
- The Media Coverage of the Matrix result is Terrible (though not worse than usual)
- Cheating in Chess and in Class
- Alpha Tensor
- BYTE LYNX- an awesome video game/Am I an influencer?
- How Not to Pass a Polygraph Test
- Will Strassen's Matrix Mult Alg ever be practical?
- Art and Technology
- Is it okay for a paper or book to say `for more on this topic see Wikipedia Entry BLAH.
September 2022
- Machine Learning and Complexity
- Is the complexity of approximating Vertex Cover of degree 3 open? (ADDED LATER-NO)
- POSTED UPDATED VERSION OF Computers and Intractability: A guide to Algorithmic Lower Bounds posted (New title)
- There are two different definitions of Integer Programming. Why?
- Monarachy: A Problem with Definitions
- Thirty Years of Dagstuhl
August 2022
- The NIST Process for Post-Quantum Cryptography
- Computational Intractability: A Guide to Algorithmic Lower Bounds. First draft available! Comments Welcome!
- 20 Years of the Computational Complexity Weblog
- Conference Modality
- A non-controversial question about the Documents Donald Trump had in his house
- The Godfather of Complexity
- The Held Prize for comb. opt. AND Disc Opt AND Alg AND Complexity theory AND related parts of CS.
July 2022
- Juris Hartmanis passed away on July 29 at the age of 94
- 100 Best Number Theory books of all Time---except many are not on Number Theory
- What is known about that sequence
- An open question about a sequence mod M.
- Review of The Engines of Cognition: Essays From the LessWrong Forum/Meta question about posts
- The Highland Park Shooting
June 2022
- A Gadget for 3-Colorings
- Counting the Number of 3-colorings of a graph is Sharp-P complete. This should be better known.
- Guest post by Prahalad Rajkumar: advice for grad students
- I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrong
- Does the Social Media Law in Texas affect theory bloggers?
May 2022
- Discussions I wish we were having
- In the 1960's students protested the Vietnam war!/In 1830 students protested... Math?
- Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...
- Queen Elizabeth is the 3rd longest reigning monarch; The problem with definitions
- The (R)evolution of Steve Jobs
- Elon Musk To Buy Complexityblog
April 2022
- The Roeder Problem was Solved Before I Posed it (how we missed it)
- 1-week long Summer School for Ugrads Interested in Theory, and my comments on it
- The Roeder Seq Problems was Solved Before I Posed it (Math)
- Masks
- A Ramsey Theory Podcast: No Strangers at this Party
March 2022
- I don't care about Ketanji Brown Jackson's LSAT scores and she does not care about my GRE scores
- Do you want to be the SIGACT NEWS book review editor?
- The War and Math
- Problem X won't be solved in MY lifetime- but what about...
- Random thoughts on the Russian Invasion of Ukraine
- REU programs in general, and two at Univ of MD this summer.
February 2022
- I did an Instagram Live with Mohammad Hajiaghayi
- I will be on instagram/If you have two reals in a box- Answer (Guest Post by David Marcus)
- I will be on Instagram/If you have two reals in a box.... (Guest Post by David Marcus)
- Belated happy 80th, Allan Borodin!
- A Book Break
- PSPACE is contained in Zero Knowledge!! How come nobody seems to care?
- The Beginnings of Zero-Knowledge
January 2022
- Regan Lipton celebrates my 1000th blog post and random thoughts this inspires
- A Failure to Communicate
- Personal Reflections on Dick Lipton in honor of his 1000th blog/75th bday.
- On the California Math Framework
- Math problems involving Food
- Did Betty White die in 2021?/Why do people have their `end-of-the-year' lists before the end of the year?
2021 89
December 2021
- Complexity Year in Review 2021
- Fifty Years of P vs. NP and the Possibility of the Impossible
- Did Lane Hemaspaandra invent the Fib numbers?
- Defending the Status Quo
- Yes Virginia, there is a Santa Clause for Complexity Theorists, If you Only Believe
- TheoretiCS: A New TCS Journal
November 2021
- Open: 4 colorability for graphs of bounded genus or bounded crossing number (has this been asked before?)
- Finding an element with nonadaptive questions
- CS Slow to Change?
- When did Computer Science Theory Get so Hard?
- 20 Years of Algorithmic Game Theory
- Reflections on Trusting ``Trustlessness'' in the era of ``Crypto'' Blockchains (Guest Post)
- A Complexity View of Machine Learning?
October 2021
- When did Math Get So Hard?
- Fall 2021 Jobs Post
- Squaring the circle is mentioned in a Gilbert and Sullivan comic Opera.
- Is MATH Ready for P=NP? Is Alexandra Fahrenthold Ready for P=NP?
- A Young Person's Game?
- I have a book out on muffins (you prob already know that)
- C++ is for Cookie and That's Good Enough for Me
- How have computers changed society? Harry Lewis (with co-authors) have a book out on that.
September 2021
- Being the Chair
- My academic lineage and more interesting facts that come out of it
- Why Conferences?
- The New Jeopardy Champion is a `A CS grad student from a school in New Haven'
- Review of A Blog Book based on the Less Wrong Blog
- The Death of Expertise
- Guest Post on Solving (or trying to) Poly Diophantine Equations by Bogdan Grechuk
- The hierarchy and GapP
August 2021
- Since we will soon be back in the classroom, how was Zoom? Anything you want to maintain?
- The Long Road
- When Words Get Stretched Beyond Their Original meaning
- Trusting Scientists
- What are the most important 46 papers in Computer Science? Harry Lewis has a book about them!
- Recognizing Faces
- Combing two posts: Blankface (Scott Aa) and Is Science Slowing Down? (Scott Al)
- Pole Vault Live Blogging
- Do Four Colors Suffice?
July 2021
- Covid Stats
- I wish problems I have with computers really were my fault
- Technical Difficulties
- Political Intersections: Trump honors Antifa member who was shot dead by police
- Would you take this bet (Part 2) ?
- Would you take this bet (Part 1) ?
- Intersecting Classes
June 2021
- Someone thinks I am a fine artist! Why?
- I went to the ``debate'' about Program Verif and the Lipton-Demillo-Perlis paper
- Collusion Rings
- Benny Chor (1956-2021)
- The Future of Faculty Hiring
- When do you use et al. as opposed to listing out the authors? First names? Middle initials? Jr?
- What happened to self-driving cars?
May 2021
- What is a natural question? Who should decide?
- Does the university matter?
- Emerging from the Pandemic
- Why do countries and companies invest their own money (or is it?) in Quantum Computing (Non-Rhetorical)
- Cryptocurrency, Blockchains and NFTs
- Trump, Facebook, and ComplexityBlog
- Negotiations
- The Mythical Man-Month, Hen-Day, and Cat-Minute (Fred Brooks Turned 90)
April 2021
- Ferrer's Diagrams can be used to prove X theorems about partitions. What is X?
- The Million Dollar Sermon
- An investment puzzle and speculation as to why some think its hard
- Ordering Beauty
- Is the following reaction to getting the first COVID shot logical?
- Quantum Stories
- Do any NP-reductions use deep mathematics? Non-rhetically
- Want to Buy a Theorem?
March 2021
- Slicing the Hypercube
- The key to my Taylor series problem: Buddy can you spare a penny, nickel, dime, or quarter
- A Taylor Series Problem
- I read the news today oh boy
- I didn't understand The Art Market before the NFT sale, and I understand it less now
- Cake Cutting in Overtime
- When do I need to warn about Spoilers?
February 2021
- Using number-of-PhD's as a measure of smartness is stupid.
- Complexity is the Enemy of Speed
- Good Names and Bad Names of Game Shows and theorems
- Two examples of Journalists being... Wrong. One BIG one small
- The Victoria Delfino Problems: an example of math problems named after a non-mathematician
- A Blood Donation Puzzle
January 2021
- Grading policies during Covid-No easy answers
- PhDs and Green Cards
- Answers to the Prez Quiz, and some interesting history
- Alan Selman (1941-2021)
- Presidential Quiz: Three ways to take it
- The Ethics Board
- The ACM History Committee call for proposals looks wrong
- My Survey on Hilbert's 10th for particular (d,n) is ready for you to help me on!
2020 76
December 2020
- Complexity Year in Review 2020
- Slowest Sorting Algorithms
- Dr Jill Biden
- Optiland
- Quarterly Th. Wksp `at' Northwestern, and thoughts inspired by it
- Shuffling Around
- In 1974 Planarity was O(V) time and could do 900 node graphs in 12 seconds! Fast then...
- Chess is Back
November 2020
- James Randi, Magicians-Author-Skeptic, passed away at the age of 92
- Fun with birthdays, inspired by Nov 20
- Vaughan Jones and Kaikoura
- Alex Trebek/What is today's post about?
- Recovery
- Random Thoughts on the Election (2020)
- I polled my class about the election
October 2020
- 2020 Fall Jobs Post
- Do not become obsessed with the Polls unless...
- Nature vs Nurture close to my birthday
- 50 Years of PBS
- Hugh Woodin, Kurt Godel, Dwayne `The Rock' Johnson, Robert De Niro, David Frum, Tom Selleck: Do I care what they think? Should I?
- Revisiting the Continuum Hypothesis
- MIP* = RE Redux
September 2020
- A Quote from Tesla which is very predictive in one way, and perhaps not in another way
- Remembering 2000
- Baseball can go on forever, it doesn't just seem that way
- An interesting serendipitous number
- When are both x^2+3y and y^2+3x both squares, and a more general question
- Two Math Problems of interest (at least to me)
- A well known theorem that has not been written down- so I wrote it down- CLIQ is #P-complete
August 2020
- Sharp P and the issue of `natural problems'
- Mathematics is not commutative
- Simons Institute Gets Another Decade
- Random Thoughts on the Pandemic
- Do Senators have an Advantage for being Dem VP Nominee?
- The Gauss story is false yet we still tell it. Should we?
July 2020
- Do computers make us more safe or less safe?
- Virtual Complexity
- Erdos-Turan for k=3 is True!
- Ronald Graham: A summary of blog Posts We had about his work
- Reflections on Ronald Graham by Steve Butler
- A table for Matrix Mortality- what I wanted for Hilbert's 10th problem
June 2020
- Can you name a famous living Chemist? Can anyone?
- Winner of Ramsey Meme Contest
- On Chain Letters and Pandemics
- Presentations of Diffie-Helman leave out how to find g
- The Committee for the Adv. of TCS- workshop coming up SOON!
- How to handle grades during the Pandemic
May 2020
- Oldest Living Baseball Players- can you estimate...
- Obit for Richard Dudley
- Awesome Video from Women In Theory!
- And the winners are ....
- Vidcast on Conferences
- Why is there no (d,n) grid for Hilbert's Tenth Problem?
- Predicting the Virus
April 2020
- A Guest Blog on the Pandemic's affect on disability students
- Complexity Vidcast - Future Edition
- The Summer Virtual Conference Season
- Theoretical Computer Science for the Future
- John Conway Dies of Coronvirus
- Return of the Vidcast
- Let's Hear It for the Cloud
March 2020
- Length of Descriptions for DFA, NFA, CFG
- Robin Thomas
- What to do while ``stuck'' at home/Other thoughts on the virus
- What to do while stuck at home Part I
- Richard Guy passed away at the age of 103
- The Importance of Networking
- Theorist Paul R Young passed away
- A New College of Computing at Illinois Tech
- Logic examples for your Discrete Math class
February 2020
January 2020
2019 84
December 2019
- Complexity Year in Review 2019
- Why is there no all-encompassing term for a course on Models of Computation?
- What do you call your ugrad non-algorithms theory course?
- Julia Robinson's 100th birthday
November 2019
- Fields used to be closer together than they are now. Good? Bad?
- A non-moral dilemma about cheating, but it brings up some points
- Limits of using the web for info- self-reference
October 2019
- Statistics to Scare
- Random non-partisan thoughts on the Prez Election
- Differentiation and Integration
- 2019 Fall Jobs Post
- The Sheldon Conjecture (too late for Problems with a Point)
- William Kruskal's 100th birthday
- What comes first theory or practice? Its Complicated!
- Quantum Supremacy: A Guest Post by Abhinav Deshpande
- Richard Guy is 103 years old today
September 2019
- Quantum Supremacy
- Applicants to Grad School are too good. Here is why this might be a problem.
- this paper from 2015 cracks Diffie-Hellman. What to tell the students?
- Are there any natural problems complete for NP INTER TALLY? NP INTER SPARSE?
- Transitioning
- Can Mathematicians Fix Iphones? Can anyone?
August 2019
- `Are you a math genius?' `Can you fix my Iphone?' `What do you think about Facebook and Privacy?'
- Obstacles to improving Classical Factoring Algorithms
July 2019
- Turing to be on the Bank of England 50 pound note, giving me an excuse to talk about Turing
- The Advisor/Advisee Relationship
- Answer to both Infinite Hats Problems from the last post
- Guest post by Samir Khuller on attending The TCS Women 2019 meeting
- Two infinite hat problem and a question about what is ``well known''
- Degree and Sensitivity
- Fortran is underated!
- Local Kid Makes History
- A proof that 22/7 - pi > 0 and more
June 2019
- FCRC 2019
- Are you smarter than a 5th grade amoeba?
- The Urban/Rural Collegiality Divide
- Why does the Nevalina Prize (now Abacus) got to Algorithms/Complexity people
- Compressing in Moscow
- Ray Miller, one of our founders, Passes away at the age of 90
- What Happened to the Surprising Theorems?
- IMU's non-controversial changing the name of the Nevanlinna Prize
May 2019
- NSF Panels
- separating fact from fiction with the 56% of Americans say Arabic Numerals should not be taught in school
- Logic Then and Now
- Notorious L.A.H or Notorious LAH? OR You always need one more proofread
- Getting Through the Clutter
- Ronald Graham's other large number. Well---- it was large in 1964 anyway.
- Multiple Provers
- Thoughts on the recent Jeopardy streak (SPOILERS)
- The Next Chapter
April 2019
- x3 + y3 + z3 = 33 has a solution in Z. And its big!
- Geo-Centric Complexity
- Quiz Show Scandals/Admissions Scandal/Stormy Daniels/Beer names:being a lawyer would drive me nuts!!!!!!
- Physics of Everday Life
- Good article, terrible headline
- Elwyn Berlekamp Died April 9, 2019
- Problems with a point- NOT a plug, just some thoughts on books and book writing
- Cuckoo Cycles
- An Interdisciplinary approach to P vs NP
March 2019
- Scooped
- Random Thoughts on the admissions scandal
- Back at Dagstuhl
- Third Poll on P vs NP and related Questions is out now! And the winner is Harambe!
- Captain Einstein
- Richard Karp: His influence and how to honor him
- Qed
- How are there 20 copies of my new book through other booksellers and why are they so highly priced
February 2019
- Flying Pigs Unsafe at Any Speed
- Problems with a Point: Exploring Math and Computer Science
- Extra! Extra! Read all about it!
- Using `who will be the dem VP choice' article in class
- The iPhonification of Everything
- I think ze was confused -- in favor of genderless pronouns
- An Immerman-Szelepcsényi Story
- Don't know Football but still want bet on the Superb Owl?
January 2019
- Phish Before Turkey
- The Paradigm Shift in FinTech Computation and the need for a Computational Toolkit (Guest Post by Evangelos Georgiadis)
- Machine Learning and Wind Turbines
- ACM prize and some thoughts on the Godel Prize
- The Cost of Privacy
- do we ever only care about the decision problem? I know of only one case of that
- Search versus Decision
- When is a kilogram not a kilogram?
- Today is Thirdsday! Enjoy it while you can!
2018 100
December 2018
- Complexity Year in Review 2018
- Ker-I Ko (1950-2018)
- Guest post: Join SIGACT!
- Inverting Onto Functions
- Super Asymmetry on The Big Bang Theory: How Realistic?
- Remembering George H. W. Bush
- George HW Bush passed away- some non-partisan math comments
November 2018
- LOGCFL Venkat Style
- If you think a theorem is true then spend half your time trying to prove its true, and half trying to prove its false.
- Is Secret sharing REALLY REALLY REALLY used?
- Simons and Amazon
- And the winner is again, Harambe: A pre election poll of my class that was truly a referenum on the Prez
- The Data Transformation of Universities
- Is Fuzzy Sets Common Knowledge? How about Napier as inventing (or something) logs?
- P = NP Need Not Give a SAT Algorithm
October 2018
- If P=NP then we HAVE an alg for SAT.
- Good Results Made Meaningless
- Please Don't call them Guidance Counselors
- A New Cold War?
- Practical consequences of RH ?
- 2018 Fall Jobs Post
- A New ACO Center (guest post by Vijay Vazirani)
- John Sidles, Mike Roman, Matt Howell, please email me/hard to get emails of people
- Google added years to my life
- Muffin Math
September 2018
- Still Typecasting from Dagstuhl
- Lance and Bill go to Dagstuhl: The Riemann Edition
- Why wasn't email built securely?
- What is a Physicist? A Mathematician? A Computer Scientist?
- P = NP and Cancer
- The Tenure system is broken but not in the way that you think (Anon Guest Post)
- Are Conferences Discriminatory?
- The Rule of Threes/Astrology
August 2018
- What is Data Science?
- Is Trivium (the Stream Cipher) used?
- Katherine Johnson (1918-)
- The Zero-One Law for Random Oracles
- Fractional Problems: 2.1-colorable, 2.8-SAT
- How valuable is a Fields Medal?
- While I Was Away
- The Future of TCS Workshop, celebrating V Vazirani 60th, now online
- Three trick questions in Formal Lang Theory
July 2018
- Complexity in Oxford
- Need EASY approaches to getting unif random from non-random sources
- CRA Snowbird 2018
- The Mystical Bond Between Man and Machine
- The Six Degrees of VDW
- Soliciting answers for THIRD survey about P vs NP
- Happy 90th Juris!
- The BREAKTHROUGH on Chromatic Number of the Plane (guest post)
June 2018
- STOC 50 Part II
- STOC 50 Part I
- The Muffin Problem
- Its good to be mii
- Hoteling
- How the Villarino-Gasarch-Regan paper came about
- I tell my class that P is important because... but is that really true?
- BQP not in the Polynomial-Time Hierarchy in Relativized Worlds
May 2018
- Seventh Grade Math Contest
- Why is someone emailing me an offer to apply to be chair?
- Kolmogorov Complexity and Causation
- COMPUTER PROOF vs computer proof- Quadratic VDW theorem
- The Complexity of the Firm
- What does it mean for a student to guess an answer?
- Richard Feynman (1918-1988)
- Second of N posts on G4G13. Maybe
- Broader Impacts Redefined
April 2018
- Gathering for Gardner 13 - the first or third of many posts
- The 8 digit number I asked for
- Find an 8-digits number such that ....
- Memory is Hot
- Is DTIME(n) closed under concat? star? of course not but...
- Lance and Bill Gather for Gardner
- Whan a deep theorem of your Uncles becomes standard should you be sad?
- Challenge about NFA for {a^y : y\ne 1000} answered.
- Challenge: Is there a small NFA for { a^i : i\ne 1000} ?
- Almost Famous Quantum Polynomial Time
March 2018
- A Reduced Turing Award
- Why do we give citations? How should we give citations?
- Stephen Hawking (1942-2018)
- Wanted: An Easy Proof of a Weak Theorem in NT so that I can get another VDW--> Primes infinite proof to be really easy.
- Data-Driven Programming
- When the Wrong People raise the issue
- Me and My Bolt
February 2018
- When students are wrong but have a valid point, encourage them
- NP is Hard
- The web bad/People using it bad.
- Corporate Education
- A ``new'' ``application'' of Ramsey Theory/A Truly ``bad'' math song
- For the Love of Algorithms
- "How can you use your research for ugrad projects?'- the wrong question
- Flying Blind
January 2018
2017 101
December 2017
- Complexity Year in Review 2017
- Having Faith in Complexity
- Monkey First!
- Our AI future: The Good and the Ugly
- Interesting Probability on a VERY OLD TV show
- Razor's Edge
- Fireside chat with Simons Inst Director Dick Karp
November 2017
- Kolmogorov Complexity and the Primes
- Van der Waerden's theorem implies the infinitude of the primes
- The Grad Student Tax
- A Tale of Three Rankings
- Can you measure which pangrams are natural
- Advice for the Advisor
- The two fears about technology- one correct, one incorrect
- Matching and Complexity
October 2017
- The k=1 case is FUN, the k=2 case is fun, the k\ge 3 case is... you decide.
- 2017 Fall Jobs Post
- Open: PROVE the pumping and reductions can't prove every non-reg lang non-reg.
- The Amazon Gold Rush
- Reductions between formal languages
- Lessons from the Nobel Prizes
- Michael Cohen
- Is the Textbook Market doomed?
- Monty Hall (1921-2017) and His Problem
September 2017
- Tragic Losses
- Science fiction viewers used to embrace diversity (or did they) and now they don't (or do they)
- Acronyms and PHP
- A problem I thought was interesting- now...
- Random Storm Thoughts
- The Scarecrow's math being wrong was intentional
- Statistics on my dead cat policy- is there a correlation?
- Rules and Exceptions
August 2017
- NOT So Powerful
- either pi is algebraic or some journals let in an incorrect paper!/the 15 most famous transcendental numbers
- Kurtz-Fest
- The Crystal Blogaversity
- What is unusual about this MIT grad student in Applied Math?
- Wearable Tech and Attention
- Should we care if a job candidate does not know the social and ethical implications of their work (Second Blog Post inspired by Rogaway's Moral Character Paper)
- What Makes a Great Definition
July 2017
- Harvard punishes some social organizations. Why?
- Peter Wegner (1932-2017)
- Lessons from Norway
- What are the top Computer science programs for women?
- I would call these Galois Games but I can't
- 89944 Hat Problems
- Solutions to some Hat Problem AND some points of interest.
- Two hat problems you may or may not have seen but I have a point to make about one of them
- The Complexity of Rubik's Cube
June 2017
- 50 Years of the Turing Award
- Best. STOC. Ever.
- Joan Clarke (1917-1996)
- Harvard revokes admission of students based on what was said in a private(?) chat room
- The Power of Economic Inefficiency
- Climate Change: The Evolution of the Deniers/Does Paul Ryan Hate His Grandchildren?
- Theory Jobs 2017
- Big News on W(3,r) !
- Who Sets Policy?
May 2017
- Google Scholar thinks my Hilbert Number is 1
- Graduation from the Other Side
- The Optimizers
- If an ugrad asks `is field X worth studying' the answer is almost always yes
- William Tutte (1917-2002)
- How to Solve It
- Students try to memorize rather than understand! Who knew! (everyone)
- Summer Conferences
- A Celebration of Computer Science at Harvard in Honor of Harry Lewis's 70th Bday
April 2017
- So Was I
- I was at the March for Science on Saturday
- Will talk about Harry Lewis 70th bday conference later but for now- that was then/this is now
- Understanding Machine Learning
- Alice and Bob and Pat and Vanna
- What is William Rowan Hamilton know for- for us? for everyone else?
- A Bridge Too Far
- Proving Langs not Regular using Comm Complexity
- William Rowan Hamilton- The Musical!
March 2017
- Parity Games in Quasipolynomial Time
- The Dagstuhl Family
- If you want to help your bad students DO NOT give an easy exam
- NP in ZPP implies PH in ZPP
- Other fields of math don't prove barrier results- why do we?
- The Beauty of Computation
- why are regular expressions defined the way they are
- International Science
February 2017
- Should we learn from the Masters or the Pupils (Sequel)
- Ken Arrow and Oscars Voting
- The benefits of Recreational Mathematics
- Liberatus Wins at Poker
- Raymond Smullyan: Logician, Recreational math writer, Philosopher, passed away
- The Dichotomy Conjecture
- The Hardness of Reals Hierarchy
- We Are All Iranians
January 2017
- What was the first result in complexity theory?
- 60 years of Eric and Mike
- My once-every-four-years Presidential Quiz/how should quizes work in the e-era?
- Infinite Series and Markov Chains
- My REU program/REU's in general/Flyers? Why do some Transcripts...
- Guest Post about the first Women in Computational Topology (WinCompTop) Workshop
- Babai Strikes Back
- Learning About Learning
- Predictions for 2017
2016 101
December 2016
- Complexity Year in Review 2016
- Hidden Figures
- Moneyball for Academics
- The very first Ramseyian Theorem
- Freedom of Speech
- Guest post by Samir Khuller on Humans, Machines, and the Future of Work (a workshop)
- Fixing the Academic Job Market
- A students unusual proof might be a better proof
- Guest post by Samir Khuller about Visiting the Simons theory Inst for Computing
November 2016
- A Few Interesting Computer Science Papers
- Music Theory for Theorists
- Should I tell HS students that if they do well I'll write them a letter OR do I want them to ...
- Computer Science Academic Hiring
- Did you do research when you were an undergrad? Well.. it was a different time.
- Our Role and Responsibility
- And the winner is... Harambe
- Do We Still Need Great Minds?
- My chair wants me to post about.. Mohammad Haj wants me to post about.. I want to post about...
October 2016
- Get Ready
- Exaggeration is one thing but this is....
- Alternate Histories
- This university does not discriminate based on....
- 2016 Fall Jobs Post
- Ideal courses for a comp sci dept/I'm glad we don't do it
- Typecasting from Avi's 60th Celebration
- A Second Order Statement true in (R,+) but not (Q,+)
September 2016
- Give a second order statement true in (R,+) but false in (Q,+) or show there isn't one
- Who's Afraid
- Boris Trakhtenbrot (1921-2016)
- Academic Rankings Foster Competition
- Noam Nisan wins the Knuth Prize
- Why I Don't Believe in ET
August 2016
- I have consulted four times. Really!
- 1956 Was a Fine Vintage
- Chrisitan Comment on the Jesus Wife Thing misses the important point
- Predicting in Changing Environments
- Is the examiner being pedantic? Whats really going on here?
- Robin Hanson's Ems
- A Game Theory Conference! That sounds like fun!
- Seymour Papert (1928-2016)
July 2016
- GAMES/EC 2016
- The College Issues that are talked about/College issues that are important
- Snowbird 2016
- Solution to the Alice-Bob-Box problem.
- Solution to the infinite hat problem/a point/a new problem
- An infinite hat problem and later a point
- Is determining if a poly over a finite field is 1-1 hard? Sure seems so.
June 2016
- Excalibur
- There is now a Bounded Discrete Envy Free Cake Cutting Protocol!
- STOC 2016
- When does n divide a_n? The answer, though you already know it. The Point, though its not as strong as I wanted. Oh well.
- The Relevance of TCS
- Karp v Wigderson 20 Years Later
- When does n divide a_n in this sequence?
- Math Movies
- What do Evolution, Same Sex Marriage, and Abstract Set Theory have in Common?
- CCC 2016
May 2016
- New Ramsey Result that will be hard to verify but Ronald Graham thinks its right which is good enough for me.
- Theory Jobs 2016
- My third post on Gathering for Gardners
- Upfronts
- Does this leak information?
- The Challenges of Smart Cities
- Math lessons from the Donald Trump Nomination (non-political)
- Open Questions
- Some more bits from the Gathering for Gardner
April 2016
- Claude Shannon (1916-2001)
- Some short bits from the Gathering for Gardner Conference
- The Master Algorithm
- Its hard to tell if a problem is hard. Is this one hard?
- Who Controls Machine Learning?
- What Rock Band Name would you choose?
- It's All About the Jobs
- Are Perfect Numbers Bigger than Six initial sums of odd cubes (answered)
- Are perfect numbers bigger than 6 initial sums of odd cubes?
- The Machine Learning Turk
March 2016
- MohammadTaghi HajiAghayi on David Johnson
- Complexity versus Complexity
- Hilary Putnam passed away on March 13
- The Value of Shapley
- On Phillip Rogaway's The Moral Character of Cryptographic Work.
- David Johnson (1945-2016)
- When do we care about the constants?
- Changing This Ancient Art Into a Science
February 2016
- It works in practice, but does it work in theory (Pollard's Factorization algorithm)
- Primary Game Theory
- What is a `previous publication'?
- Posting Papers
- ∑{p≤ n} 1/p = ln(ln(n)) + o(1). read it here because....
- Test of Time Award- a good idea but...
- The Moral Hazard of Avoiding Complexity Assumptions
- Go Google Go
- Math questions that come out of the Iowa Caucus
January 2016
- We Still Can't Beat Relativization
- When do we stop giving the original reference?
- The Growing Academic Divide
- Is it okay to praise an article or book in an article or book?
- A limit on the DFA-CFG divide for finite sets
- A question in Formal Lang Theory about Size of Desc of Languages.
- Rūsiņš Freivalds (1942-2016)
- Predictions for 2016
2015 103
December 2015
- Complexity Year in Review 2015
- Guns and Crypto
- Blog Followers
- Simons and Berkeley
- Ada Lovelace (1815-1852)
- crank math and crank people
- Moonshots
November 2015
- One more sign that a Journal is bogus. Or is it?
- Star Trek Computing
- A Silly String Theorem
- Is the word Quantum being used properly by civilians? Understood by them? You know the answer.
- A Primer on Graph Isomorphism
- Looking forward to the GI result
- Computation and Journalism Part 2
- Conference on Computation and Journalism (Part I)
- George Boole (1815-1864)
October 2015
- S. Barry Cooper (1943-2015)
- A human-readable proof that every planar graph is 4.5-colorable
- Complexity Blast from the Past
- Amazon going after fake reviews but mine is still posted
- 2015 Fall Jobs Post
- Moore's Law of Code Optimization
- Randomness by Complexity
- Is Kim Davis also against Nonconstrutive proofs?
- Cancer Sucks
September 2015
- Venn Diagrams are used (yeah) but abused (boo)
- 21st Century Problems
- When did Mathematicians realize that Fermat did not have a proof of FLT?
- The Theorems Conference
- An Open(?) Question about Prime Producting Polynomials Part II in 3-D!
- Designer Chips
- An Open(?) question about prime-producing-polynomials
- Whiplashed
August 2015
- Two candidates that I want to see run for Democratic Nomination
- Pacm
- Interesting properties of the number 24 on someone's 24th wedding anniversary
- Crowdsourcing the Truth
- Have we made Progress on P vs NP?
- What is Theoretical Computer Science?
- Ways to deal with the growing number of CS majors.
- How hard would this cipher be for Eve to crack?
- 17 candidates, only 10 in the debate- what to do?
July 2015
- Explain this Scenario in Jeapardy and some more thoughts
- Explain this Scenario on Jeopardy
- New Proof of the Isolation Lemma
- Hartley Rogers, Author of the first Textbook on Recursion Theory, passes away
- Microsoft Faculty Summit
- Is there an easier proof? A less messy proof?
- Will Our Understanding of Math Deteriorate Over Time?
- Does Bob Deserve the lavish acknowledgement: A problem in Logic
- Goodbye SIGACT and CRA
June 2015
- When do we care about small improvements?
- Changing STOC
- Learning from teaching a HS student Schur's theorem on change
- FCRC Complexity
- STOC Business Meeting
- First issue of SIGACT news where I wasn't the editor. But...
- A Metric Group Product
- The city where the book publishers resides is Funkytown!
- Langs with provably bigger CFG's then CSG's
- Award Season
May 2015
- Who wins this bet?
- John Nash (1928-2015)
- An Intentional and an Unintentional teaching experiment regarding proving the number of primes is infinite.
- Theory Jobs 2015
- Fiftieth Anniversary of the Publication of the seminal paper on Computational Complexity
- The law of the excluded middle of the road republicans
- The Virtuous Cycle
- Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.
April 2015
- Is Logarithmic Space Closed Under Kleene Star?
- Advice on running a theory day
- Fifty Years of Moore's Law
- The New Oracle Result! The new circuit result! which do you care about?
- PH Infinite Under a Random Oracle
- Baseball is More Than Data
- FCRC 2015
- Two cutoffs about Warings problem for cubes
- Which of these stories is false
March 2015
- Intuitive Proofs
- News Aplenty
- Which mathematician had the biggest gap between fame and contribution?
- Feeling Underappreciated
- Has anything interesting ever come out of a claimed proof that P=NP or P ≠ NP?
- Quotes with which I disagree
- Guest Post by Thomas Zeume on Applications of Ramsey Theory to Dynamic Descriptive Complexity
- (1/2)! = sqrt(pi) /2 and other conventions
- Leonard Nimoy (1931-2015)
February 2015
- Selecting the Correct Oracle
- Eliminate the Postal Service
- And the Winners Are...
- Stephan Colbert, Jon Stewart, Andrew Sullivan, William Gasarch
- Richard Hamming Centenary
- Pros and Cons of students being wikiheads
- Computers Turn Good and Evil
- Less elegant proofs that (2n)!/n!n! is an integer
January 2015
2014 111
December 2014
- 2014 Complexity Year in Review
- Undergraduate Research
- The NIPS Experiment
- Joint Center for Quantum Information and Computer Science
- The Ethics of Saving Languages
- Godel and Knuth Prize Nominations due soon. Which would you rather win? Or ...
- Favorite Theorems Recap
- Cliques are nasty but Cliques are nastier
November 2014
- Guest Post about Barbie `I can be an engineer' -- Sounds good but its not.
- A November to Remember
- A Fly on the wall for a Harvard Faculty meeting: Not interesting for Gossip but interesting for a more important reason
- From Homework Solution to Research Paper
- Non controversial thoughts on rankings
- George Dantzig >= 100
- Favorite Theorems: Circuit Lower Bounds
- A few more notes about Sipser and Sipser-60th
October 2014
- Metrics in Academics
- Sipser Symposium
- Guest Post by Dr. Hajiaghayi: A new way to rank departments
- MSR SVC Letters
- Martin Gardner Centennial
- The Curious Case of NP and NEXP
- Luddite or not?
- 2014 Fall Jobs Post
- The Complexity of NIM. Open?
- Favorite Theorems: Multilinear Circuits
September 2014
- Dagstuhl on Algebra in Computational Complexity
- MikeFest
- Typecasting in Dagstuhl
- Goodbye MSR-SVC
- Gentry and Lurie and Zhang can say they are geniuses without bragin'- MacArthur Geniuses
- Maryland Theory Day October 10!
- Richard Lipton Wins Knuth Prize
- Beyond the Commodity
- A Statistical oddity ?
- Favorite Theorems: Quantum Interactive Proofs
- How hard is changing fields? Ask Sheldon!
August 2014
- Sixteen Years in the Making
- A Deadly Side of Complexity
- Turing's Oracle
- Complexity versus Algorithms: The FOCS Challenge
- Favorite Theorems: Limited Independence
- Subhash Khot wins Nevanlinna
- Questions that arose teaching High School students crypto
- The n^{1/3} barrier for 2-server PIR's broken! A lesson for us all!
- How I know Moneyball is a true story. Do we clean up theorems and life too much?
July 2014
- How NOT to bet
- The Change Problem and the Gap between Recreational and Serious Mathematics
- Need some book reviewed- faster than usual
- The Burden of Large Enrollments
- Elfdrive
- What to call the top and bottom part of (n choose k)
- Is there a word for the top part of a binomial coefficient?
- Favorite Theorems: Compressing the Local Lemma
- Four Centuries of Logarithms
June 2014
- 3000 lunches
- Computer Dating
- How many ways can you make change of n cents?
- Favorite Theorem: PCP Simplified
- Ref/info request for an obvious appraoch to GI
- CCC 2014
- Wassily Hoeffding 1914-1991
- Fair question? Trick question?
- Do you support CCC's declaration of Ind? If so...
- STOC 2014
- Law of small numbers and letters
May 2014
- Forgotten but not Lost in a Mapless World
- Review of People, Problems and Proofs By Lipton and Regan
- Theory Jobs 2014
- ''4col \le 3col is counter-intuitive and makes me sad'' NOT ANYMORE!
- Losing the Middle
- How should qualifying exams and courses work
- 1984 + 30
- Every Theory Grad Student should know...
- (IEEE) Conference on Computational Complexity
- Favorite Theorems: Equilibrium
April 2014
- The Big bang Theory hits close to home
- Libraries Without Books
- Changing the ORDER you teach things in might help A LOT
- Announcements
- Should you reveal a P = NP algorithm?
- Factorization in coNP- in other domains?
- Favorite Theorems: Extended Formulations
- How free is Randomness?
- How I learn a result
- I am Bill Gasarch
March 2014
- Should We Have a TCS Ethics Board?
- The answer is either 0,1, or on the board
- Spring Breaking at Dagstuhl
- Leslie Lamport wins Turing Award!
- Cosmos from Generation to Generation
- Why do we think P NE NP? (inspired by Scott's post)
- Favorite Theorems: Unique Games
- Why are there so few intemediary problems in Complexity? In Computability?
February 2014
- Why Become a Professor
- When is a paper public? When is anything public?
- Analog Adventures
- Maryland looking for a Lecturer/Who teachers your intro courses?
- IEEE and the Conference on Computational Complexity
- Superbowl underdogs and overdogs
- Favorite Theorems: Connecting in Log Space
- Contribute to the Martin Gardner Centennial
January 2014
- Snow Days
- Fermat's Last Theorem and Large Cardinals. Really!
- What will we wrought?
- We don't care about Ballroom Dancing. Should we?
- Favorite Theorems: Introduction
- A short History of Crypto
- Is Traveling Salesman NP-Complete?
- Tell me more about Alice and Bob
- Two cheers for the Pardon of Turing. But not three.
2013 108
December 2013
- 2013 Complexity Year in Review
- To Write, or Not to Write, That Is the Question
- Our Journal is 99 44/100 percent pure!!
- Security Changes
- Analogs between Quantum Computing and Parallelism
- Approximate Computing
- Inventions are Non-Commutative: Amazon vs Amazon
- Bitcoins Revisited
- Global Warming and the Axiom of Choice
November 2013
- The Institute for proving Graph Isomorphism is in P
- The New Patrons
- Local Reductions
- Four answers to the Recip problem
- A problem on Reciprocals
- A Theorist Goes to SOSP
- My Pope Number is 2: The Smaller World Hypothesis
- Andrzej Mostowski (1913-1975)
October 2013
- University of Maryland Job Posting Mentions Quantum Computing explicitly!
- Science and Humanities
- Teaching without a net
- 2013 Fall Jobs Post
- Who controls what is taught- the dept or the students?
- Shut Down
- P vs NP is Elementary? No-- P vs NP is ON Elementary
- Celebrating Maths in Oxford
September 2013
- Long Tails and Fat Heads
- Complexity and FOCS
- Dealing with Death
- Crystal Math- What NUMB3RS and BREAKING BAD both get wrong
- STOC CFP still delayed- but I was asked to pass this along
- Tldr
- Did YOU think the NSA could factor fast?
- Cryptography and the NSA
- T/F - No Explanation needed VS T/F-Explanation needed.
- Myhill Nerode versus Pumping Lemma
- Types of questions for exams
August 2013
- The Dream
- What are Galois Games?
- P = NP and the Weather
- When Lance was 10 years old..
- Flash Gordon
- How much Trig does your governor know?
- Don't Have an End Game
- Longest time between posing a math problem and it being answered?
- Why is Multiplication Hard?
July 2013
- Certifying primality in a CONSTANT number of operations
- Ph.D. Attrition
- I gave a poster session at Erdos 100- so how did it go?
- A(nother) nice use of Gen Functions
- DUMP YOUR TABLES! (the moral of my story that started with a hat problem)
- A problem and later a story and a point.
- Combinatorics use to not get any respect. But because of Erdos...
- AltaVista versus Google
- Computability in Europe
June 2013
- Friends Don't Let Friends Carpool
- Quantum Tecniques/Gen Functions- don't be afraid of new techniques
- Automate Me
- Fraud or not ?
- The Internship
- STOC: Some NON-radical ideas
- Complexity Typecast
- STOC is Burning
May 2013
- The High Quality Research Act
- Theory Jobs 2013
- Quantum Computing Fast and Slow
- Do you KNOW how you KNOW what you KNOW? I don't KNOW.
- The MOOCs Degree
- Mother's Day Math
- GPU Computing
- Are you smarter than a fifth grader? I'm not.
- Map Coloring Revisited
- Computer Assisted Proofs- still controversial?
April 2013
- Ideas in Search of a Blog Post
- Oh, I remember/recorded/DVRed it well
- The Golden Ticket
- Post Mortem on an April Fool's day joke
- You should apply for STOC and/or CCC travel money (students)
- Technology and Jobs
- Is the rule of threes a meta-urban legend?
- Gary Miller to Receive the Knuth Prize
- A nice case of interdisciplinary research
March 2013
- Counting Descriptions- a ``new'' complexity class
- A Century of Erdős
- The Slot Machine Theory of Paper Submissions
- Will they use EasyPope to pick the Pope in 2050?
- Goodbye Old Friends
- Turing Award to Shafi and Silvio
- What if they gave an exam and nobody came?
- Opera and MOOCS
- Do we ever NEED the adv pumping lemma for Reg langs?
February 2013
- Our Government at Work
- Enos, Oona, sqrt(3), and Aaronson
- Interruptions
- Are most lower bounds really upper bounds?
- Beauty and Science
- The Complexity-STOC Bonanza
- Proving DFA-langs closed under concat and * without using equiv to NDFA's
- Postdocs in Computer Science
- The (il)logic of fandom
January 2013
2012 132
December 2012
- 2012 Complexity Year in Review
- Flash Fill
- Goodstein Sequences (Its his 100th birthday!)
- The Fiscal Cliff
- Book review column
- Where is the youth of TCS/Market Eq/Guest Post by Vijay
- Too Much Competition?
November 2012
- App Love
- Inverse Closure Problem
- Recursion Theorem follows from Church-Turing
- A Simple PSPACE-Complete Problem
- If GASARCH Tweeted what would he tweet?
- Fifty Years of Computational Complexity
- Andrew Goldberg guest blog on new max flow result
- Produce or Perish
- Random thoughts on the election
October 2012
- Sandy Extension
- Fall Jobs Post
- Planarizing Gadgets for Perfect Matching do not Exist!
- Song of the Complexity Classes
- Short Announcements
- Dagstuhl Typecast
- Matching Nobel Prizes
- Why Does College Cost So Much?
- Theory Day. How to get the word out on this and other events?
- Cruel XOR unusual Punishment
- Close to Genius
- Quantum Workshop
September 2012
- Things a Complexity Theorist Should Do At Least Once
- A new kind of Spam
- Poset Games are PSPACE-complete
- Theory Conferences Galore
- Imagining Imaginary Probabilities
- Max Flow
- Some quantum Stuff
- The Time of Research
- Theory Day at UMCP Oct 24
- Should we learn from the Masters or from the Pupils?
August 2012
- The Net or the Jet
- Neil Armstrong, Ray Bradbury: The future is not what we thought it would be
- Knuth Prize
- Ten Years of the Complexity Blog
- Fellow blogger Abie Flaxman named Top Innovator!
- Is the Turing Test Still Interesting?
- Book Review Column (a bit late)
- Another Algorithmic Market Failure
- My take on the Olympics
- Moocs
July 2012
- A natural function with very odd properties
- Six Questions about unnatrual and natural mathematical objects
- The Combinatorics of Batman
- CCC12- post 4 of 4- Misc Info.
- CCC 2012- Post 3 of probably 4
- CCC 2012: Post 2 of n
- CCC12: Post 1 of n
- North Carolina tries to legislate science
- Why is it called the Turing Award?
June 2012
- Instance Compression
- Transitions
- Alan Turing (1912-1954)
- The Ketchup Problem
- Name My Book
- Do 50-1 longshots in the Kentucky Derby ever come in?
- Fortnoy's Complaint
- A new bound on 3-hypergraph Ramsey Number! Why wasn't it discovered earlier?
- Mihai Pătraşcu (1982-2012)
- Which Books to Keep?
May 2012
- 17x17: Paper that solved it available!/A contest inspired by it!/NPC result inspired by it!
- Theory Jobs 2012
- STOC 2012- workshop and honored talks
- STOC Business Meeting
- Meetings/Conferences/Workshops/Seminars- whats in a name?
- Gödel Prize
- Wall Street Complexity
- So THATS why the 17x17 challenge was so hard. Or maybe not.
- Paying to Publish
- Is it well known that we need to redefine well known?
- Microsoft saves the Yahoo NY Researchers
- Berkeley Wins the Simons
April 2012
- Is Moore's Law Good for CS?
- Hanan Samet wins Kanellakis Prize!
- I left Push Down Automata out of my class and learned some things!
- CS in the Sunshine State
- How important is the PROOF of Cooks theorem for my ugrad class?
- Some Announcements
- ACM/IEEE Curriculum 2013
- Unique Golf Winners
- I'll be on that list until the day I die. Or later.
- Guest post on Tom Cover by Yoav Freund
- We Think Like Our Fields
- Trick question or Stupid question?
March 2012
- The Value of an Academic Publication
- Sanjeev Arora wins ACM-Infosys Award
- "Math was a mistake- I made it too hard"
- What is an Elegant Proof?
- David Waltz (1943-2012)
- A Busy Time of The Year
- Heading South
- Intel Science Talent Search
- Judea Pearl wins Turing Award
- How do legit fields of knowledge decide between competing theories? How does Astrology?
- March Madness
- Scott wins the Waterman
- When a+b is harder than b+a
- The Internet of the Present
- Turing's Titanic Machine!
February 2012
- The Erdos- de Bruijn theorem
- Nash and the NSA
- Is 99.8% Secure Secure?
- The Envelope Please
- Presidents Day Poll- what does the youth of american think about....
- Aggie for a Day
- People solve math problems for the prize money! NOT!
- Sloans and More
- Barney the Evil Dinosaur
- STOC 2012 accepts are posted
- The 17x17 problem SOLVED! (also 18x18)
- Competition
- Why do we have awards?
- Dusting off my bookshelf I find a book on FORTRAN
January 2012
- A result of Specker in Recursive Combinatorics
- Guest post on ITCS by Chazelle
- Ernst Specker (1920-2011)
- What should we do?
- Teaching an Honors Section of Discrete Mathematics
- How important are the Fib numbers in math? in Nature? In History of Math books?
- The Information Flood
- Being Random and Trivial in Dagstuhl
- The Conjunction Paradox
- Rank these possibilities by probability
- Starting the Year with Turing
- Is there a NICE gadget for showing PLANAR HC is NPC?