Fwd: TALK:Thursday 5-16-13 Succinct Non-Interactive Arguments via Linear Interactive Proofs

What the what ?? Only the words in isolation make any sense ....

---------- Forwarded message ----------
From: CSAIL Event Calendar <eventcalendar@csail.mit.edu>
Date: Mon, May 13, 2013 at 7:49 PM
Subject: TALK:Thursday 5-16-13 Succinct Non-Interactive Arguments via Linear Interactive Proofs
To: seminars@csail.mit.edu



Succinct Non-Interactive Arguments via Linear Interactive Proofs
CIS Seminars 2012/2013
Speaker: Alessandro Chiesa
Speaker Affiliation: MIT
Host: CIS Seminar

Date: 5-16-2013
Time: 10:30 AM - 12:00 PM
Location: 32-D507

 Succinct non-interactive arguments (SNARGs) enable verifying NP statements
with lower complexity than required for classical NP verification.
Traditionally, the focus has been on minimizing the length of such arguments;
nowadays researchers have focused also on minimizing verification time, by
drawing motivation from the problem of delegating computation.

A common relaxation is a preprocessing SNARG, which allows the verifier to
conduct an expensive offline phase that is independent of the statement to be
proven later. Recent constructions of preprocessing SNARGs have achieved
attractive features: they are publicly-verifiable, proofs consist of only O(1)
encrypted (or encoded) field elements, and verification is via arithmetic
circuits of size linear in the NP statement. Additionally, these constructions
seem to have "escaped the hegemony" of probabilistically-checkable proofs
(PCPs) as a basic building block of succinct arguments.

We present a general methodology for the construction of preprocessing
SNARGs, as well as resulting concrete efficiency improvements. Our results are
achieved by studying a natural extension of the interactive proof model that
considers algebraically-bounded provers; this new setting is analogous to the
common study of algebraically-bounded "adversaries" in other fields, such
as pseudorandomness and randomness extraction. More concretely, in this work
we focus on linear (or affine) provers, and provide several constructions of
(succinct two-message) linear-interactive proofs (LIPs) for NP. We then show
how to generically compile LIPs into preprocessing SNARGs.

Joint work with Nir Bitansky, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth.

Relevant URL(S):
For more information please contact: Holly A Jones, 617-253-6098, hjones01@csail.mit.edu


_______________________________________________
Seminars mailing list
Seminars@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/seminars

RE: geeksta rap

> -----Original Message-----

> From: Shantanu Singh

>

> ---------- Forwarded message ----------

> From: Vebjorn Ljosa

> Subject: Re: Fun weekend read

>

> On Sat, May 4, 2013 at 8:43 AM, Shantanu Singh wrote:

> > http://www.newyorker.com/online/blogs/elements/2013/05/a-most-profound-math-problem.html

>

>

> If P = NP, the geeksta rappers will need to come up with some new

> putdowns.

>

> > Yo, MC Plus Plus, my rhymes are so phat, I'm PSPACE-complete but I'll

> > reduce you to 3-SAT.

> > My crew is so hard that we roll in NP, … With more power than

> > multitape Turing Machines.

> > Blowin' up the rap scene faster than factorial functions, I'm dope

> > like PNP transistors and I'll saturate your junctions.

> > By the time you've rhymed one line, I've already busted ten; You rap

> > in exponential time and I'm big-O of log(n).

> >

> > http://www.monzy.com/intro/drama_lyrics.html

>

> Vebjorn

 

You know you're reading the New Yorker when there's a name-drop of David Foster Wallace even in an article on P=?NP. These litterateurs ... sigh.

 

"A few of the Clay problems are long-standing head-scratchers. The Riemann hypothesis, for example, made its debut in 1859. By contrast, P versus NP is relatively young, having been introduced by the University of Toronto mathematical theorist Stephen Cook in 1971, in a paper titled “The complexity of theorem-proving procedures,” though it had been touched upon two decades earlier in a letter by Kurt Gödel, whom David Foster Wallace branded “modern math’s absolute Prince of Darkness.” The question inherent in those three letters is a devilish one: Does P (problems that we can easily solve) equal NP (problems that we can easily check)?"

 

