Lance Fortnow's Blog, page 116

Approximate Computing

Hadi Esmaeilzadeh is the newest professor in the School of Computer Science at Georgia Tech. Hadi works in computer architecture and did some great work on dark silicon. (Just noticed this is starting to look like a Lipton-style blog post.)



I had Hadi give a lecture in my theory class (the dreaded day-before-Thanksgiving lecture). Hadi talked about his new research directions in approximate computing. Approximate computing is a new paradigm in the architecture community, doesn't even have its own wikipedia entry yet.



When you do arithmetic operations, say addition and multiplication on real numbers, you typically want full precision up to the limits of the bits we use to store those numbers. Suppose you allow some error, say 5%. For logical operations, this would be a disaster giving a very wrong answer. Running various optimization algorithms, like simplex, these error might compound leading to very suboptimal results.



But there are several scenarios where approximate computing might not hurt that much. Processing media, like pictures, sound and video, are not exact anyway and a small error might not degrade the quality successfully. Statistical methods that sample a large space, such as when we analyze big data, still could yield reasonable results using approximate computing.



Why do approximate computing? Because of the architecture--approximate computing can be done often faster and with less power consumption. The tradeoffs may allow approximate computing to handle tasks beyond what we can do with traditional computing.



Approximate computing needs good theoretical models and that's where our community can come it. What's the right way to model the power-speed-accuracy tradeoffs and how can we determine the right computational problems that can take advantage of these tradeoffs. Might have nice connections to learning theory and property testing.

Inventions are Non-Commutative: Amazon vs Amazon

(Tal Rabin, Shubhangi Saraf and Lisa Zhang asked me to remind you to publicize this: the bi-annual Women in theory (WIT workshop), NYC, May 28-30, 2014. Apps due Jan 20, 2014. Go here for all relevant information)



If FAX machines had come out 20 years earlier they would have had far MORE impact.

If FAX machines had come out 20 years later they would have had NO impact since by then

we all had email and scanners and what not. So when an invention comes out matters.



Ask your grandparents what white-out was for corrections on a typewriter (while you are at it ask your grandparents what a typewriter is). If it came out 20 years later then Bette Nesmith  would have not made 50 million dollars, her son Michael Nesmith would not have had the spare time to become a musician and there might not be a group  called THE MONKEES. Gee, we would have no LAST TRAIN TO CLARKSVILLE. But I digress (from what?).



If Lasik  eye surgery came first and glasses later, glasses may have been seen as a great way to avoid surgery!



Amazon is working on a technology that may become obsolete before it really takes off. I am referring to the Amazon Drone Project. The idea is that when your order an item from Amazon a drone will get it to your house (or perhaps wherever you are) VERY FAST - maybe within 30 minutes. This works well for objects under 5 pounds. Say like what Amazon is best know for BOOKS.



But there is an a technology out there that may kill this idea before it gets off the ground. There is a competing company called Amazon which has already developed ways for people to get books on what they call a Kindle, which is like emailing them a book. So there is NO Physical object to be delivered.

Hence the Amazon Drone project may, like the 8-track tape (ask your great grandparents) become obsolete due to technology being developed by Amazon.



I wonder- had Amazon Drone come out 20 years ago would it have had more impact? Would it have made less of a demand for Amazon Kindle?



Amazon Drone may still have an impact by delivering other things. But I wonder how long it will take before 3-d printers make MOST things that Amazon delivers not need to be physical objects.

Inventions are Non-Communative: Amarzon vs Amarzon

(Tal Rabin, Shubhangi Saraf and Lisa Zhang asked me to remind you to publicize this: the bi-annual Women in theory (WIT workshop), NYC, May 28-30, 2014. Apps due Jan 20, 2014. Go here for all relevant information)



If FAX machines had come out 20 years earlier they would have had far MORE impact.

If FAX machines had come out 20 years later they would have had NO impact since by then

we all had email and scanners and what not. So when an invention comes out matters.



Ask your grandparents what white-out was for corrections on a typewriter (while you are at it ask your grandparents what a typewriter is). If it came out 20 years later then Bette Nesmith  would have not made 50 million dollars, her son Michael Nesmith would not have had the spare time to become a musician and there might not be a group  called THE MONKEES. Gee, we would have no LAST TRAIN TO CLARKSVILLE. But I digress (from what?).



If Lasik  eye surgery came first and glasses later, glasses may have been seen as a great way to avoid surgery!



