The Curious Engineer

Computational Complexity

2002–2004

425 posts

2005–2011 →

2004 200

December 2004

  1. Complexity Year in Review
  2. Copyrights on Conference and Journal Papers
  3. Computation and the Socio-Economic Sciences
  4. Tragedy in Asia
  5. FSTTCS 2004 at Chennai
  6. Favorite Theorems Recap
  7. Numb3rs
  8. Ooscla
  9. Quality Matters
  10. Decryption by Clancy
  11. Favorite Theorems: Derandomizing Space
  12. Can We Fairly Teach and Grade?
  13. A Map of Complexity Classes
  14. The Other Nigerian Scam
  15. The NSF Gets Some Attention
  16. When Average Case is the Worst Case
  17. Bad Timing
  18. Use Google to Search Your LaTeX Files

November 2004

  1. Suggestions to Program Committees
  2. The State of CISE
  3. Conflicts
  4. NSF Budget
  5. Letting Go
  6. Zig-Zag Connectivity
  7. Google Scholar
  8. How about Informaticians?
  9. The Polar Express
  10. Does Google Make Us Lazy?
  11. Undirected Connectivity in Log Space
  12. How Did We Survive Before the Internet?
  13. Favorite Theorems: Quantum Lower Bounds
  14. Public Referee Reports
  15. Life Goes On
  16. Vote Complexity

October 2004

  1. Election Day
  2. The Co-Author Conundrum
  3. Solving an 86-Year Old Open Problem
  4. Nothing Like a Deadline to Ruin Your Day
  5. What Would the Martians Think?
  6. Favorite Theorems: Learning Circuits
  7. Go Sox!
  8. Conversations with Bill
  9. More FOCS News
  10. FOCS News
  11. Some Dagstuhl Presentations
  12. Is the Internet Harming Dagstuhl?
  13. Back in Dagstuhl
  14. A Celebration of Women in Computing
  15. NP-Completeness for a 9-Year Old
  16. Groups versus Departments
  17. Holy Trefoils, Math Fans!
  18. Larry Stockmeyer Commemorations
  19. Are we too nice?

September 2004

  1. The Specialization of Computer Science
  2. Computer Science's Newest Genius
  3. Republicans and Democrats on Science Research
  4. The Blue State of Science
  5. NP-Completeness is Illuminated
  6. The Beauty of the Magic Number
  7. Quantum in the North; Random in the South
  8. NSF News
  9. Email's Curse of Success
  10. Is the AP Test to Blame for Shifting CS Enrollments?
  11. Favorite Theorems: List Decoding
  12. Which Affiliation?
  13. Just Because I'm a Scientist Doesn't Mean I Know Anything
  14. The Electoral College
  15. Is Encryption Doomed?
  16. Theory in the Coca-Cola Capital of Iowa

August 2004

  1. Computationally Simple One-Way Functions
  2. What happened to the future?
  3. ε and the Olympics
  4. "Conclusions and Open Problems" (by Adam Klivans)
  5. Constant Depth Circuits, Fourier Transform, and Learnability (by Adam Klivans)
  6. Banff Revisited (by Adam Klivans)
  7. Favorite Theorems: The Harmonic Sieve (by Adam Klivans)
  8. Favorite Theorems: Parallel Repetition
  9. Wisdom of Crowds
  10. Fun with Information Markets
  11. Micromorts
  12. When to Announce?
  13. Small Circuits
  14. Larry Stockmeyer
  15. Strangers in the Same Place

July 2004

  1. Journal Rankings
  2. NSF Budget
  3. Favorite Theorems: Superlinear Bounds on Branching Programs
  4. Carl Smith 1950-2004
  5. Extracting Randomness
  6. Some Links and Random Thoughts
  7. Why are CS Conferences so Important?
  8. Time and Space Hierarchies
  9. Bringing Families to Conferences
  10. Final Notes from Banff
  11. RESULTAPHOBIA!
  12. Gems of Additive Number Theory
  13. Howdy from Banff
  14. JCSS To Pay Editors, Possibly Referees
  15. Lessons from Economics