TED thinking

An article bashing Tim O'Reilly:

http://thebaffler.com/past/the_meme_hustler

 

The reason I like this article is for coining the term "TED elitists" - as a nice term for pseudo-intellectuals - the type who mistake the infotainment piffle of TED as intellectual discourse ...

 

Another interesting monograph on "TED thinking" 

http://blogs.hbr.org/haque/2013/03/lets_save_great_ideas_from_the.html

 

"It ain't what you don't know that will kill you. It's what you know
for sure that just ain't so."
-- somebody

FJ on TV

Boy !!  This is no way matches how I sound or appear to myself ....

http://videolectures.net/machine_janoos_networks/

Ravishankar

So --- 2 days ago driving home from work and listening to Pandora - this piece comes up selected by Pandora's randomness.

 

http://www.youtube.com/watch?v=AKceywea5T8

 

Initially - I go  "What the fuck Pandora -what bloody rubbish is this?" - but I'm too busy driving to change it. Or maybe I feel that despite it's strange sounds it has potential. So I continue to listen.

 

And it soon turns into one of the most psychedelic and mind-bending pieces of music I have ever heard. At that moment - for the first time - I realize what a serious genius Ravishankar was.  

 

And he dies the next day ... :-/

 

Aren't you lucky I don't think you are particularly smart ?

A full jar

When things in your life seem almost too much to handle, when 24 hours in a day are not enough, remember the mayonnaise jar and the 2 Beers.

A professor stood before his philosophy class and had some items in front of him. When the class began, he wordlessly picked up a very large and empty mayonnaise jar and proceeded to fill it with golf balls. He then asked the students if the jar was full. They agreed that it was.

The professor then picked up a box of pebbles and poured them into the jar. He shook the jar lightly. The pebbles rolled into the open areas between the golf balls. He then asked the students again if the jar was full. They agreed it was.

The professor next picked up a box of sand and poured it into the jar. Of course, the sand filled up everything else. He asked once more if the jar was full.. The students responded with a unanimous 'yes.'

The professor then produced two Beers from under the table and poured the entire contents into the jar effectively filling the empty space between the sand.The students laughed..

'Now,' said the professor as the laughter subsided, 'I want you to recognize that this jar represents your life. The golf balls are the important things---your family, your children, your health, your friends and your favorite passions---and if everything else was lost and only they remained, your life would still be full. The pebbles are the other things that matter like your job, your house and your car.. The sand is everything else---the small stuff.

'If you put the sand into the jar first,' he continued, 'there is no room for the pebbles or the golf balls. The same goes for life.

If you spend all your time and energy on the small stuff you will never have room for the things that are important to you.

Pay attention to the things that are critical to your happiness.

Spend time with your children. Spend time with your parents. Visit with grandparents. Take your spouse out to dinner. Play another 18. There will always be time to clean the house and mow the lawn.

Take care of the golf balls first---the things that really matter. Set your priorities. The rest is just sand.

One of the students raised her hand and inquired what the Beer represented. The professor smiled and said, 'I'm glad you asked.' The Beer just shows you that no matter how full your life may seem, there's always room for a couple of Beers with a friend.

Just shut up and drink

 

http://m.newyorker.com/online/blogs/frontal-cortex/2012/06/wine-taste.html

To quote:

 

If these blind testings teach us anything, it's that for the vast majority of experts and amateurs fine-grained perceptual judgments are impossible. Instead, ...,  our expectations of the wine are often more important than what's actually in the glass. When we take a sip of wine, we don't taste the wine first, and the cheapness or expensiveness second. We taste everything all at once, in a single gulp of thiswineisMoutonRothschild, or thiswineisfromSouthJersey. As a result, if we think a wine is cheap, then it will taste cheap. And if we think we are tasting a premier cru, then we will taste a premier cru. Our senses are vague in their instructions, and we parse their inputs based upon whatever other knowledge we can summon to the surface. It's not that those new French oak barrels or carefully pruned vines don't matter—it's that the logo on the bottle and price tag often matter more.

 

 

 