Amazon is working on a technology that may become obsolete before it really takes off. I am referring to the Amazon Drone Project. The idea is that when your order an item from Amazon a drone will get it to your house (or perhaps wherever you are) VERY FAST - maybe within 30 minutes. This works well for objects under 5 pounds. Say like what Amazon is best know for BOOKS.



But there is an a technology out there that may kill this idea before it gets off the ground. There is a competing company called Amazon which has already developed ways for people to get books on what they call a Kindle, which is like emailing them a book. So there is NO Physical object to be delivered.

Hence the Amazon Drone project may, like the 8-track tape (ask your great grandparents) become obsolete due to technology being developed by Amazon.



I wonder- had Amazon Drone come out 20 years ago would it have had more impact? Would it have made less of a demand for Amazon Kindle?



Amazon Drone may still have an impact by delivering other things. But I wonder how long it will take before 3-d printers make MOST things that Amazon delivers not need to be physical objects.

Bitcoins Revisited

Two years ago I gave a lecture and posted about bitcoin. Of course what I didn't do was buy a bitcoin whose value back then was about $3 and today runs in the $1000 range.



Bitcoins have received quite a bit of press, particularly with the FBI shutting down Silk Road, the drug trafficking site which used bitcoins for their transactions. Then people realized that bitcoins are starting to become a real currency, with a market cap of about US$11 billion not far now from the money supply of the Costa Rica Colones (US$13 billion). Now governments are deciding on how to deal with bitcoins as a currency, one which they really can't regulate or control.



The Economist has one of the better articles on Bitcoins, talking about some of the technical issues involved.

The Bitcoin system is designed to cope with the fact that improvements in computer hardware make it cheaper and faster to perform the mathematical operations, known as hashes, involved in mining. Every 2,016 blocks, or roughly every two weeks, the system calculates how long it would take for blocks to be created at precisely 10-minute intervals, and resets a difficulty factor in the calculation accordingly. As equipment gets faster, in short, mining gets harder. But faster equipment is constantly coming online, reducing the potential rewards for other miners unless they, too, buy more kit. Miners have formed groups that pool processing power and parcel out the ensuing rewards. Once done with ordinary computers, mining shifted to graphics-processing units, which can perform some calculations more efficiently. Miners then moved on to flexible chips that can be configured for particular tasks, called field-programmable gate arrays. In the past year, bespoke chips called ASICs (application-specific integrated circuits) have appeared on the scene.

Then there was the paper Dorit Ron and Adi Shamir wrote that explored the bitcoin transaction graph and suggested a (now supposedly debunked) connection between the mysterious creator of bitcoins, "Santoshi Nakamoto", and Ross William Ulbricht aka Dread Pirate Roberts, the founder of Silk Road.



Bitcoins even make it to my Thanksgiving table. My brother thought they were a scam even though I pointed out the systems has no scammers. He remains unconvinced though he invests heavily in gold, which has the same property of the value mostly being there because people believe it has value.



I taught a lecture on bitcoins again in my intro theory course. We all generally agreed that a few years from now we'll all remember the days when bitcoins were worth $1000. Not sure we'll remember those days because bitcoins will be worth millions or because they'll be worth pennies.

Global Warming and the Axiom of Choice

Who was the first scientist to warn of Global Warning? These questions are complicated, but I would say it was Bing Crosby in a paper called White Christmas. Here are the first two lines:

I'm dreaming of a white christmas

Just like the ones I used to know

Why are there no more white christmas's? Because global warming made it stop snowing!



Why do otherwise intelligent people refuse to believe that Global Warming is real and is caused by humans and we we need to do something about it? I have a conjecture and an analog. Here is what I think the reasoning is




Republicans have the following AXIOM (until they are in office): government IS the problem, not the solution. More than this, they think that there is NO problem that requires government action.


Consequence: Government should do NOTHING about Global Warming.


Since Government shouldn't do anything about Global Warming, it is not a problem.



Rather than rethink their AXIOM they accept the conclusion that Global Warming is either not a problem or not caused by humans. The shame of it is that there ARE economically viable ways, perhaps moderate republican ways, to fight global warming- some version of Cap-and-trade, or pay-to-pollute. And getting off of Fossil Fuels would be good for other reasons. I can picture history going a different way so that Republicans want more fuel-eff cars to get us off of Mideast Oil. I can picture a history where the insurance companies are more powerful than the oil companies for lobbying and hence Government takes LOTS of action against global warming.



Are their things in math where people accept an axiom despite its absurd consequences?Yes:


Most math people believe the Axiom of Choice.


Consequence: the Banach-Tarski Paradox





