Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

Monday, July 29, 2013

Certifying primality in a CONSTANT number of operations

›
For this post I will only count the operations PLUS, MINUS, MULT. They may be done on rather large numbers. Recall that from the work comi...
7 comments:
Thursday, July 25, 2013

Ph.D. Attrition

›
Leonard Cassuto writes in the Chronicle an article  Ph.D. Attrition: How Much Is Too Much?  He presupposes the answer with the subtitle ...
14 comments:
Tuesday, July 23, 2013

I gave a poster session at Erdos 100- so how did it go?

›
In a a prior post I suggested that STOC perhaps have people give posters instead of talks. While I doubt this will ever happen I think its ...
2 comments:
Friday, July 19, 2013

A(nother) nice use of Gen Functions

›
In a prior post I tried to give a simple example of a proof that uses Gen Functions where there was no other way to do it. For better or w...
2 comments:
Tuesday, July 16, 2013

DUMP YOUR TABLES! (the moral of my story that started with a hat problem)

›
Recall from my last post: PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on ...
3 comments:
Monday, July 15, 2013

A problem and later a story and a point.

›
I have (1) a math problem to tell you about (though I suspect many readers already know it), (2) a story about it, and (3) a point to make. ...
17 comments:
Thursday, July 11, 2013

Combinatorics use to not get any respect. But because of Erdos...

›
(This blog is based on things I heard at the Erdos 100th Bday Conference ) I have spend the last week at the Erdos 100th bday conference. ...
6 comments:
Monday, July 08, 2013

AltaVista versus Google

›
Today Yahoo is closing AltaVista, the best search engine before Google. The news caught me by surprise, AltaVista still existed? A number of...
9 comments:
Tuesday, July 02, 2013

Computability in Europe

›
Bill and I are both in Europe this week. I'm in Milan at  Computability in Europe and Bill is 500 miles away in Budapest for the  Paul ...
3 comments:
Thursday, June 27, 2013

Friends Don't Let Friends Carpool

›
The AAA foundation measured cognitive distraction while driving and reported that having a passenger in the car is as dangerous as using a ...
13 comments:
Monday, June 24, 2013

Quantum Tecniques/Gen Functions- don't be afraid of new techniques

›
Ronald de Wolf gave a GREAT talk at CCC on the uses of Quantum techniques to Classical Problems. He made the analogy of using the Prob Meth...
9 comments:
Thursday, June 20, 2013

Automate Me

›
An economist friend asked me if there were still productivity gains to be had for office workers (like us). After all, we have email, social...
5 comments:
Monday, June 17, 2013

Fraud or not ?

›
For each of these, are they frauds? The Turk was a chess playing ``computer'' (around 1770) that was later discovered to be chea...
6 comments:
Thursday, June 13, 2013

The Internship

›
Last weekend I took my teenage daughters to see The Internship , the Vince Vaughn-Owen Wilson vehicle where they play two forty-year old int...
6 comments:
Tuesday, June 11, 2013

STOC: Some NON-radical ideas

›
At the STOC business meeting Joan Feigenbaum (PC chair) raised some very good points. There was no real discussion (or perhaps the burning ...
12 comments:
Thursday, June 06, 2013

Complexity Typecast

›
Lance:  Welcome to another exciting typecast coming from sunny Stanford University. I'm with Bill at the 28th Conference on Computationa...
6 comments:
Tuesday, June 04, 2013

STOC is Burning

›
Bill and I are in Palo Alto this week for the co-located meetings of STOC and Complexity . In a new ACM policy, the STOC 2013 papers  are f...
6 comments:
Thursday, May 30, 2013

The High Quality Research Act

›
Lots of talk, mostly negative , about the proposed  High Quality Research Act . Prior to making an award of any contract or grant funding ...
8 comments:
Tuesday, May 28, 2013

Theory Jobs 2013

›
Time for the annual spring jobs posts. Like last year , I set up a  Google Spreadsheet  that everyone can edit so we can crowd source who is...
6 comments:
Thursday, May 23, 2013

Quantum Computing Fast and Slow

›
I just read two very different science books, Daniel Kahneman's Thinking, Fast and Slow and Scott Aaronson's Quantum Computing sinc...
10 comments:
‹
›
Home
View web version
Powered by Blogger.