Why do we dream - BBC Horizon

> -----Original Message-----

> From: Arindam Bhattacharya [mailto:arindamb86@gmail.com]

> http://www.youtube.com/watch?v=9nmVzXxdUeU&repost

 

Really good documentary.

I used to watch Horizon on BBC in India - it was - and probably still is - one of the best science TV shows. I've seen great stuff - including documentaries on plate tectonics, apoptosis, Fermat's last theorem, the Riemann hypothesis, the discovery of DNA, the works of Darwin's, Fleming, Priestley, Mendel, Curie and what not.

I would say this is the show that made me want to get into science. Unfortunately, the real practice of science bears little resemblance to this romantic portrayal of it. Real science is dirty, messy and like the conversation goes:

CIA Superior: What did we learn, Palmer?

CIA Officer: I don't know, sir.

CIA Superior: I don't fuckin' know either. I guess we learned not to do it again.

CIA Officer: Yes, sir.

CIA Superior: I'm fucked if I know what we did.

What a lovely Friday

Sipping on chilled beer.

Hi-def music in my head.

Looking out on the NYC skyline

Ominous rain clouds in the background.

Grey, blue and white.

And the Hudson shimmering

With sunrays bursting through.

 

 

 

 

The Conversion of a Climate-Change Skeptic

Nice article - read through it and let me know your thoughts.

 

Through multiple conversations, I've begun to notice this general trend about the climate-change skeptic argument  - that it more and more resembles the "smoking doesn't cause cancer" argument of 20 years ago, in that the points raised are technically true but push the boundaries of plausibility. Y

 

Yes - there is the "correlation is not causation" enjoinder about cigarettes causing cancer (the canard with which Sir Ronald Fisher infamously fought the ban on smoking). But we human beings have the innate capacity to reason through such statistical niceties taken to absurd levels.

On a side note, this is one of the main attractions of the (mathematically rigorous) framework of Bayesianism, that it allows you to make statement likes "it is more likely than not that xyz is the cause of abc", rather than getting trapped in the vaccous sophism of classical statistics.

 

For me the anthropogenic climate change case has a very simple and powerful structure:

 

a) Data undeniably shows that the earth is getting warmer - and that it is doing so much faster than at any earlier non-catastrophic period. 

 

b) CO2 is an undeniable green house gas. No sophisticated proof is need - all that you need is a glass beaker, co2 gas, and sunlight. A very trivial high-school science project.

 

c) Human beings have undeniably produced a lot of CO2 and other greenhouse gases. Again - no complex shit is needed. Just figure out - over the past 100 years how much hydrocarbon have we burnt - how much total CO2 was produced and what % of the current CO2 content of the atmosphere it is. 

 

Now - yes there are lots of unknowns, unknowables, uncertainities and margins of error and what not. But from an Occam's razor point of view, how does one in all intellectual honesty reject this simple argument in favor of more unprovable sci-fi theories like solar cycles and galactic trends, magneto-thermal effect, etc.

 

  

The Conversion of a Climate-Change Skeptic

By RICHARD A. MULLER

Berkeley, Calif.

CALL me a converted skeptic. Three years ago I identified problems in previous climate studies that, in my mind, threw doubt on the very existence of global warming. Last year, following an intensive research effort involving a dozen scientists, I concluded that global warming was real and that the prior estimates of the rate of warming were correct. I'm now going a step further: Humans are almost entirely the cause.

My total turnaround, in such a short time, is the result of careful and objective analysis by the Berkeley Earth Surface Temperature project, which I founded with my daughter Elizabeth. Our results show that the average temperature of the earth's land has risen by two and a half degrees Fahrenheit over the past 250 years, including an increase of one and a half degrees over the most recent 50 years. Moreover, it appears likely that essentially all of this increase results from the human emission of greenhouse gases.

These findings are stronger than those of the Intergovernmental Panel on Climate Change, the United Nations group that defines the scientific and diplomatic consensus on global warming. In its 2007 report, the I.P.C.C. concluded only that most of the warming of the prior 50 years could be attributed to humans. It was possible, according to the I.P.C.C. consensus statement, that the warming before 1956 could be because of changes in solar activity, and that even a substantial part of the more recent warming could be natural.