Rather than rethink their AXIOM they accept the absurd conclusion that you can break a ball into 5 pieces, reassemble, and get twice the volume. Fortunately, believing this does not endanger the planet.

The Institute for proving Graph Isomorphism is in P

(This post was inspired by Adam Winklers awesome book

Gunfight: The Battle over the Right to Bear Arms in America.

Disclaimers one: Adam Winkler is my cousin and I got a free copy.

Question: Should I give him a free copy of my VDW book when it comes out?

Disclaimer two: Scott did a post on a related matter here.)



If someone started an Institute to prove Graph Isomorphism is in P that would

be very odd since it could be that GI is not in P.

If someone started an Institute to study Graph Isomorphism that would be

much less odd (though still somewhat odd).



Does it make sense to have an openly biased think tank?



If a pro-gun-control person writes a book that proves that there weren't that many

guns in America in the early 1800's would you believe it?

If an anti-gun-control person writes a book claming that the more guns there are

the less crime there is, would you believe it?

The CATO Institute: A Libertarian Think Tank.

If they did an honest study of gun control and concluded that it does reduce

crime then would they publish it? I honestly do not know.

If they did an honest study of gun control and concluded that it increases

crime then would anyone believe it? Being openly biased might undermine their credibility.

The Tobacco Institute (they no longer exist). They produced reports

claiming that smoking was not unhealthy (or perhaps that the evidence is incomplete).

They were employed by the Tobacco industry. Did they ever have any credibility?

Did they do any unbiased science, perhaps on non-smoking issues?

I honestly don't know.

It is tempting to say Scientists should not have an opinion before they do a study. But this is clearly not correct in theory or practice. Scientists do indeed have an opinion, even an interest, in what a study will tell. Why is that different from the Tobacco institute? An honest scientist's preconceived notions are hopefully also based on science and not on who is paying him and not on other non-science factors.

An honest scientist, when faced with evidence that they are wrong, will hopefully pursue that evidence and perhaps change their mind. This might be easier in math than in science since Proof is our accepted criteria. For example, I doubt there are diehards who still think that NL ≠ coNL.

The New Patrons

A few centuries ago if you wanted to do science and not independently wealthy you needed help.

Most of the important astronomers and natural philosophers (as well as artists) in the 16th and 17th centuries depended on the patronage of powerful religious or political figures to fund their work. Patronage networks extended all the way from Emperors and Popes to regional nobles to artisans to peasants; even university positions were based to some extent on patronage. Scholarly careers in this period were driven by patronage, often starting in undistinguished universities or local schools or courts, and traveling closer or farther from centers of power as their fortunes rose and fell.

Today most scientists have salaried positions at universities and get funded by the government but with sequestration and budget cuts, scientists have to seek out other sources, such as industrial funds. We've long had various scholarships endowed by private donors: Sloan, Packard, MacArthur. Recently though we've seen some new patrons, the upper 1%, who want to help out where other funds are limited. Some of these work through endowed positions at universities, but we also see some who create foundations dedicated to funding directed at research.



In the past few months I came face-to-face, or at least in the same room, as two of them: Landon Clay in Oxford for the opening of the new Maths Institute partially funded by his foundation and Jim Simons, when I visited Stony Brook and had lunch in the Simons Center for Geometry and Physics. The Clay Mathematics Institute funds several mathematicians and offers the million dollar bounty on P v NP and other open questions. The Simons Foundation supports a few theoretical computer scientists, not to mention the Simons Institute in Berkeley.



Of course the more money coming into our field, the more research we can do. But patronage does have its other side.

Patronage, and the desire for more, also shaped the work and publications of scientists. Effusive dedications to current or potential patrons can be found in almost every scholarly publication, while the interests of a patron in a specific topic was a strong incentive to pursue said topic—or reframe one's work in terms of it. Galileo, for example, first presented the telescope as a naval instrument to military- and commerce-focused Republic of Venice; when he sought the more prestigious patronage of the Medici court in Florence, he instead promoted the astronomical potential of the device (by naming the moons of Jupiter after the Medicis).

 How much do the lessons of the 16-17th centuries still apply today?

Local Reductions

With the STOC deadline passing on Monday, now is a good time to look at the arXiv to see what has been posted since then. Hamid Jahanjou, Eric Miles and Emanuele Viola have a new paper, Local Reductions, that gives a new reduction from NTIME(t) to 3-SAT formulas of size t polylog(t). The twist to their new reduction: there is an NC0 circuit C that maps the number i to the ith clause. NC0 means every output bit depends on only a constant number of input bits. The proof uses old-fashioned parallel routing.