June 2004

  1. FOCS Accepted Papers
  2. Don't Make it Too Easy or Too Much
  3. Note from Vereshchagin
  4. Complexity Conference Recap
  5. Rump Session Redux
  6. Shimon Even (1935-2004)
  7. Visa Problems Continue
  8. Riemann Hypothesis and Computational Complexity
  9. Special Issues
  10. STOC Business Meeting
  11. Favorite Theorems: Connections
  12. Win a Gmail Account
  13. Professional Societies
  14. BEATCS Complexity Column
  15. Survey Papers
  16. Complexity Registration Deadline
  17. IEEE Fellowship at the State Department
  18. Impagliazzo's Five Worlds

May 2004

  1. Visas and Titles
  2. What if P = NP?
  3. Informatics in Indiana
  4. Comments
  5. A Part-Time Ph.D.?
  6. Randomized Blogspace
  7. Cornell's New President
  8. Favorite Theorems: Probabilistically Checkable Proofs
  9. An Auction of Google
  10. Page Charges
  11. Games
  12. New Web Host
  13. America Losing Its Edge

April 2004

  1. Karp Symposium
  2. Conferences versus Journals
  3. Is Disney World NP-complete?
  4. Gödel Prize
  5. Theory Girl
  6. A Few Short Announcements
  7. Are There #P Functions Equivalent to SAT?
  8. Asian Food for Thought?
  9. Favorite Theorems: Primality
  10. The Cost of Textbooks
  11. The View of a Science Writer
  12. Blum Complexity Measures
  13. More News from Dagstuhl

March 2004

  1. A Free Lunch Theorem For Circuit Complexity
  2. Changes in Introductory Theory
  3. Opening Day
  4. Teaching High School Physics
  5. Evolution
  6. Is Satisfiability Checkable?
  7. AT&T Research
  8. Computer Science Unplugged
  9. An Unnatural Post
  10. Favorite Theorems: Derandomization
  11. March Madness
  12. Publishing Papers from Iran
  13. Outsourcing and the Future of Computer Science
  14. Seeing the Same People in Different Places
  15. SIGACT News
  16. Persi Diaconis
  17. Counting the Rationals Quickly

February 2004

  1. Marriage and the Donald
  2. Fermat's Last Tango
  3. Why the NSF Needs Your Grant Proposals
  4. My Doom
  5. Sneakers
  6. The LaTeX Generation
  7. Parberry's Guides
  8. And the Accepted Papers are ....
  9. Is it Recursive, Computable or Decidable?
  10. Journal of Algorithms Editorial Board Bolts to New ACM Journal
  11. Minimal Indices
  12. The MIT-Berkeley Axis
  13. Reading the Applications
  14. Super Theory Day at Columbia on May 14
  15. Designing for Innovation
  16. A letter from the editors of the journal Computational Complexity

January 2004

  1. A Little Theorem
  2. The Defense, Part II
  3. Howdy from Amsterdam
  4. STOC and the NSF
  5. The Defense, Part I
  6. John Lewis
  7. The Da Vinci Code
  8. I'm Back
  9. Scaring Away The Scientists Of Tomorrow (last post of guest blogger Scott Aaronson)
  10. Algorithmic Cooling on Mars II: Mars (by guest blogger Scott Aaronson)
  11. Algorithmic Cooling on Mars I: Algorithmic Cooling (by guest blogger Scott Aaronson)
  12. Live From QIP (by guest blogger Scott Aaronson)
  13. Advice, Not The Quantum Kind (by guest blogger Scott Aaronson)
  14. Ingredients for Serious Thought (by guest blogger Scott Aaronson)
  15. Arrr, Even Pirates Be Polynomially-Bounded (by guest blogger Scott Aaronson)
  16. Complexity Class of the Week: PP (by guest blogger Scott Aaronson)
  17. How Long Until We Get Along? (by guest blogger Scott Aaronson)
  18. Guest Blogger
  19. Balance is a Red-Hot Word
  20. Survey on Private Information Retrieval
  21. Pictures from Mars
  22. What is an Algorithm?
  23. Freeman on CISE Reorganization
  24. These are a few of my favorite theorems

2003 149

December 2003

  1. End of Year Thoughts
  2. John von Neumann
  3. That's My State
  4. Scientific Superstars
  5. Does NP=UP?
  6. Does PowerPoint Make You Dumb?
  7. Ordering Authors
  8. Seven Naughty Words
  9. Two Uses of Randomness
  10. A Regular Problem Solved
  11. The Elsevier Dilemma
  12. The NSF and SIGACT News
  13. Show Us Your Papers