Our Berkeley Earth approach used sophisticated statistical methods developed largely by our lead scientist, Robert Rohde, which allowed us to determine earth land temperature much further back in time. We carefully studied issues raised by skeptics: biases from urban heating (we duplicated our results using rural data alone), from data selection (prior groups selected fewer than 20 percent of the available temperature stations; we used virtually 100 percent), from poor station quality (we separately analyzed good stations and poor ones) and from human intervention and data adjustment (our work is completely automated and hands-off). In our papers we demonstrate that none of these potentially troublesome effects unduly biased our conclusions.

The historic temperature pattern we observed has abrupt dips that match the emissions of known explosive volcanic eruptions; the particulates from such events reflect sunlight, make for beautiful sunsets and cool the earth's surface for a few years. There are small, rapid variations attributable to El Niño and other ocean currents such as the Gulf Stream; because of such oscillations, the "flattening" of the recent temperature rise that some people claim is not, in our view, statistically significant. What has caused the gradual but systematic rise of two and a half degrees? We tried fitting the shape to simple math functions (exponentials, polynomials), to solar activity and even to rising functions like world population. By far the best match was to the record of atmospheric carbon dioxide, measured from atmospheric samples and air trapped in polar ice.

Just as important, our record is long enough that we could search for the fingerprint of solar variability, based on the historical record of sunspots. That fingerprint is absent. Although the I.P.C.C. allowed for the possibility that variations in sunlight could have ended the "Little Ice Age," a period of cooling from the 14th century to about 1850, our data argues strongly that the temperature rise of the past 250 years cannot be attributed to solar changes. This conclusion is, in retrospect, not too surprising; we've learned from satellite measurements that solar activity changes the brightness of the sun very little.

How definite is the attribution to humans? The carbon dioxide curve gives a better match than anything else we've tried. Its magnitude is consistent with the calculated greenhouse effect — extra warming from trapped heat radiation. These facts don't prove causality and they shouldn't end skepticism, but they raise the bar: to be considered seriously, an alternative explanation must match the data at least as well as carbon dioxide does. Adding methane, a second greenhouse gas, to our analysis doesn't change the results. Moreover, our analysis does not depend on large, complex global climate models, the huge computer programs that are notorious for their hidden assumptions and adjustable parameters. Our result is based simply on the close agreement between the shape of the observed temperature rise and the known greenhouse gas increase.

It's a scientist's duty to be properly skeptical. I still find that much, if not most, of what is attributed to climate change is speculative, exaggerated or just plain wrong. I've analyzed some of the most alarmist claims, and my skepticism about them hasn't changed.

Hurricane Katrina cannot be attributed to global warming. The number of hurricanes hitting the United States has been going down, not up; likewise for intense tornadoes. Polar bears aren't dying from receding ice, and the Himalayan glaciers aren't going to melt by 2035. And it's possible that we are currently no warmer than we were a thousand years ago, during the "Medieval Warm Period" or "Medieval Optimum," an interval of warm conditions known from historical records and indirect evidence like tree rings. And the recent warm spell in the United States happens to be more than offset by cooling elsewhere in the world, so its link to "global" warming is weaker than tenuous.

The careful analysis by our team is laid out in five scientific papers now online at BerkeleyEarth.org. That site also shows our chart of temperature from 1753 to the present, with its clear fingerprint of volcanoes and carbon dioxide, but containing no component that matches solar activity. Four of our papers have undergone extensive scrutiny by the scientific community, and the newest, a paper with the analysis of the human component, is now posted, along with the data and computer programs used. Such transparency is the heart of the scientific method; if you find our conclusions implausible, tell us of any errors of data or analysis.

What about the future? As carbon dioxide emissions increase, the temperature should continue to rise. I expect the rate of warming to proceed at a steady pace, about one and a half degrees over land in the next 50 years, less if the oceans are included. But if China continues its rapid economic growth (it has averaged 10 percent per year over the last 20 years) and its vast use of coal (it typically adds one new gigawatt per month), then that same warming could take place in less than 20 years.