Should have some interesting applications. It does save a step in Williams' proof that ACC0 ≠ NEXP but the combined proofs are longer.



In other news, I've been getting several email from other CS chairs looking for students to hire as faculty in their departments. The latest CRA News is 59 pages, 50 of them are faculty job ads. It's a good year to be on the job market.

Four answers to the Recip problem

In my last post I asked you to solve the following question which

was from the Maryland Math Competition:



The inequalities 1/2 + 1/3 + 1/6 = 1 and 1/2 + 1/3 + 1/7 + 1/42 = 1

express 1 as a sum of three (resp. four) reciprocals.



Find five positive integers a,b,c,d,e such that

1/a + 1/b + 1/c + 1/d + 1/e = 1.



Prove that for any positive integer k GE 3 there exists positive intgers numbers d1,d2,...,dk

such that 1/d1 + ... + 1/dk.



The HS students had the following solutions.

I list the answers to part b first.  I sketch the proofs. They are all by induction.



1) Use 1/n = 1/(n+1) + 1/n(n+1).  This was the most common solution.  This leads to (2,3,7,43,1806) for part a.



2) Since the question itself gives the solution for m=2 and 3 we only need P(k) --> P(k+2)

Use 1/n =  1/2n + 1/3n + 1/6n.  This leads to (2,3,12,18,36).

One of the students later told me that knew the solution (i) but did it this way to

avoid having to multiply 42 by 43 which is needed to get part a using that solution.



3) Inductively that the largest denom n is even Use 1/n = 3/3n = 1/3n + 2/3n = 1/3n + 1/(3n/2)

Less than five students did 2b this way.  This leads to (2,3,7,63,126) for 2a.



4) If (d1,...,dn) is a solution then so is (2,2xd1,...,2xdn).

Only two student did it this way.  It leads to (2,4,6,14,84), which they both used.



NOBODY did in the non-inductive way mentioned in the last post.



There were THIRTY TWO solutions to 2b.  Several people had their part 2a and 2b not

related to each other at all.  This was far more solutions than I anticipated.

While grading I got good at adding reciprocals.

I list them in lex order along with how many people did that answer.

(This is likely approx- I may have miscounted a bit, but its basically right)



(2,3,7,43,1806) - 91 (linked to solution 1 above)



(2,3,7,48,336)  - 3



(2,3,7,56,168)  - 1



(2,3,7,63,126)  - 6 (linked to solution 3 above)



(2,3,7,70,105)  - 1



(2,3,8,25,600)  - 1



(2,3,8,30,120)  - 1



(2,3,8,32,96)   - 6



(2,3,8,36,72)   - 5



(2,3,8,42,56)   - 11



(2,3,9,21,126)  - 2



(2,3,9,24,72)   - 4



(2,3,9,27,54)   - 3



(2,3,10,20,60)  - 5



(2,3,11,22,33)  - 1



(2,3,12,15,60)  - 1



(2,3,12,16,48)  - 1



(2,3,12,14,84)  - 2 (linked to solution 4 above)



(2,3,12,18,36)  - 12 (linked to solution 2 above)



(2,4,5,25,100)  - 3



(2,4,5,30,60)   - 1



(2,4,6,14,84)   - 3



(2,4,6,16,48)   - 1



(2,4,6,18,36)   - 2



(2,4,6,20,30)   - 1



(2,4,7,12,42)   - 4



(2,4,7,14,28)   - 2



(2,4,8,12,24)   - 6



(2,4,8,10,40)   - 2



(2,5,6,10,30)   - 1



(2,5,6,12,20)   - 2



(3,4,5,6,20)    - 3

A problem on Reciprocals

(I thought I had posted this a while back but I can't find it in past blogs

so I think I did not. I DID post a diff problem on reciprocals.)



Here is the question I graded a while back on a  Maryland Math Olympiad.

I request that you do it and post your answer as a comment- I'll be curious

how your answers compare to the students who took it.

I will post the solutions the students used in my next post and comments

on how they were similar or different than yours.

The students had two hours to do five problems.

This was problem 2.



The equalities 1/2 + 1/3 + 1/6 = 1 and 1/2 + 1/3 + 1/7 + 1/42 = 1

express 1 as a sum of three (resp. four) reciprocals.



PART A: Find five distinct positive integers a,b,c,d,e  such that



       1/a + 1/b + 1/c + 1/d + 1/e = 1.





PART B: Prove that for any positive integer k  GE 3 there exists k distinct positive intgers numbers d1,...,dk such that



1/d1 + 1/d2 + ... + 1/dk = 1.