November 2003

  1. Critical Mass
  2. Theory and XML
  3. Rational Functions and Decision-Tree Complexity
  4. Midwest Theory Day
  5. Editors Needed
  6. A Regular Problem
  7. Opportunities at Chicago (Blatant Plug)
  8. 25 Years of Science Times
  9. CISE Reorganization
  10. The Web and Research
  11. The PCP Theorem
  12. What happened at NEC?

October 2003

  1. Lessons from the IM Experiment
  2. Changing Strings but not Distributions
  3. Quantum Leaping to Conclusions
  4. When Good Theorems Have Bad Proofs
  5. Talk to Me
  6. What's happening at the NSF?
  7. Tti
  8. The Agony of Defeat
  9. Tutorials on Machine Learning and Mixing via Markov Chains
  10. Columbus Day
  11. Advice for Students Going to a Conference
  12. Focs
  13. A New Genius
  14. Waiting for Nobel
  15. Happy Fiscal New Year

September 2003

  1. One-Way Functions
  2. A Speech and A Weblog
  3. Proof, The Movie
  4. Turing, The Novel
  5. The Buzz
  6. Creative Commons
  7. Balanced NP Sets
  8. Is P versus NP formally independent?
  9. STOC 2004
  10. Institute of Advanced Study
  11. Scheduling Research

August 2003

  1. Electronic Commerce
  2. Hello Chicago
  3. Goodbye New Jersey
  4. A New-To-Me Pumping Lemma for Regular Languages
  5. Splitting Sets
  6. SIGACT News and The Cold War
  7. My Life in Email

July 2003

  1. Information Markets for Fighting Terrorism
  2. The Tour
  3. The Move
  4. Juntas
  5. Citeseer
  6. Quantum Advice
  7. A Combinatorial Theorem Proven by Kolmogorov Complexity
  8. The Rump Session
  9. Coming Home
  10. Complexity Abstracts
  11. For the Love of Math

June 2003

  1. Expanders from Epsilon-Biased Sets
  2. Sigact
  3. Epsilon-Biased Sets
  4. Whose hands are on the FOCS cover?
  5. Walter Savitch
  6. FOCS 2003
  7. Boosting
  8. Alonzo Church
  9. Thoughts on FCRC
  10. The Business Meeting
  11. Howdy from San Diego
  12. Back to Chicago
  13. Foundations of Complexity Lesson 19: The Immerman-Szelepcsenyi Theorem

May 2003

  1. Open Questions from Hopcroft and Ullman
  2. Computing's Lost Allure?
  3. Celebration for Walter Savitch
  4. Turing Machines and Godel's Theorems
  5. Foundations of Complexity Lesson 18: Savitch's Theorem
  6. The Nerd Shot
  7. Foundations of Complexity Lesson 17: Space Complexity
  8. Universal Search
  9. Fcrc
  10. History's Loss/Mathematics' Gain

April 2003

  1. The Power of Random Strings
  2. More on Kolmogorov Complexity
  3. Kolmogorov Centennial
  4. Complexity Classes of the Week: SBP and A0PP
  5. Paddable NP-Complete Sets are Isomorphic
  6. The Turing Award
  7. Awards
  8. Finding Problems to Work On
  9. Articles on Quantum and DNA Computers
  10. Razborov on Unprovability
  11. Comments
  12. Computation Beyond Turing Machines?
  13. Math Riots Prove Fun Incalculable
  14. Big Ideas
  15. Counterexample to Fermat's Last Theorem Found!!!

March 2003

  1. The Berman-Hartmanis Isomorphism Conjecture
  2. Is P versus NP undecidable?
  3. Foundations of Complexity Lesson 16: Ladner's Theorem
  4. On Basketball and Politics
  5. ICALP Papers Announced
  6. Information Markets
  7. It's Not a Tree After All
  8. War and This Weblog
  9. March Madness
  10. Doing homework the hard way
  11. Complexity Class of the Week: The Permanent
  12. Theory A and Theory B
  13. Talk Posted
  14. Rush Hour
  15. Cardinality Theorem for Regular Languages?

February 2003

  1. Howdy from Berlin
  2. A Zero-One Law for RP
  3. Complexity Papers Announced
  4. More on Perfect Graphs
  5. Complexity Class of the Week: BPPpath
  6. News for Nerds. Stuff that Matters.
  7. Traveling Salesman on the Plane
  8. Foundations of Complexity Lesson 15: More NP-complete Problems
  9. NEXP not in P/poly?
  10. JACM is 50
  11. While I was gone

