The Curious Engineer

Computational Complexity

2005–2011

1,461 posts

← 2002–2004 2012–2026 →

2011 134

December 2011

  1. Complexity Year in Review 2011
  2. Game Changers
  3. Romney vs. Aaronson
  4. Algorithmic Driving
  5. Solution to the reciprocals problem
  6. Is this problem too hard for a HS Math Competition
  7. A Great Time to be a Computer Scientist
  8. What is a Breakthrough?
  9. Probability
  10. Analysis of Boolean Functions blog/book (Guest post by Ryan O'Donnell)

November 2011

  1. Matrix Mult (you heard it here... third?)
  2. The Death of Complexity Classes?
  3. The Jobs Bio
  4. Short Bits
  5. Are these journals real?
  6. Penn State
  7. My response to the Gasarch P vs NP poll
  8. Making Money the (Computationally) Hard Way
  9. The Annual Fall Jobs Post
  10. Journals

October 2011

  1. The Digital Random Bit Generator
  2. John McCarthy (1927-2011)
  3. It's Open Access Week
  4. The Cup Holder Principle
  5. Theorems that are impressive at first but then....
  6. Teaching PCPs to Undergrads
  7. Dennis Ritchie (1941-2011)
  8. If Bill Tweeted what would he tweet (Steve Jobs Edition)
  9. More than East and West
  10. Steve Jobs 1955-2011
  11. If you find a mistake in someone elses paper you should....
  12. What is Random?

September 2011

  1. Bibliographies
  2. A candidate for a new Millenium Problem
  3. Moneyball
  4. Mahaney's Theorem
  5. Where do theorems go to die?
  6. Conferences Again
  7. Happy Constitution Day
  8. Conventions in Math- just to make the rules work or more?
  9. Imagine
  10. Guest Post on Conference Locations
  11. Next in the sequence
  12. Knowing some History is a good thing- Why?
  13. The Anti-Privacy Generation

August 2011

  1. Do we use Technology before its perfected? Should we?
  2. Patrick Fischer (1935-2011)
  3. The Not-So-Simple Path
  4. What inspired you to work on... whatever you work on?
  5. The Future of Universities
  6. An application of Ramsey Theory to Proving Programs Terminate
  7. My Cruise Vacation
  8. What is a simple function?
  9. If I was a tweeter (is that a word?)
  10. Does STOC/FOCS take simple-nice-ideas papers? A one-element case study

July 2011

  1. The Problems of LaTeX
  2. Why did 1+1=2 take Russell and Whitehead 300 pages?
  3. Delay for a Postdoc
  4. Looking for people to review books for my column
  5. Disproving the Myth that many early logicians were a few axioms short of a complete set
  6. Math, the Universe, and Everything: Max Tegmark's Interpretation of reality (guest post)
  7. A slightly diff take on Lipton's use of Ramsey's Theorem
  8. FOCS Accepts
  9. Scooped by 400 years
  10. The Quantum Tivo

June 2011

  1. The Sputnik Moment
  2. Math on FUTURAMA and LAW AND ORDER:CI
  3. FCRC 2011. Part 2 of... probably 2.
  4. Blog Redesign
  5. Creating an Email System at Cornell
  6. I am conducting a NEW POLL on P vs NP
  7. Theory Jobs 2011
  8. FCRC 2011. Part I of... maybe I, maybe more.
  9. New Complexity Vidcasts
  10. Talks I Missed
  11. An Update on Impagliazzo's Worlds
  12. The Longest Day
  13. A Valiant Weekend
  14. Partioning Students

May 2011

  1. RaTLoCC (Ramsey Theory in...)
  2. 75 Years of Computer Science
  3. Cell Phones versus Drunk Driving
  4. Is Computer Science Cool Again?
  5. Håstad to receive the 2011 Gödel Prize
  6. On demand Publishing (guest post)
  7. President Regan (not Reagan)
  8. FCRC Early Registration May 16
  9. Those Happy Samoans
  10. How has the STRUCTURES, OH- I mean CCC Conference changed: Lets look at the Call For Papers
  11. Forty Years of P v NP

April 2011

  1. How important is Teaching Experience on the job market (guest post)
  2. Don't Blame the Tech
  3. Ravi Kannan wins the Knuth Prize
  4. What did Banach's Wife think of the Banach-Tarski Paradox?
  5. Choosing an Undergrad School
  6. Going off topic in class: I think it worked--- this time
  7. Workshop/Award/Conference/Who wants to review books?
  8. Do You Know the Way to San Jose?
  9. The Mathematics of Huging my great Niece Jordan
  10. Kanellakis and Grace Murray Hopper Prizes
  11. A New Proof of the Nondeterministic Time Hierarchy
  12. The Complexity of the Soul

March 2011

  1. Phillipe Flajolet passed away
  2. An unusual Voting Scheme
  3. How I'm Spending my Spring Break
  4. Travel Support for Students going to STOC 2011
  5. Update on 17x17 problem
  6. TAMC conference accepts are out/What does a name tell you about a general theory conference?
  7. Computer Science Takes Over
  8. STOC 1989
  9. Les Valiant wins the Turing Award
  10. Three Questions that I think Watson would have trouble with
  11. Greetings from Porto
  12. A good article on how science is publicized gets the science wrong

February 2011

  1. Interesting Math related to the Unexpected Hanging Paradox
  2. What I Tweeted
  3. Aaron Sterling starts his own blog!
  4. Lincoln's Dog-Tail question (in honor of Presidents Day)
  5. CCC 2011 papers- you heard it here first
  6. If I tweeted here is what I would tweet
  7. Can we Innovate without Producing?
  8. PROS and CONS of being on a Program Committee
  9. STOC 2011 accepte papers posted.You heard it here...12th!
  10. The Theory Postdoc Culture
  11. All the news that fit to tweet

January 2011

  1. Is Cheminformatics the new Bioinformatics? (Guest Post by Aaron Sterling)
  2. The Ideal Conference
  3. Why My Kids Trust Wikipedia
  4. Does Tiger Woods know what a Venn Diagram is?
  5. Coloring Maps
  6. Are you a Ringer? A Reverse Ringer?
  7. LICS and TAMC call for papers
  8. The Enduring Legacy of the Turing Machine
  9. What is a breakthrough? Lets have an intelligent discussion!!!!!!

2010 191

December 2010

  1. Complexity Year in Review 2010
  2. America's Most Important Algorithm
  3. BREAKTHROUGH in algorithms: Improved algorithm for Metric TSP!!!!!!!!
  4. Low, Superlow, supersuperlow sets, and Paywalls
  5. Math- Old School
  6. 46 free lunches!
  7. Do Uniform Lower Bounds Matter?
  8. A BREAKTHROUGH result on density and 3-AP's

November 2010

  1. Complexity as Friction
  2. Game Theory, Terrorism, Hardness and SAT Solving
  3. Erdos Distance Problem SOLVED!
  4. Eleven Tweets from GASARCH
  5. Is Ryan's Theorem Only Interesting to Complexity Theorists?
  6. A Problem with Wikipedia and the Next Best Thing to Winning a Godel Prize
  7. Dr. Scott Goes to Washington
  8. A Breakthrough Circuit Lower Bound
  9. The FOCS Experience
  10. A non rigorous proof technique
  11. The revolution will be DVRed
  12. By Any Other Name Would Be Just As Hard

October 2010

  1. Advice on getting connecting to the community (guest post by Daniel Apon)
  2. Do conference build community? (joint post)
  3. FOCS Part II
  4. FOCS Part I
  5. New York Area Theory Day- Nov 12, 2010
  6. Will there be a 50th CCC? Will you be there?
  7. A Note from the Trenches (Guest Post from Michael Mitzenmacher)
  8. My Trip to Denmark
  9. Benoît Mandelbrot (1924-2010)
  10. How hard is this problem?- I ask this non-rhetorically
  11. Two Candidates for an Ig Noble in Mathematics
  12. The NSF Takes Shape
  13. Noble and Ig Noble Prizes
  14. Partha Niyogi (1967-2010)
  15. The Annual Fall Jobs Post

September 2010

  1. NRC Rankings
  2. Review of Lipton's Book-Blog/Review of Goldreich and Arora-Barak/New Book Review Column/Do you want to review?
  3. The Theory Social Network
  4. Theorems that are less interesting because they are more interesting
  5. The World in Its Own Terms
  6. Joseph B Kruskal passed away (Guest post by Clyde P Kruskal)
  7. Should You Mentor High School Students?
  8. How Can You Spend $150 Million?
  9. FOCS Travel Support (Guest Post by Paul Beame)
  10. A Mathematical Urban Legend
  11. The Rubik's Cube Conjecture PROVEN! (Do we care?)
  12. How to Write Up Major Results
  13. CS Happenings
  14. Intelligent questions about the alleged P NE NP proof

August 2010

  1. Report from Barriers II Part 1
  2. New Institute for Theory of Computing
  3. Theory Journals
  4. Cryptography if P = NP
  5. ***SORELLE*** PHD!!/Workshop on Boolean Threshold Functions/NSF program
  6. NEW math on Futurama
  7. Is Scheduling a Solved Problem? (Guest Post)
  8. Comments
  9. NSF Updates
  10. Spielman Receives the Nevanlinna Prize
  11. Today is Paul Turan's 100th Birthday!
  12. My last post on the alleged P NE NP paper
  13. But This One Is Different...
  14. P vs NP vs IEEE (Guest post by Paul Beame)
  15. Factoring in P ?
  16. That P ne NP proof- whats up with that?
  17. The Solution to the Mark-Betty Game
  18. I want your intuitions on this, so the less you know the more I want you to post

July 2010

  1. What is the complexity of these problems and metaproblems?
  2. This Post is Quite Different from any you've ever read!!
  3. A Seventh Mil. Problem
  4. CRA Snowbird Part II
  5. CRA Snowbird Part I
  6. Do you want to review a book
  7. Factors for getting a job- Arbitrary, random, and complex
  8. How I Find Homework Problems
  9. Sparse problems in NP thought to not be in P
  10. GCT Workshop (Guest Post by Josh Grochow)
  11. Can you ever be denied Full Prof? Can you ever really fail a PhD defense.?
  12. Conflicts of Interest
  13. Drowning in Data
  14. Theory Happenings
  15. Is this solution cheating?

June 2010

  1. Broader Impacts
  2. The P vs NP quiz Show. NP! NP! NP!
  3. The Lefthanded Latina Lesbians in Algebraic Topology Workshop
  4. Talking about your work with a layperson
  5. The Future of STOC
  6. Foundational ... or simply a curiosity (Guest Post by Vijay Vazirani)
  7. CCC 2010
  8. László Lovász wins Kyoto Prize
  9. Alternative Careers for Logicians
  10. News from Cambridge
  11. Another post on Martin Gardner
  12. Whats your Game Mr. Bond- The sequel!
  13. Sims Complexity
  14. STOC and EC and Complexity, Oh My
  15. Conference Acceptance Rates
  16. Advice for an Engineer
  17. Avner Magen (1968-2010)

May 2010

  1. 24: Really Bad Game Theory, technology, and science
  2. The Structure (or lack thereof) of Data
  3. Complexity and Computability
  4. Parallel Thinking
  5. The Life of Martin Gardner 1914-2010
  6. The End of Numb3rs
  7. Teaching for the first time: SUBRUK's story
  8. What should be in an automata course: Two views based on recent experience
  9. Boycotting Arizona
  10. When to go Low Tech
  11. Goodbye PostScript
  12. Knowledge is Power!
  13. What did he know and when did he know it?
  14. Which Name Do You Play For?
  15. NSF at 60
  16. Is Complexity Math or Science?
  17. COLT and CCC no longer take papers in ...
  18. Ralph Kramden: Your wait is over! 3D-TV is here!
  19. Gadget Love
  20. Guest Post on Robin Milner who passed away recently

April 2010

  1. The Base of Computational Complexity
  2. STOC/CCC/EC/THEORYDAY/GRANTS
  3. A possible NP-Intermediary Problem
  4. Trading Money for Computation
  5. Google VS Experts VS readers VS Bing
  6. A Post on the Post Post
  7. P and NP: A Short Movie
  8. Is there a pangramic palindrome?
  9. Life without Flying
  10. Is Guessing a good idea?
  11. The Pad
  12. New Constructive Aspects of the Lovász Local Lemma
  13. Tom L DVD and Birthday and You Tube and...
  14. Choosing a Graduate School
  15. Sum of squares: How much to cheat?
  16. What Makes a Lecture "Distiguished"?
  17. Baseball violates the rules of mathematics!!
  18. But seriously now folks- what do you make of barrier results?
  19. Finding the Right Model
  20. What Does It Meant to be Published?
  21. SIGACT Social Networking
  22. Lets Prove Something instead of proving that we can't prove something

March 2010

  1. SIGACT Awards
  2. Traveling Too Much
  3. Book Review Column AND request for reviews
  4. Turning down a Fields Medal is eccentric, turning down the Millennium Prize is INSANE!
  5. Laci Babai Turns 60
  6. What I'm Doing Over Spring Break, Part I
  7. Stoc Travel Support/WELCOME BACK LANCE!
  8. Notes to My Dad
  9. Unique Games Redux
  10. A prospective Theory Blogger wants your input (Guest Post)
  11. Repost on Turing and Wasserman- lets talk about...
  12. Central Website for FOCS as a whole (guest post)
  13. Theorems that you simply don't believe
  14. Turing Award and Waterman Award and the variety of our field
  15. HW policies: PROS and CONS
  16. A HW policy- MORAL due date.
  17. Special Issue of TOC in honor of Rajeev Motwani
  18. Can The Hill Cipher ever be used?
  19. Knuth Prize for 2009: David Johnson
  20. CCC 2010 papers posted (I know- Old News)

February 2010

  1. Is Math too hard?
  2. Doing it OLD SCHOOL!
  3. What is in MY automata theory course/What should be
  4. What is more importantt: Automata Theory or Crypto?
  5. A problem about Graph Partitions (guest post)
  6. Kurt Mehlhorn to receive EATCS award
  7. e to the pi vs pi to the e
  8. Prediction on Presidents Day
  9. FOCS 2010 CALL FOR PAPERS is out!
  10. STOC and More
  11. What is an Elementary Proof?
  12. The more things change the more things change
  13. Time Space Tradeoffs for SAT- good resuls but...
  14. Naming and Ranking
  15. Travel Support for Grad Students who GOTO STOC 2010

January 2010

  1. Referees'''' reports
  2. Guest post on ICS 2010 (x of y for some x and y)
  3. The First pseudorandom generator- probably
  4. When is a theorem really proven?
  5. Job Postings
  6. Two Theorems this blog missed
  7. Should CCC2012 be at the North Pole?
  8. Do Innovative papers have a hard time getting into STOC and FOCS? I ask this objectively with no ax or teeth to grind.
  9. ICS I: snapshots (guest post)
  10. Guest Post on ICS 2010 (2 of 3)
  11. Guest Post on ICS 2010 (1 of 3)
  12. COLT and CCC
  13. DO NOT do this when choosing books for your class
  14. Axioms: What should we believe?
  15. Voting on Mathematical Truths: The Axiom of Det.

2009 249

December 2009

  1. 2009 Complexity Year in Review
  2. How to tell how good a TV show is
  3. What is an explicit Construction?
  4. A hard problem inspired by an easy problem
  5. Guest Post- Women in Theory Workshop
  6. Mild Request for Guest Posters.
  7. CCC deadline Dec 15, 2009! (not factorial)
  8. A Blog Sabbatical
  9. Whats your Game Mr. Bond? Nim?
  10. Is posting about 17x17 problem BAD FOR ACADEMIA?
  11. Dequantification
  12. Complexity Vidcast 3
  13. The Probability of P=NP
  14. Congrats to new ACM fellows
  15. 17x17: Comments on your comments
  16. Who Pays for Trips?

November 2009

  1. The 17x17 challenge. Worth $289.00. This is not a joke.
  2. Birthday Paradox Variance
  3. DIMACS at 20
  4. An undervalued Math Problem
  5. Citing Papers
  6. Laptops in Church?
  7. FOCS Videos
  8. A Prayer Book for the Internet Generation
  9. Rules about Blogs becaues Blogs RULE!
  10. Jobs
  11. Breaking Walls
  12. New York Theory Day
  13. Multi-Agent Biological Systems and Nat Algorithms Workshop (Guest Post)
  14. Is FACEBOOK the new email?
  15. Button Button
  16. Innovation
  17. Amir Pnueli (1941-2009)
  18. Really Liked Bertinoro- Ramsey Thing
  19. Report From Ramsey-Logic-Complexity Workshop

October 2009

  1. FOCS News
  2. Proud to be a Monomath
  3. FOCS Last Day
  4. FOCS Day 2
  5. FOCS Day 1
  6. FOCS Day 0
  7. Notes on Dagstuhl
  8. Need a Roomate for a conference?
  9. The Humbling Power of P v NP
  10. An unintentional Sociology of Blogs experiment
  11. List of books I want reviewed
  12. Typecasting Again
  13. Thanks for the Fuzzy Memories
  14. Bill and Lance's Excellent German Adventure
  15. Dagstuhl Day One
  16. The Molly Solution
  17. Complexity Vidcast 2
  18. Publicity for P versus NP
  19. The last Universal Mathematician was ???
  20. You are coordially invited... Why?
  21. Two Recent Complexity Books omit Mahaney's theorem- ovesight or wisdom?
  22. On Being Narrow
  23. The Journal Manifesto 2.0

September 2009

  1. The Journal Manifesto
  2. The IT Rules
  3. Debunking Proofs
  4. Inspiring a Love of Math
  5. My two cents on P vs NP
  6. Another Reason to goto FOCS: Theory Day!
  7. The Netflix Prize and the Sequel
  8. Why You Shouldn't Not Go to FOCS
  9. You Will All Work for Google
  10. Possibly Recruits for the Polymath Primes Project
  11. Announcing a New Blog: Silent Glen Speaks
  12. Fashionable Research
  13. Ambiguity
  14. The Mystique of the Open Problem
  15. Models versus Proofs
  16. An apology for Turing may be in the works
  17. Hiring at Univ of MD at College Park
  18. Interface Between Computer Science and Economics
  19. Is P=?NP ind of ZFC a respectable viewpoint?
  20. The End of Summer Classes (Guest Post)
  21. Musing from the Barriers Workshop

August 2009

  1. My last post on steretypes (I hope)
  2. CS and the Web of Knowledge
  3. The Status of the P versus NP Problem
  4. Why are the French Fair Game for ...
  5. A Busy Week
  6. The Hungarian Reputation foR Combinatorics
  7. An application of VDW theorem to Number Theory- is there a better proof?
  8. Request insights on future of the job market (guest post)
  9. What is the most interesting number ?
  10. What is the least boring number (NOT the usual paradox)
  11. Imre Simon Passed Away Recently
  12. How much credit should the conjecturer get? Is Conjecturer a word?
  13. Live from Russia
  14. Is Quantum the new Random ?
  15. Rump Sessions at Conferences
  16. Computer Go
  17. What To Do With the Little Theorems?
  18. Statistics for Fun and Profit
  19. Using the web you may run into self-reference
  20. Finding Primes
  21. Find the Number- again

July 2009

  1. The Singularity
  2. Are you a firstblocker or a lastblocker?
  3. QIP = PSPACE
  4. Whither to Post, Tweet or Facebook?
  5. Why go to conferences?
  6. Time for Computer Science to Grow Up
  7. Patenting P=NP
  8. California Nightmare
  9. Eccc
  10. The Moon and a Legend
  11. Complexity Wrap-Up
  12. Our First Complexity Vidcast
  13. Complexity Day 1
  14. A Complexity Proposal
  15. Icalp
  16. Will the real Adam Smith please stand up, please stand up, please stand up
  17. TARK vs. EC
  18. Speedup for Natrual Problems (Guest Post)
  19. Raking Up the Frequent Flyer Miles
  20. Pairs of Celebrities died/born the same day
  21. FOCS Papers
  22. Learn PCPs at DIMACS
  23. 2pi-day? Other holiday possibilities!

June 2009

  1. The NSF Annual Report
  2. Re-request/when to include a known proof in a paper?
  3. Tales of Two Theories
  4. Complexity Report from DNA 15
  5. Two requets: A sum and a reference
  6. Annoucing YATB (Yet Another Theory Blog)
  7. Sigact
  8. The Story of the Blog
  9. Nondeterministic Parallelism
  10. Do laypeople know what Prisoner's Dilemma is? Now they might
  11. Cond. Cvg Sequences in R^d AND real applications!
  12. Conference Proceedings should have final version in Journal! (Guest Post)
  13. Math on Kindle DX
  14. The Great Oracle Debate of 1993
  15. Can we make this problem FUN?
  16. Fifty Years of Mathmagic Land
  17. Are there any longstanding conjectures that ended up being false?
  18. Rajeev Motwani
  19. Not about STOC/Funny Stuff people have send me
  20. A Failure of Social Networks?
  21. Thoughts from STOC
  22. A Kolmogorov Complexity Proof of the Lovász Local Lemma
  23. Stoc

May 2009

  1. The Alpha
  2. Randomness in Madison
  3. Games from the Eco-Daughter
  4. Oracle Results are Good For You
  5. Raymond Smullyan's Birthday
  6. Get Your Stimulus Money Here
  7. Gödel Prize
  8. Is FKS and other Data Structure Algorithms actually being used?
  9. Lessons from EC
  10. Halt is Undecidable in Verse (YES, you've seen it before)
  11. The Quadratic Formula
  12. The Prime Number Theorem
  13. Shaving Logs with Unit Cost
  14. My Obligatory Star Trek Post
  15. Requst for Info on Prob Hypergraphs
  16. New URL Same Blog
  17. Doctor for Two Decades
  18. New York THEORY DAY 2009
  19. My Kindle
  20. My Publications
  21. A new way to educate the public
  22. Foundations of Complexity

April 2009

  1. Converse oF Clarke's famous quote
  2. International Spy Museum
  3. Information Overload
  4. AI in Jeopardy
  5. Vardi: Are Conferences Worth Fixing?
  6. Complexity Theory songs (repost)
  7. The Economy and Conferences
  8. Who Gives the Talk?
  9. NASA's Poll a Sham!!
  10. ACM Pubs
  11. Workshop on Theory and Many Cores
  12. Conference Accepts
  13. Traveling to Conferences
  14. Accessing Ladner
  15. Tom Lehrer turns 9*9 today!
  16. The Lance Effect
  17. Baseball is Back
  18. The Jack Schwartz Memorial
  19. Guest Blog by Clyde Kruskal on Jack Schwartz
  20. ToCT Launches
  21. The Letter

March 2009

  1. Submit and Forget
  2. Change we can believe in!
  3. Voting on the Web- Beware Colbert
  4. To Adopt or Not to Adopt
  5. Return to Berkeley
  6. Community
  7. The Putnam Exam: Some Thoughts
  8. The Presidential Binary Tree
  9. Which Awards are well known? Why?
  10. The Best or the Worst
  11. The Madhu Move
  12. Math on the Simpsons Last Night
  13. Skimming Journals
  14. Math Solves Problems
  15. Barbara Liskov Wins Turing Award!
  16. Watching the Watchmen
  17. Lets Congradulate Gerard Huet! (who?)
  18. Addresses
  19. Seeking an EASIER proof of s x s^2 theorem
  20. How much does it cost to produce an online Journal? Do I hear $0.00?
  21. Algorithms for All
  22. You Can't Separate the Art from the Artist

February 2009

  1. Conventional Wisdom
  2. Losing touch naturally was a good thing. Now...
  3. Proof-Ready Projects
  4. The FOCS Call
  5. Seeking the NON-Elementary proof of...
  6. The New Facebook Generation
  7. Movie Mistakes- or are they?
  8. A Great way to use a math blog
  9. Sloan Fellows
  10. The Office
  11. STOC Papers
  12. Baseball Families and Math Families
  13. Cleverness Squared
  14. How Big is a Trillion?
  15. Are results about actual constants interesting?
  16. The Ugly Proof
  17. New Blog on our blogroll: Be prepared to be blown away by BLOWN TO BITS
  18. Stimulating Science
  19. While I was Gone
  20. And you thought the STOC/FOCS deadline were pressure!

January 2009

  1. When to declare a problem is hard?/Constructive versions of Dilworth's theorem
  2. Random Thoughts on the Inaugural
  3. Prez Quiz ANSWERS and...
  4. Fooling Constant-Depth Circuits
  5. Presidential Trivia Quiz !
  6. Rightful Place
  7. The Dream
  8. Planes. Fellows. Power.
  9. Amitabh varshney graphics faculty at
  10. So You Think You Settled P verus NP
  11. Best Job?
  12. A Complete History of the LVDW conjecture
  13. Conferences Abroad
  14. Sorting a Partial Order
  15. SODA and Me
  16. I went to SODA 2009!
  17. Stephen Kleene: Not A Regular Guy
  18. Randomness in Voting

2008 253

December 2008

  1. 2008 Complexity Year in Review
  2. The Rooster
  3. Springer Open Choice
  4. No Good Deed Goes Unpunished
  5. Predicability in Movies: was there ever a case where...
  6. Have We Solved Spam?
  7. TEACH EVERYONE PROGRAMMING! (Guest Post)
  8. Prediction Markets Review
  9. A NIM-game and some possibly open problems
  10. Request for Grant Reviewers from NSF
  11. The Job Market
  12. How was New York Theory Day?
  13. Ingo Wegener (1950-2008)
  14. A job posting for THEORY-Univ of Michigan
  15. Science of Victory!
  16. Proofs Still Not Dead
  17. Quantum Leap/Quantum of Solace/What does Quantum mean anyway?
  18. How Many Sides to Your Error?
  19. Cellprobe complexity- Yao model still relevant?

November 2008

  1. Blatant Plugs
  2. The Flame
  3. Should tables be sorted? Yes but--- a question
  4. What is your best paper? Ambigous!
  5. Is the Medium the Message?
  6. Reflection on the old days- by Joseph Kruskal
  7. Secrets from the Future
  8. A "well known" theorem
  9. Monotone Sequence Theorem: literature thing
  10. My New Hybrid
  11. The Kakeya Conjecture over finite fields resolved! Why can't we resolve P vs NP?
  12. Barrington's Theorem
  13. STOC reminder- TODAY!/ NYU Theory Day
  14. A new logical fallacy
  15. The Terminal Man
  16. Random thoughts about the election
  17. Election Day
  18. Will fivethirdyeight.com use this poll?

October 2008

  1. Focs Wrap Up
  2. Election Special
  3. Math NAMES
  4. The Gossip Center
  5. Post-Lunch Highlights, Day 1
  6. Business Meeting
  7. Pre-Lunch Session
  8. Sampling FOCS
  9. Knuth Prize to Strassen
  10. Who to vote for?
  11. Academic Dominance
  12. Weird Sum/ith largest/Wallet-- revisited
  13. World Series at FOCS
  14. An interesting Summation
  15. Finding the ith largest of n numbers for i,n SMALL
  16. How Much is a Proof?
  17. Theory Day at University of Maryland
  18. The Fiscal Crisis
  19. Thanks for better upper bound. Still want better lower bound- On Comm Comp of MAX
  20. Patents and Copyrights vs Web Traffic (guest Post by Amir Michail)
  21. A Victim of the Internet
  22. Contradictions in Math-bad, in Political Pundits- Standard
  23. Expectation of Expectations
  24. The Unexpected Hanging Paradox-any seriosu math their?
  25. A minor but perhaps indicative failure of technology
  26. Go Sox
  27. When does Alice deserve to be a co-author?

September 2008

  1. Making People Fly
  2. comp Geom/MD Theory day/New Blog/Bond, James Bond
  3. An Accidental Theorem
  4. Markets and Polls
  5. How well do Academic Books Sell?
  6. Another Year, Another Genius
  7. The Communication Complexity of MAX: Open problem
  8. Sum-Product Theorems
  9. Dagstuhl Review
  10. Opening up the ACM Digital Library
  11. Fringe Science
  12. Some New Lower Bounds on actual VDW numbers
  13. Yahoo more popular than Google according to Google
  14. Another Dutch Defense
  15. SODA 2008 accepted papers list is out!
  16. Jogging on Trips
  17. Three sequences
  18. Tracking Trends in Computer Science
  19. Announcements
  20. I would bet on INTRADE that INTRADE will do badly picking VP Nominations
  21. The Big Aggregators

August 2008

  1. The Ultimate Wallet
  2. If a Hobby relates to your work, is it a Hobby?
  3. While I Was Gone
  4. What to teach in grad course in Comm Comp- some non-theorists in it
  5. A nice result, but not good for...
  6. Ways Scott could have gotten his question answered
  7. Acknowledging anonymous blog comments
  8. Amihood Amir more famous than Dick Cheney
  9. Olympic Markets
  10. AI Follows Theory
  11. Ridiculously hard proof of easy theorem
  12. Math Problems on vacation
  13. What is the probability that ...
  14. Discounted Time
  15. The Gaza Fulbright Story
  16. A Theory of Reductions?
  17. A Simple Heuristic
  18. Analysis in Complexity
  19. Complexity Special Issue

July 2008

  1. Psychological Proofs and Reverse CAPTCHAs
  2. Proceedings
  3. Rules for Success
  4. Movie Time
  5. Nick Reingold
  6. Vinyl Record Bowls
  7. A Nonconstructive argument about the election
  8. Open Math Problems easy to state to layperson
  9. The One Who Walked Away
  10. GAMES and Computer Science
  11. Topics for theory grad course for non theorists?
  12. An Interesting Summation- NOT new but raises some questions
  13. An interesting summation- new?
  14. Games
  15. Some NSF notes of interest
  16. Electoral Markets Map
  17. Attendence at CCC: We have no edge people
  18. Busy Conference Week
  19. Attendence at CCC I: History
  20. The Great Procrastinators
  21. A NEW Blog in Town-kdphd
  22. NSF and CACM

June 2008

  1. The Special Issue Debate
  2. Complexity Conference Wrap
  3. On being local on the local org comm.
  4. Podcasting from the Conference
  5. FOCS Accepts
  6. Seven Dirty Words
  7. ACM Awards Banquet
  8. Karp Wins Kyoto Prize!
  9. See you at CCC 2008!
  10. Guest Post on App of Ramsey to Constraint Satisfaction
  11. In my day...
  12. I am Iron Man
  13. Posting a SUBMITTED paper
  14. Working Outside Our Fields
  15. Complexity Zoo Poster
  16. Impressions of C++
  17. SODA 2009 Call for Papers- and a comment on it
  18. Journals and Information Obsolescence
  19. email: not as useful as it could be
  20. Nerds
  21. High Level Monographs- why?
  22. Outside In
  23. I will derive!

May 2008

  1. R-O-S-E
  2. Would you buy a math book for $160.00?
  3. Completeness Does Not Imply Complexity
  4. Gödel Prize
  5. Elsevier Happenings
  6. CCC2008/ ACM dissertation awards 2007
  7. Tough Math
  8. Final STOC Post
  9. STOC Business Meeting, Part I
  10. STOC Day 1
  11. Visioning Workshop
  12. Reminder: Register for Complexity 2008
  13. The Week Ahead
  14. Surveyed to Death
  15. The problem with making websites
  16. What is an application?
  17. Teaching Parallelism
  18. Electronic Commerce and Prediction Markets
  19. Any Questions?
  20. Vanished from the web- of more interest...
  21. If you find something online download it NOW
  22. Report on Sym for Lipton's 60th bday (guest post Ken Regan)
  23. The ID Conundrum

April 2008

  1. AAAC in Hong Kong
  2. Should Mahaney's theorem be taught in a complexity grad course for non-theorists?
  3. What would the best base be?
  4. If we had 12 fingers on our hands then Obama would be the nominee
  5. The Life of the Party
  6. What Happened to the Indians?
  7. Laptops in classroom and lectures
  8. Ketan Mulmuley Responds
  9. Facebook and Forums and Feeds, oh my!
  10. My First Grand Student
  11. The Revenge of Parallelism
  12. Complexity of Income Tax
  13. Eight (yes eight) math problems worth $1,000,000
  14. How to Prove NP Different from P
  15. Applying Math to politics
  16. ICALP and EC
  17. Applying Math to getting rides
  18. A Web 1.0 Guy in a Web 2.0 World
  19. If we didn't log on how much email would we get?
  20. An Analog Guy in a Digital World
  21. Two Israels
  22. Erik Demaine proves P=NP!

March 2008

  1. Opening Day
  2. Univ of MD Grad Student Visit Day
  3. Complexity Conf 2008 - CCC08- You can now REGISTER!
  4. An odd way to find good employees- it might work
  5. Deadline Extension for NSF Theoretical Foundations Grant Proposals
  6. Nine Billion Names
  7. The Life of David Gale
  8. Should a grad student use one offer for leverage at another school?
  9. The Broken Remote Problem
  10. Networking
  11. The Big Red Dance
  12. Abuse of Tagging System on amazon
  13. The Long Slog
  14. Why is PARITY not in AC_0 important?
  15. The Video King
  16. AI overhyped!!!!!!!!!!!!!!!!!!!!!!!!!!!
  17. Endorsements and Game Theory
  18. Visions in Theory Workshop
  19. Skipping Class
  20. Playing to Win

February 2008

  1. ToCT is a Go
  2. Ineffective Spam- or is it?
  3. When good recommender systems go bad!
  4. FOCS 2008 Call For Papers is available
  5. Outed by Amazon
  6. Compulsory Voting with Careful Consideration of Choices
  7. Why is Lance Lance and GASARCH GASARCH?
  8. Campus Tragedy
  9. More funny answers on math olympiad
  10. Engineering Challenges
  11. Valiant wins EATCS award
  12. There is no such thing as a sure thing
  13. Average Case versus Worst Case
  14. The Moment of Truth
  15. The Candidates on Science Funding
  16. Ten greatest Math Puzzles of All time- NOT
  17. Movie Mathematicians
  18. This years Turing Award: Model Checking
  19. WSEAS: A Greek Tragedy
  20. Short Cuts
  21. The Final Two

January 2008

  1. If you get a new result of interest with little effort...
  2. If 50 is the new 40 then is 100 the new 80?
  3. Announcement from source at NSF
  4. The Lance-Food Diet
  5. More on Graph Minors
  6. The End of TV as I Knew It
  7. Optimizing your vote
  8. Politics and The Blog
  9. Bobby Fischer (Guest Post by Ken Regan)
  10. Lance 2.0
  11. If you submitted a CDI proposal READ THIS
  12. Math books you can actually read
  13. Invited Post on Invited Speakers Website
  14. Today is Knuth's 70th birthday!!
  15. predictions for 2008 and beyond
  16. The Past and the Future in Song Form
  17. Graph Minor Theorem and Non Const Algorithms
  18. 2007 Complexity Year in Review

2007 159

December 2007

  1. Presidential Math
  2. Oral Homework
  3. The Twelve Days of Tenure
  4. A Bad Deal
  5. More on VDW over the Reals
  6. Bad News for American Science Funding/Good News for Australia Science Funding
  7. Complexity Theory Class Drinking Game
  8. An ill define question inspired by that HS question
  9. Funny Answers on a Math Olympiad (MD)
  10. Crypto problem inspired by politness
  11. Sending out Job Applications

November 2007

  1. Google-stupid
  2. Unrefereed DOES NOT EQUAL bogus
  3. Bogus or not- You decide
  4. Theoretical and Mathematical Foundations of Bogosity
  5. Reading Math over Thanksgiving
  6. Advice about NSF grants (not from me)
  7. More on the Tables Problem
  8. Math Problems from everyday life
  9. COMPUTATIONAL COMPLEXITY CONF 2008 SUBMISSIONS WEBSITE OPEN!
  10. Richard Beigel is at NSF
  11. Resubmitting Rejected FOCS paper to STOC
  12. It was a stupid question!!!!!!!!!! or...
  13. Equations and Colorings: Rado's theorem
  14. Do we root for how a problem will go?

October 2007

  1. Stoc seeking papers that...
  2. THANKS to Nicole's FOCS blogs and her positive outlook
  3. Wolfram Prize won!- There IS a (2,3)-UTM
  4. FOCS VIII
  5. FOCS VII : Funding? NSF? whats it all about?
  6. FOCS VI- Local Arrangements AND the future of FOCS!
  7. FOCS V- Report from Prog Comm.
  8. FOCS IV
  9. FOCS III
  10. FOCS II
  11. FOCS I
  12. Why do I find this result interesting- MOD 17 SAT
  13. A more intelligent SPAM discussion
  14. Spam Assassin
  15. Is Computer Science a Science?
  16. The Free Software Foundation and Richard Stallman
  17. If pigs could fly then bacon would be cheaper
  18. Deal-No Deal: MORE $ = LESS Interesting

September 2007

  1. WHERE to apply to grad school?
  2. Andrej (Andrey) Muchnik-a late memorial
  3. The Amish and Cell Phones
  4. Math on TV
  5. Is Immunity Interesting?
  6. Question and Metaquestion about Students emailing you problems
  7. SODA papers are out. Plus...
  8. Search Engines gone wild!
  9. Quantum Computing and Quantum Phy.
  10. Social Process and Proofs of Theorems and Programs

August 2007

  1. The Koblitz Controversy: A reaction
  2. Theory Starts Here! (Informatics Olympiad)
  3. RANT about Electronic Refereeing
  4. Impact of Facebook platform on CS enrollment
  5. Checkers- Clarification by Schaefer
  6. FOCS registration Open
  7. A New Job and Journal
  8. Graduate Complexity Theory Course
  9. Math in Turkey
  10. Theorists who got jobs for fall07-where?
  11. Is Pi defined in the best way?
  12. This is the 1000th post !
  13. Scorpio's Logic

July 2007

  1. Away Message
  2. Suggestion for STOC /FOCS(guest post)
  3. Checkers Solved- its a draw!
  4. W(6,2) = 1132! (excitment, not factorial)
  5. Can Jerry Seinfeld crack P vs NP ?
  6. A postal campaign against spam
  7. An Open Problem wiki!
  8. A ``Concrete'' Open problem
  9. `Its Huffman coded!' does make sense!
  10. A Review of THE KLEIN FOUR's CD
  11. Collapsing degrees (Tribute to Mahaney)

June 2007

  1. Sparse Sets (Tribute to Mahaney)
  2. Steve Mahaney
  3. Down to 100% sure that P\ne NP
  4. Possibly GRANT opp!
  5. New Blog by Mitzenmacher-BIASED COIN
  6. Complexity Theory Theme Song options
  7. Petition Against Boycott of Israel Academics
  8. Math Terms used in real life-good or bad?

May 2007

  1. ASK THE ALGORITHM!
  2. The Man who loved Algorithms
  3. $25,000 prize for ... Univ TM
  4. Godel Prize: Natural Proofs. My 2 cents
  5. When i was undergraduate 1976 1980
  6. FCRC- deadline for late registration FRIDAY
  7. Believing an open problem has been closed
  8. Coda to idiot-post

April 2007

  1. Idiot
  2. Meta Comment on FOCS/STOC comments
  3. Radical change to Conferences by Vijay Vazirani
  4. Getting an 8-year old interested in math:Do's and Don'ts
  5. Knuth Prize goes to Nancy Lynch
  6. Complexity 2007- BE THERE!
  7. What to make of the Ind of CH ?

March 2007

  1. The Complexity Blog Lives!
  2. The End
  3. Turtles
  4. Laws, Taxes and Computer Science
  5. FCRC: Registration, Visas and Hockey
  6. Theory Program Director
  7. A Computer Scientist in Jeopardy
  8. A Place for Open Problems
  9. From Toronto to Chicago to Basketball
  10. When Technology Doesn't Change
  11. The Tenure Process
  12. Pure Evil
  13. Bit Pieces
  14. Jumping in Space
  15. Goodbye CompUSA
  16. Inductive Turing Machines

February 2007

  1. Time to Cash It In
  2. Avoiding the Two-Body Problem
  3. On NP in BQP
  4. Organizing the Academic Job Market
  5. Henzinger on Algorithms
  6. Turing Award
  7. Graduate Student Guide
  8. STOC and FOCS
  9. Time and Music
  10. MARTIN DAVID MEMORIAL (Part II- by Clyde Kruskal)
  11. MARTIN DAVID KRUSKAL MEMORIAL (Part I)
  12. THE DEFINITION OF RARE
  13. Reading papers for fun bill gasarch
  14. Complexity Papers
  15. Divestment
  16. Proposed NSF Budget
  17. The Interview Trip
  18. Up and Downs
  19. Bear Down, Chicago Bears
  20. James Gray

January 2007

  1. More NSF News
  2. Theory Candidates
  3. Good News for the NSF
  4. Thought of the Day
  5. Rating Papers
  6. Too Useful to be a Computer Scientist
  7. The Bourbaki Lecture
  8. Is it Morning or Mourning for American Science?
  9. Complexity Textbooks
  10. Proceedings Papers
  11. The Academic Road Trip
  12. Computing Square Roots
  13. The Proceedings
  14. Events
  15. The Sum and Product Riddle
  16. The State Universities
  17. Four Eyes
  18. SODA and Funding
  19. Dress for Success
  20. 2007 Celebrations
  21. Solving Puzzles
  22. Baseball and Opera
  23. The Job Talk

2006 238

December 2006

  1. 2006 Year in Review
  2. Foundations and Impacts
  3. An Internet-Free Week
  4. A Recommendation Letter
  5. The Necessity of Engineering for Science
  6. Entertainment Tidbits
  7. Show Us Your Research
  8. The Mega-Conferences
  9. Motivation
  10. Science a Victim of Politics Again
  11. You Ask, We Answer
  12. Favorite Theorems: Second Decade Recap
  13. Reductions To SAT
  14. Save the Mathlete, Save the World
  15. The Efficient Church-Turing Thesis
  16. Shifting Time
  17. On Paper Titles
  18. My International Day
  19. The Social Scientist

November 2006

  1. The Campers and the Bread
  2. Electronic vs Physical Program Committees
  3. Victims of the Digital Age
  4. Happy Thanksgiving!
  5. Microfiche
  6. Since We Can't All Win Turing Awards
  7. Favorite Theorems: Nonuniform Complexity
  8. The Future of Science
  9. Pepsi Math
  10. Key References
  11. Puzzles That Keep You Awake at Night
  12. Virtual Academics
  13. Math-Love Songs
  14. Finding Academic Jobs
  15. Prediction Map Post Mortem
  16. Podcast Q&A
  17. PIR Update
  18. Time Zones
  19. Fifteen Seconds
  20. A Thesis to Forget
  21. FCRC Deadlines

October 2006

  1. Algorithms and Networks in The Times
  2. Network Neutrality
  3. The Generalist
  4. Whose Thesis is it Anyway?
  5. Introductory CS Sequences
  6. FOCS Funding, Music and Talks
  7. FOCS Day 1 and Business Meeting
  8. FOCS Begins
  9. Quickies
  10. For-Profit Universities
  11. Scott and P versus NP
  12. Favorite Theorems: The Yao Principle
  13. Numb3rs of Collaborators
  14. What Happened to Departmental Tech Reports?
  15. STOC Undergrad Research Competition
  16. Wholly Natural
  17. Theory Confidential
  18. Brochure Season
  19. Embargoed Science
  20. Recommendation Systems
  21. Commitment
  22. The New CCC

September 2006

  1. Predictions Markets Map of Senate Races
  2. Sponsored Search Panel Discussion
  3. Contributions of Co-Authors
  4. Extended Abstracts
  5. Favorite Theorems: Parity
  6. Short Takes
  7. Don't Get Mad, Get a Lawyer
  8. Some New Geniuses
  9. Back to School Night
  10. Magic Numbers Revisited
  11. Putting the Pieces Together
  12. Styles of Research
  13. Memories of 9/11
  14. Conferences and More
  15. The Haystack
  16. A Continuum of Quality
  17. The Box and The Net
  18. Reception for FOCS 2007?
  19. Favorite Theorems: Unique Witnesses

August 2006

  1. Misha Alekhnovich Retrospective
  2. Parallel Repetition Redux
  3. Analyzing the Zoo
  4. Who Wants to Watch?
  5. Conferences Best Practices
  6. Nevanlinna and Fields Medals
  7. Elsevier Updates
  8. Mikhail Alekhnovich (1978-2006)
  9. French Universities
  10. Guess the max
  11. Why do research?
  12. Using Mobius numbers for a lower bound
  13. Refereeing: Go with your Guts, or Let Reason Rule?
  14. Gin and vermouth
  15. Correlation Clustering
  16. Funding
  17. Flying Away with No Water
  18. A Predictions Markets Mess
  19. Missile Season
  20. Confessions of a Quantum Computing Skeptic
  21. Optimism and Patience
  22. Zero-Knowledge Sudoku
  23. Fulkerson Prize
  24. Privacy

July 2006

  1. Full Derandomization
  2. On Being Color Blind
  3. The Collected Works of Lance Fortnow
  4. A Metapost
  5. Favorite Theorems: The Permanent
  6. The Science and Art of Computation
  7. Going Home
  8. Complexity Day 1
  9. Complexity in Prague
  10. Principles of Problem Solving: A TCS Response
  11. Bouncing a Little French Girl
  12. Useful Information
  13. Naming Complexity Classes
  14. Definitions of Advice
  15. On to Portugal
  16. Complexity and Randomness
  17. England on the 4th of July
  18. England on the 4th of July

June 2006

  1. A Super Addiction
  2. FOCS Accepts and a Movie
  3. Finding a Mate
  4. FREE REPRINTS
  5. Favorite Theorems: Probabilistic Complexity
  6. Campus Maps
  7. The Two-Body Problem
  8. The H-Number
  9. EC
  10. Incomprehensible implies Boring?
  11. EC, PCs and the WC
  12. Time-Travel Circuits
  13. Can Settling P vs. NP Get You Sued?
  14. Funding Committee Report
  15. The Funniest Computer Science Joke Ever
  16. The May 1 Deadline
  17. Beauty and the Bee
  18. Research with Colleagues Visiting for a Short Time

May 2006

  1. Dispersing Ramsey Graphs
  2. The South Has Risen
  3. Talking to Publishers
  4. Flying American
  5. Thoughts from STOC
  6. STOC Business Meeting
  7. Favorite Theorems: Primality Algorithms
  8. Taulbee Survey
  9. Graph Theory and the NSA
  10. Computer Reliability
  11. Fcrc
  12. Game Science
  13. The Importance of Natural Proofs
  14. Forward-Looking Links
  15. Rejection and Rejecting
  16. The Cost of Big Science
  17. Four Coloring the United States
  18. New Priorities for Computability Theory
  19. The Home Stretch

April 2006

  1. Kurt Gödel (1906-1978)
  2. Richard Rado (1906-1989)
  3. Overheard
  4. Theory and Systems
  5. One Miserable Year
  6. Student Weblogs
  7. Favorite Theorems: Small Sets
  8. Ham Radios, Coding Theory and the Internet
  9. The iCal Effect
  10. Microsoft Academic Search
  11. Gödel Prize
  12. What Math to Take?
  13. Reviewer Ethics
  14. The Life of the Party
  15. How Many Students?
  16. The Terror of the Unabomber
  17. Baseball is Back and All is Good in the World

March 2006

  1. Uniform Derandomization Assumptions
  2. Choosing Graduate Schools
  3. Science Without Borders
  4. Making Complexity a Spectator Sport
  5. Links for Friday
  6. Large Search Problems for Small Inputs
  7. Favorite Theorems: Relativization
  8. Avoiding South Dakota
  9. An Interview with Vardi
  10. The Podcast of Uninformed Decisions
  11. Another Approach to P ≠ NP
  12. Resolving Dagstuhl
  13. March Madness
  14. On P versus NP
  15. Presidents and Faculty
  16. Computation and Geometry
  17. Computational Thinking
  18. Computer-Assisted Proofs
  19. Elsevier and TCS
  20. The Internet Never Forgets
  21. Class Times

February 2006

  1. NSF Theory Solicitation Announced
  2. Deal or No Deal Redux
  3. Computational Complexity Accepts
  4. Globalization and Offshoring
  5. Oh Canada
  6. ACM Awards
  7. Accuracy of Predicted Probabilities
  8. Why Computer Science Theory Matters?
  9. Great NSF Theory News
  10. A Referee's Boycott
  11. Favorite Theorems: Alternation
  12. Weapons of Math Instruction
  13. Advanced Placement
  14. Advising
  15. Surprising Gasarch
  16. Sauer's Lemma
  17. Computational Complexity: A Modern Approach
  18. Discovering the Discovered
  19. Announcements
  20. Science in the Union

January 2006

  1. STOC Papers
  2. Quality versus Quantity
  3. Too Many Conferences, Too Little Time
  4. LUDDITES Revisited
  5. How Much are we effected by non-scientific criteria?
  6. A Theorem that should be better known
  7. Making up Problems
  8. Are you a Luddite?
  9. Free Electronic Editions of New Collaborative Books
  10. Theory at NSF
  11. Favorite Theorems Preview
  12. Sports Droughts
  13. The Defense
  14. Time to Write the Letters
  15. My Second Home
  16. Counting Go
  17. A Search Without End
  18. A Classical World
  19. The Technology of Academic Papers
  20. A Year of Incompleteness

2005 237

December 2005

  1. Year in Review
  2. Start Your Engines
  3. Deal or No Deal
  4. All I Want for Christmas is a Proof that P≠NP
  5. A Second Helping of Numb3rs
  6. Pulling Out The Quantumness
  7. Favorite Theorems: First Decade Recap
  8. SIGACT News
  9. What is PPAD?
  10. Physicists and Complexity
  11. Intellectuals and Science
  12. UG-Hard
  13. Texas Ice and Ribs
  14. Surprising Results
  15. How I Became a Theorist
  16. The Day After
  17. Complexity in the Mid-80's
  18. The First Saturday in December

November 2005

  1. The Graduate Complexity Course
  2. Game Theory Finds Computer Science
  3. Chess and Poker
  4. Goodbye Computing Chris
  5. Teaching PCPs
  6. Complexity Deadline Approaching
  7. Introducing a Speaker
  8. Another Satisfied Customer
  9. Relativized Collapse of P and NP
  10. Cornell versus Intelligent Design
  11. The History of RAM
  12. Acceptance Rates versus Competitiveness
  13. The Enemy of the Good
  14. Favorite Theorems: Defining the Future
  15. Negotiating Your Job
  16. Games for Girls
  17. Bringing Complexity to Your iPod
  18. Whither to Compete
  19. Losing the Office Phone
  20. Competitive Analysis

October 2005

  1. Making Yourself Known
  2. List Decoding Beyond Expectations
  3. Algorithms for a Ten-Year Old
  4. Joy on the South Side of Chicago
  5. Selling Theory
  6. Page Six
  7. Knuth Prize
  8. FOCS Business Meeting
  9. First day of FOCS
  10. Math in Complexity
  11. Football Schools
  12. Finding Nash has Same Complexity as Finding Fixed Points
  13. True Impact
  14. Blogging and Academics
  15. Fonts
  16. Early or Late
  17. Favorite Theorems: Logical Characterization of NP
  18. A New Packard Fellow
  19. NP-Completeness Papers
  20. Unix Free Since 1999
  21. Tradition
  22. DNA Testing for Sports
  23. Euthanizing a Virtual Pet
  24. Awards

September 2005

  1. Cocktail Conversations
  2. Circuit Complexity and P versus NP
  3. Exciting Baseball Ahead
  4. Game Theory
  5. The Price of Freedom?
  6. Egos Needed
  7. Short Takes
  8. Thanks a Bunch STACS
  9. Proof
  10. Anatomy of a Theorem
  11. Jonathan and Me
  12. Favorite Theorems: NP-Incomplete Sets
  13. Comments on Comments
  14. Do Wikis Work?
  15. Ppoly
  16. Focs
  17. SODA Rising
  18. Questions About Crypto
  19. Hard Times for the Big Easy

August 2005

  1. Theory Still Thrives at IBM
  2. Back From Vacation
  3. The Game -- what's left (by Ryan O'Donnell)
  4. Blogger.com -- stinks (by Ryan O'Donnell)
  5. The Game (by Ryan O'Donnell)
  6. Depth-two TC^0 (by Ryan O'Donnell)
  7. Explicit expander exaggerations (by Ryan O'Donnell)
  8. Additive combinatorics (by Ryan O'Donnell)
  9. More on parallel repetition (by Ryan O'Donnell)
  10. Conference Crashers
  11. Research Annealing
  12. US Visa Limit Reached
  13. Extreme Oracles
  14. Information and Computation
  15. Sudoku Revisited
  16. Is the Thrill Gone?
  17. Favorite Theorems: Abstract Complexity
  18. The New Research Labs
  19. Screenplays of Science
  20. Moons and Planets
  21. Two New Blogs
  22. Relativizing Space

July 2005

  1. The Secrets of Success
  2. Powerful, Aware and Evil
  3. Majority is Stablest
  4. Understanding Proofs
  5. What Kind of Science is Computer Science?
  6. Complexity versus Computability
  7. Magic is in the Eye of the Beholder
  8. Winnie the Mathematician and a Few Comments on Comments
  9. Computer Science Has Been Very Very Good To Me
  10. Do Only Simple Theorems Have Simple Proofs?
  11. MC Plus +
  12. Favorite Theorems: P = NP for Space
  13. The Organized Scientist
  14. Computer Science in High School
  15. Matrix Rigidity
  16. Different Views of Consciousness
  17. Independence Day in America

June 2005

  1. Research Directions for Theory
  2. FOCS Accepts
  3. Defining Theory
  4. The Unique Games Conjecture
  5. The End of an Era?
  6. Herbie: AI Marvel
  7. Communicating Open Problems
  8. Favorite Theorems: The Polynomial-Time Hierarchy
  9. An Eulerian Tour
  10. Where will you be next year?
  11. Understanding "Understanding"
  12. Conference on Computational Complexity
  13. Graduation Day
  14. Growth Causes Shrinking
  15. Humor in Talks
  16. The Wife and The Mistress
  17. Making Pigs Fly
  18. Mysteries of the Seventies
  19. On Language

May 2005

  1. Conference Presentations
  2. Newspaper Odds
  3. CCC 2005
  4. Complexity and Sudoku
  5. STOC Business Meeting Redux and More
  6. STOC Business Meeting
  7. Welcome Summer
  8. A Long Time Ago in a City 800 Miles Away
  9. George Dantzig 1914-2005
  10. Crisis in Theory Funding
  11. Pitfalls of the Tenure System
  12. A Day of Links
  13. Temporal Theory
  14. Complexity of Computer Computations
  15. Favorite Theorems: Combinatorial NP-Complete Problems
  16. Ranking CS Departments
  17. An Endless Frontier Postponed
  18. Postdocs
  19. Dilemmas of Prisoners and Professors
  20. Leonid Khachiyan (1952-2005)
  21. Read this Weblog, Get a Job

April 2005

  1. Clemens Lautemann
  2. The Quality Thesis
  3. My Mouse and Me
  4. The Story of Ribbit
  5. scIenCE Princess
  6. Favorite Theorems: NP-Completeness
  7. A Fine Line Between Prank and Fraud
  8. And The Winner Is …
  9. A New PCP Proof
  10. Discussion Questions
  11. The Translation Lemma
  12. A Modest Proposal
  13. Paper Pet Peeves
  14. Does a book exist if nobody reads it?
  15. The Battle of Grantsburg
  16. Baseball is Back
  17. Math Poetry Contest
  18. What happened to the PRAM?
  19. Another Breakthrough!

March 2005

  1. Sublogarithmic Space
  2. A Non-Standard Post
  3. Getting an Edge
  4. My Brother
  5. P=NP and the Arts
  6. Complexity LaTeX Package
  7. Tape Reduction
  8. Paul Fortnow (1937-1980)
  9. The End of the Travel Season
  10. Bicycling in Holland
  11. What Makes a Good Collaborator?
  12. The Reality of Virtual Pets
  13. NP-complete Problems and Physical Reality
  14. Favorite Theorems: Efficient Computation
  15. The Researcher's Dilemma
  16. Finding Duplicates
  17. Theory in Japan

February 2005

  1. Are we the university?
  2. New Horizons in Japan
  3. Ramanujan's Lost Notebook
  4. The Complexity of the Nash Equilibrium
  5. Factoring NUMB3RS
  6. Computer Science Recruiting
  7. Complexity Accepts
  8. It's Safe to Study in America Again
  9. From Industry to Academics?
  10. Just Say No
  11. Favorite Theorems: The Seminal Paper
  12. Maybe He Missed Some Math
  13. Guest Post on Numb3rs P vs NP Episode
  14. The Super Bowl Parties
  15. Information Markets and Quantum Computing
  16. Internet at Conferences
  17. How to Judge a Weatherman?

January 2005

  1. An Auction of Computing History
  2. Dimacs
  3. Choosing Your Advisor
  4. Remembering the Holocaust
  5. STOC Papers
  6. Blink
  7. The Premier of Numb3rs
  8. Machine Learning, Information Markets and Love
  9. Does a Chess Program have Free Will?
  10. Favorite Theorems: The First Decade
  11. Recommendation Letters
  12. Theory for Dentists
  13. Your Patience Has Been Rewarded (by guest blogger Rahul Santhanam)
  14. Open papers (by guest blogger Rahul Santhanam)
  15. Theory used to be Fun (by guest blogger Rahul Santhanam)
  16. Mandatory Technical Post (by guest blogger Rahul Santhanam)
  17. Recreational Complexity (by guest blogger Rahul Santhanam)
  18. World Series of Complexity Theorists (by guest blogger Rahul Santhanam)
  19. What's in a Name? Complexity (by guest blogger Rahul Santhanam)
  20. While the advisor is away ...
  21. Spamalot
  22. Big Omega
  23. Asher Peres, 1934-2005
  24. Embarrassing Mistakes

← 2002–2004 2012–2026 →