Science is that narrow realm of knowledge that, in principle, is universally accepted. I embarked on this analysis to answer questions that, to my mind, had not been answered. I hope that the Berkeley Earth analysis will help settle the scientific debate regarding global warming and its human causes. Then comes the difficult part: agreeing across the political and diplomatic spectrum about what can and should be done.

Richard A. Muller, a professor of physics at the University of California, Berkeley, and a former MacArthur Foundation fellow, is the author, most recently, of "Energy for Future Presidents: The Science Behind the Headlines."

Theory of Interest

I've started to read Irving Fisher's highly influential and transformative text on economic theory "The theory of interest" and here is a wonderful excerpt from his introduction:

 

Income is a series of events.

 

According to the modern theory of relativity the elementary reality is not matter, electricity, space, time, life or mind, but events. For each individual only those events which come within the purview of his experience are of direct concern. It is these events—the psychic experiences of the individual mind—which constitute ultimate income for that individual. The outside events have significance for that individual only in so far as they are the means to these inner events of the mind. The human nervous system is, like a radio, a great receiving instrument. our brains serve to transform into the stream of our psychic life those outside events, which happen to us and stimulate our nervous system.

 

But the human body is not ordinarily regarded as an owned object, and only those events in consciousness traceable to owned objects other than the human body are generally admitted to be psychic income. However, the human machine still plays a rôle in so far as, through its purposeful activities, it produces, or helps produce, other owned objects which are material sources of desirable events—food, houses, tools, and other goods, which in their turn set in motion a chain of operations whose ultimate effect is registered in our stream of consciousness. The important consideration from this point of view is that human beings are ever striving to control the stream of their psychic life by appropriating and utilizing the materials and forces of nature. In man's early history he had little command over his environment. He was largely at the mercy of natural forces—wind and lightning, rain and snow, heat and cold. but today man protects himself from these by means of those contrivances called houses, clothing, and furnaces. He diverts the lightning by means of lightning rods. He increases his food supply by means of appropriated land, farm buildings, plows, and other implements. He then refashions the food by means of mills, grinding machinery, cook-stoves and other agencies, and by the labor of human bodies, including his own.

 

Neither these intermediate processes of creation and alteration nor the money transactions following them are of significance except as they are the necessary or helpful preliminaries to psychic income—human enjoyment. We must be careful lest, in fixing our eyes on such preliminaries, especially money transactions, we overlook the much more important enjoyment which it is their business to yield. Directors and managers providing income for thousands of people sometimes think of their corporation merely as a great money-making machine. In their eyes, its one purpose is to earn money dividends for the stock-holders, money interest for the bondholders, money wages and money salaries for the employees. What happens after these payments are made seems private a matter to concern them. Yet that is the nub of the whole arrangement. It is only what we carry out of the market place into our homes and private lives which really counts. Money is of no use to us until it is spent. The ultimate wages are not paid in terms of money but in the enjoyments it buys. The dividend check becomes income in the ultimate sense only when we eat the food, wear the clothes, or ride in the automobile which are bought with the check.

Statistics in Excel

A nice note on the headaches that ensue when using Excel to do data-analysis :

 

http://biostat.mc.vanderbilt.edu/twiki/bin/view/Main/ExcelProblems

 

 

The next Sergei Zuckerberg

Interesting theories ...

http://diegobasch.com/exploiting-silicon-valley

Re: indians in NJ

Funny ....

On Tue, Jun 5, 2012 at 2:50 PM, Shantanu Singh <titosingh@gmail.com> wrote:

You must have read this http://goo.gl/oZKNw , the article that came to
define a white american's view of Edison.

Some gems
- For a while, we assumed all Indians were geniuses. Then, in the
1980s, the doctors and engineers brought over their merchant cousins,
and we were no longer so sure about the genius thing. In the 1990s,
the not-as-brilliant merchants brought their even-less-bright cousins,
and we started to understand why India is so damn poor.

- In retrospect, I question just how good our schools were if "dot
heads" was the best racist insult we could come up with for a group of
people whose gods have multiple arms and an elephant nose