January 2003

  1. Vacation
  2. An Efficient Algorithm for Testing whether a Graph is Perfect
  3. The Lambda Calculus, Part 1
  4. Breaking Real-World Locks with Cryptography
  5. The Why Me? File
  6. Foundations of Complexity Lesson 14: CNF-SAT is NP-complete
  7. Supreme Court Rules on Infinity
  8. Our Friends at the NSA
  9. A Physics-Free Introduction to the Quantum Computation Model
  10. Foundations of Complexity Lesson 13: Satisfiability
  11. What is your Erdös number?
  12. Circuits over Sets of Natural Numbers
  13. When will we show P ≠ NP?
  14. Logic in the 21st Century
  15. Foundations of Complexity Lesson 12: Turing Machine Redux
  16. 2003: A Year-Long Celebration of Geniuses

2002 76

December 2002

  1. Reflections on 2002
  2. FOCS is going to Europe
  3. Find the Longest Path
  4. A Note on Running Times
  5. Pictures of Manindra
  6. Rules for a Complex Quantum World
  7. Foundations of Complexity Lesson 11: NP-Completeness
  8. Ramsey Theory and Computer Science
  9. The Great Journal Debate
  10. Outsider Math
  11. Learning via Occam's Razor
  12. Foundations of ComplexityLesson 10: The P versus NP Problem
  13. FYI: The AIP Bulletin of Science Policy News
  14. CAPTCHA in the Times
  15. SIGACT News
  16. Complexity Class of the Week: MA
  17. Bad Math Joke
  18. Foundations of ComplexityLesson 9: Nondeterminism
  19. You can't judge a proceedings from its cover
  20. Quantum Information Science and Technology Roadmap
  21. CAPTCHA

November 2002

  1. Complexity Deadline
  2. Identity-Based Encryption
  3. Ias
  4. FOCS and Visas
  5. Coming to America
  6. Where was Cook's Talk?
  7. Foundations of ComplexityLesson 8: Efficient Computation
  8. It all started with a machine...
  9. Tic Tac Toe Variation
  10. Kolmogorov Complexity Web Site
  11. The Union of Complexity Classes
  12. Foundations of ComplexityLesson 7: The Recursion Theorem
  13. Stacs
  14. Complexity Class of the Week: SPP, Part II
  15. Foundations of ComplexityLesson 6: The Halting Problem
  16. Conferences

October 2002

  1. Complexity Class of the Week: SPP, Part I
  2. Talks by Manindra Agrawal
  3. Foundations of ComplexityLesson 5: Reductions
  4. Hard Problems
  5. Infinity and the Supreme Court
  6. Quantum Parody of Shakespeare's Hamlet III.i
  7. Scooping the Loop Snooper
  8. More from Dagstuhl
  9. Howdy from Dagstuhl
  10. Complexity Class of the Week: P
  11. Foundations of Complexity Lesson 4: Noncomputable Computably Enumerable Languages
  12. Wigderson Paper on Work of Sudan
  13. Chaitin's Omega - The Halting Probability
  14. Foundations of ComplexityLesson 3: Universal Turing Machines and Diagonalization
  15. SIGACT News

September 2002

  1. A Reader's Question about Kolmogorov Complexity
  2. New york times has finally taken
  3. Quantum algorithms and complexity
  4. Howdy from canada
  5. Im off to beautiful banff canada for
  6. Ketan mulmuley and milind sohoni have
  7. I saw carl pomerance yesterday give
  8. Complexity Class of the Week: C=L
  9. Foundations of ComplexityLesson 2: Computable and Computably Enumerable Languages
  10. Complexity Class of the Week: Factoring
  11. Who says you cant make money with
  12. Science Screenplay Contest
  13. On september 11 2001 we lost member of
  14. Foundations of Complexity Lesson 1: What is a computer?
  15. I heard of nice new result from
  16. Complexity Class of the Week: PP
  17. Todays new york times has essay on
  18. Today is major holiday in us labor day

August 2002

  1. Great books computers and
  2. Complexity Class of the Week: S2P
  3. Complexity class of week when i was at
  4. Last spring i saw copenhagen great
  5. This has been exciting summer for
  6. This is my complexity web log

2005–2011 →