So you've got an iPhone XS in Space Grey. Congrats, so do 20 million other people. Maybe you have different cases but otherwise the hardware in all these phones are virtually identical. Yet you can tell with a glance that this is your phone. You can personalize apps and other elements of the home screen. It's your calendar and email and music.
What? You've dropped your phone over Niagara falls. Luckily you've backed up your data. So you go back to Apple and buy another Space Grey iPhone XS and restore your data. Physically it's a completely different phone but for all practical purposes it's though you still had the original phone. Your phone is not defined by the device but the data that resides on it.
It's not just phones. I can log into Google on anyone's Chrome browser and it will feel like my machine.
Now we've all heard about a future world where nobody owns cars and we get driven around in self-driving Ubers, Lyfts and Waymos. One argument against this world is that people feel connected to their cars and unwilling to commute in some generic vehicle. But one can also imagine the car knows who you are, knows how you like your music, your lighting, how you adjust your seats even how your car drives. It becomes your car. Maybe even has electronic bumper stickers that change to support your political party.
You can imagine the same for hotel rooms, your office, maybe even your apartment. It won't replicate your dog (or will it?) but as we get define more by our data than our things, do our things matter at all?
Thursday, February 14, 2019
Monday, February 11, 2019
I think ze was confused -- in favor of genderless pronouns
You've probably heard the following:
At first I didn't want to get an X but now that I have it, I can't imagine life without one.
X could be telegraph, radio, TV, color TV, VCR, CD player, streaming, Netflix, Amazon prime, an uber account, Washer and Dryer, Car Phones (remember those), Cell Phones. If you go back in history wrist watches or sun dials (or wrist-sun-dials!).
This has happened to me recently though not with an object. I read an article someplace saying that ze can be used instead of he or she. It was referring to nonbinaries (using `they' never quite sounded right) but actually it would be great if this was a general genderless pronoun. I am not making a political statement here (although I doubt I have any readers who are against genderless pronouns).
Once I came across the term ze I found places to use it and now I can't imagine not using it.
In a recent article I wrote I needed to say that someone was probably confused, but I did not know their gender. I used
Ze was probably confused
which is much better than
S/he was probably confused
He or she was probably confused
The student was probably confused
They were probably confused.
Note that the first two leave out nonbinaries.
0) In the article I put in a footnote saying what ze meant. In the future I may not have to.
1) Will ze catch on? This blog post is an attempt to hasten the practice.
2) Is there a term for his/her that is non-gendered? If not then maybe zer.
3) Will there be political pushback on this usage? If its phrased as a way to include nonbinaries than unfortunately yes. If its phrased as above as when you don't know the gender, what do you do, then no.
4) Is nonbinary the correct term? If not then please politely correct me in the comments.
5) Has Ms replaced Miss and Mrs?
I have used the term ze several times since then- often when I get email from a student such that I can't tell from the first name what their gender is, and I need to forward the email, such as
Ze wants to take honors discrete math but does not have the prerequisite, but
since ze placed in the top five in the math olympiad, we'll let zer take it.
At first I didn't want to get an X but now that I have it, I can't imagine life without one.
X could be telegraph, radio, TV, color TV, VCR, CD player, streaming, Netflix, Amazon prime, an uber account, Washer and Dryer, Car Phones (remember those), Cell Phones. If you go back in history wrist watches or sun dials (or wrist-sun-dials!).
This has happened to me recently though not with an object. I read an article someplace saying that ze can be used instead of he or she. It was referring to nonbinaries (using `they' never quite sounded right) but actually it would be great if this was a general genderless pronoun. I am not making a political statement here (although I doubt I have any readers who are against genderless pronouns).
Once I came across the term ze I found places to use it and now I can't imagine not using it.
In a recent article I wrote I needed to say that someone was probably confused, but I did not know their gender. I used
Ze was probably confused
which is much better than
S/he was probably confused
He or she was probably confused
The student was probably confused
They were probably confused.
Note that the first two leave out nonbinaries.
0) In the article I put in a footnote saying what ze meant. In the future I may not have to.
1) Will ze catch on? This blog post is an attempt to hasten the practice.
2) Is there a term for his/her that is non-gendered? If not then maybe zer.
3) Will there be political pushback on this usage? If its phrased as a way to include nonbinaries than unfortunately yes. If its phrased as above as when you don't know the gender, what do you do, then no.
4) Is nonbinary the correct term? If not then please politely correct me in the comments.
5) Has Ms replaced Miss and Mrs?
I have used the term ze several times since then- often when I get email from a student such that I can't tell from the first name what their gender is, and I need to forward the email, such as
Ze wants to take honors discrete math but does not have the prerequisite, but
since ze placed in the top five in the math olympiad, we'll let zer take it.
Thursday, February 07, 2019
An Immerman-Szelepcsényi Story
As a grad student in the late 80's I had the opportunity to witness many great and often surprising theorems in computational complexity. Let me tell you about one of them, the Immerman-Szelepcsényi result that nondeterministic space is closed under complement. I wish I had the original emails for this story but instead I'm working from memory and apologies if I get some of the details wrong. I'm expanding from a short version from the early days of this blog.
I started my graduate work at UC Berkeley in 1985 and then moved to MIT in the summer of '86, following my advisor Michael Sipser. In the summer of 1987, Neil Immerman, then at Yale, proved his famous result building on his work in descriptive complexity In those days you didn't email papers, he made copies and sent them by US postal mail to several major researchers in complexity including Sipser. But Sipser was away for the summer, I believe in Russia, and the paper sat in his office.
Immerman also sent the paper to a Berkeley professor, probably Manuel Blum, who gave it to one of his students who decided to speak about the result in a student-led seminar. I forgot who was the student, maybe Moni Naor. I was still on the Berkeley email list so I got the talk announcement and went into complexity ecstasy over the news. I asked Moni (or whomever was giving the talk) if he could tell me details and he sent me a nice write-up of the proof. Given the importance of the result, I sent the proof write-up out to the MIT theory email list.
Guess who was on the MIT theory list? Neil Immerman. Neil wrote back with his own explanation of the proof. Neil explained how it came out of descriptive complexity but as a pure write-up of a proof of the theorem, Moni did an excellent job.
We found out about Robert Szelepcsényi when his paper showed up a few months later in the Bulletin of the European Association for Theoretical Computer Science. Szelepcsényi came to the problem from formal languages, whether context-sensitive languages (nondeterministic linear space) was closed under complement. Szelepcsényi, an undergrad in Slovakia at the time, heard about the problem in a class he took. Szelepcsényi's proof was very similar to Immerman. Szelepcsényi's paper took longer to get to US researchers but likely was proven and written about the same time as Immerman.
Even though both papers were published separately we refer to the result as Immerman-Szelepcsényi and is now just some old important theorem you see in introductory theory classes.
I started my graduate work at UC Berkeley in 1985 and then moved to MIT in the summer of '86, following my advisor Michael Sipser. In the summer of 1987, Neil Immerman, then at Yale, proved his famous result building on his work in descriptive complexity In those days you didn't email papers, he made copies and sent them by US postal mail to several major researchers in complexity including Sipser. But Sipser was away for the summer, I believe in Russia, and the paper sat in his office.
Immerman also sent the paper to a Berkeley professor, probably Manuel Blum, who gave it to one of his students who decided to speak about the result in a student-led seminar. I forgot who was the student, maybe Moni Naor. I was still on the Berkeley email list so I got the talk announcement and went into complexity ecstasy over the news. I asked Moni (or whomever was giving the talk) if he could tell me details and he sent me a nice write-up of the proof. Given the importance of the result, I sent the proof write-up out to the MIT theory email list.
Guess who was on the MIT theory list? Neil Immerman. Neil wrote back with his own explanation of the proof. Neil explained how it came out of descriptive complexity but as a pure write-up of a proof of the theorem, Moni did an excellent job.
We found out about Robert Szelepcsényi when his paper showed up a few months later in the Bulletin of the European Association for Theoretical Computer Science. Szelepcsényi came to the problem from formal languages, whether context-sensitive languages (nondeterministic linear space) was closed under complement. Szelepcsényi, an undergrad in Slovakia at the time, heard about the problem in a class he took. Szelepcsényi's proof was very similar to Immerman. Szelepcsényi's paper took longer to get to US researchers but likely was proven and written about the same time as Immerman.
Even though both papers were published separately we refer to the result as Immerman-Szelepcsényi and is now just some old important theorem you see in introductory theory classes.
Sunday, February 03, 2019
Don't know Football but still want bet on the Superb Owl?
(Superb Owl is not a typo. I've heard (and it could be wrong) that the NFL guards their copyright so you can't even say `Buy Beer here for the YOU KNOW WHATl' but instead `Buy Beer here for the big game''. Stephen Colbert a long time ago go around this by calling the game Superb Owl.)
If I knew more about football I might place a bet related to the Superb Owl. What kind of bets can I place?
1) Bet the point spread: Last time I looked the Patriots were a 2.5 point favorite. So either bet that Patriots will win by more than 2.5 or the Rams will lose by less than 2.5 or just win.
2) Over-Under: bet that either the total score will be over 56.5 or under it.
There are prop-bets-- bets that are ABOUT the game but not related to the final score.
I've seen the following
1) Tom Brady will retire after the game. I wonder if Tom Brady (or a friend of his) could bet on this one knowing some inside information. Not i any state in America, but off-shore...
2) Jamie White will score the first touchdown.
3) Will Gladys Knight's National Anthem go longer than 1 minute, 50 seconds (it was 1:47 seconds a few days ago but it shifted to 1:50).
Amazingly, this last one is what Josh Hermsmeyer (on Nate Silver's Webpage) chose to focus on: here. Note that:
1) The people who picked 1 minute 50 seconds as the over-under probably didn't do much research. They might have set it to get the same number of people on both sides, which may explain the shift; however, I can't imagine this bet got that much action. Then again, I'm not that imaginative.
2) Josh DID. He did an analysis of what is likely (he thinks it will go longer)
3) So- can Josh bet on this an clean up? Can you bet on this and clean up?
4) There is an issue: Some kinds of bets are legal in some places (betting who will WIN or beat a point-spread is legal in Las Vegas-- the Supreme court struck down a federal anti-betting rule). Some prop bets are legal. The Gladys Knight one is not. Why not? Someone could have inside information! Gladys Knight would!
So you CAN bet Rams+2.5 beats the Patriots LEGALLY
but to bet Gladys Knight's National Anthem will take more than 1 minute 50 seconds you might need to use BITCOIN, and go to some offshore account. Too much sugar for a satoshi.
5) There is another issue- there is no such thing as a sure thing (I blogged on that here). People who bet on sports for a living (I know one such person and will blog about that later) play THE LONG GAME. So to say
I will withdraw X dollars (for large X) from my investments and bet it on
Gladys Knight's Star Spangled Banner to go more than 1 minute 50 seconds
because its a sure thing
Would be... a very bad idea.
The above was all written the day before Superb Owl. Now its the next day and Gladys Knight has sung the National Anthem. So who won the Gladys Knight Bowl? The answer is not as straightforward as it could be, see here.
The above was all written the day before Superb Owl. Now its the next day and Gladys Knight has sung the National Anthem. So who won the Gladys Knight Bowl? The answer is not as straightforward as it could be, see here.
Thursday, January 31, 2019
Phish Before Turkey
The Chronicle of Higher Education recently published a story Phishing Scheme Targets Professors’ Desire to Please Their Deans — All for $500 in Gift Cards. The same thing happened to me last fall.
Twas the day before Thanksgiving and an email went out to most of the faculty in my department.
Some faculty checked with me to see if this is real. One faculty called me to see what I wanted. Once I found out what was happening I sent a message to my entire faculty to ignore those emails.
Some faculty did reply to see what I want. The response:
Twas the day before Thanksgiving and an email went out to most of the faculty in my department.
From: Lance Fortnow <lancefortnow@yahoo.com>
Sent: Wednesday, November 21, 2018 1:45 PM
To: [name deleted]
Subject:
Hello,are you available?At the time I was in New Jersey visiting family. lancefortnow@yahoo.com is not my email. I do own fortnow@yahoo.com but don't email there, I rarely check it.
Some faculty checked with me to see if this is real. One faculty called me to see what I wanted. Once I found out what was happening I sent a message to my entire faculty to ignore those emails.
Some faculty did reply to see what I want. The response:
i need you to help me get an Amazon gifts card from the store,i will reimburse you back when i get to the office.One of our security faculty decided to follow up and replied "Sure! Let me get them for you. Could you provide more more information? e.g., amount and #cards. I can bring them on Monday." The reply:
The amount i want is $100 each in two (2) piece so that will make it a total of $200 l'll be reimbursing back to you.i need physical cards which you are going to get from the store. When you get them,just scratch it and take a picture of them and attach it to the email then send it to me here ok
He went a few more rounds before the phisher just stopped responding.
A week later, a different faculty member came to my office and said I wanted to see him but he's been out of town. I said it was nice to see him but I didn't ask to talk to him and we figured out the confusion was the phishing email.
Someone went through the trouble of creating a fake email address in my name, looking up the email addresses of the faculty in the department and individually emailing each of them, without realizing computer science professors won't fall for a gift card phishing attack. Or at least none of them admitted falling for it.
Friday, January 25, 2019
The Paradigm Shift in FinTech Computation and the need for a Computational Toolkit (Guest Post by Evangelos Georgiadis)
The Paradigm Shift in FinTech Computation and the need for a Computational Toolkit
(Guest Post by Evangelos Georgiadis)
We are experiencing a paradigm shift in finance as we are entering the era of algorithmic FinTech computation. (**And another yet to come. See **Future** below.) This era is marked by a shift in the role played by the theoretical computer scientist. In the not so distant past, the (financial) economist had the ultimate stamp of approval for how to study financial models, pricing models, mechanism design, etc. The economist was the ultimate gatekeeper of ideas and models, whereas the main role of the computer scientist was to turn these ideas or models into working code; in a sense, an obedient beaver/engineer. (In finance, the theoretical computer scientist more often than not wears the hat of the quant.)
In today's era, the role of the theoretical computer scientist has been elevated from the obedient engineer to the creative architect not only of models and mechanism designs but also of entire ecosystems. One example is blockchain based ecosystems. In the light of this promotion from obedient engineer to architect, we might need to re-hash the notion of 'sharing blame', as originally and elegantly voiced in On Quants by Professor Daniel W. Stroock, when things go wrong.)
The role change is also coupled by a shift in emphasis of computation that in turn necessitates a deeper understanding of (what this author would refer to as) distributed yet pragmatic complexity based crypto systems' that attempt to redefine 'trust' in terms of distributed computation.
This change necessitates an ability to think in terms of approximation (and lower/upper bounds) or other good-enough solutions that work on all inputs, rather than merely easy instances of problem types that usually lead to clean, exact formulas or solutions. Additionally, looking through the lens of approximation algorithms enables a different and often more insightful metric for dealing with intrinsically hard problems (for which often no exact or clean solutions exist.) Computer Scientists are trained in this way; however, financial economists are not. Might the economists actually get in the way?
Our tentative response: The economists are valuable and the solution to the dilemma is to equip them with the right 'computational toolkit'. Ideally, such a toolkit comprises computational tools and algorithms that enable automation of certain computational tasks which otherwise would necessitate more granular understanding at the level of a theoretical computer scientist (or mathematician)
OR be too cumbersome to perform by hand even for the expert.
Essentially, a toolkit even for the theoretical computer scientist that frees her from clerical work and enables computation to scale from clean cases, such as n=1, to pathological (yet far more realistic) cases, such as n=100000, all the way to the advanced and rather important (agnostic case or) symbolic case when n=k -- without much pain or agony.
The existence of such a toolkit would in turn do justice to the definition of FinTech Computation, which entails applying advanced computational techniques not necessarily information techniques) to financial computation. in fact, this author is part of building such an infrastructure solution which
necessitates the underlying programming language [R-E-CAS-T] to have intrinsic hybrid capabilities -- symbolic as well as numeric.
One step towards this "automation" conquest is shown in A combinatorial-probabilistic analysis of bitcoin attacks with Doron Zeilberger. The work illustrates an algorithmic risk analysis of the bitcoin protocol via symbolic computation, as opposed to the meticulous, yet more laborious by hand conquest shown by the European duo in Double spend races Heavy usage of the "Wilf-Zeilberger algorithmic proof theory" one of the cornerstones in applied symbolic computation, enabled automated recurrence discovery and algorithmic derivation of higher-order asymptotics. For example, in terms of asymptotics tools: the ability to internalize a very dense body of mathematics, such as the G.D. Birkhoff and W.J. Trjitzinsky method, symbolically, automates the process of computing asymptotics of solutions of recurrence equations; a swiss army knife for any user.
<**Future**>
What does the future entail for FinTech Computation ?
[My two satoshis on this]
Where are we headed in terms of type of computation ?
Blockchain based systems, even though some of us (including this author) have noticed fundamental flaws, seem to still have momentum, at least, judging from recent news articles about companies becoming blockchain technology friendly. Ranging from (of course) exchanges such as our friends at Binance and BitMEX, we have major smartphone makers such as Samsung, Huawei, and HTC. The favorable sentiment towards blockchain technology is shared even amongst top tier U.S. banks.
Can one deduce success or failure momentum from the citation count distribution of the paper that laid grounds to this technology ? Bitcoin: A Peer-to-Peer Electronic Cash System)
If we look at crypto(currencies), one of many challenges for these blockchain based systems is the high maintenance cost. Certainly in terms of energy consumption when it comes to the process of mining -- whether Proof-of-Work (PoW) is replaced by Proof-of-Stake (PoS) or some other more energy efficient consensus variant. (This author is aware of various types of optimizations that have been used.)
A few questions that have bugged this author every since ...
a) Is there a natural way to formalize the notion of energy consumption for consensus mechanisms?
b) What about formalizing an energy-efficient mechanism design ?)
(The idea of savings when PoW is replaced by PoS as intended by our friends at the Ethereum Foundation has been around for some time but the point of this author is, the value of 0.99*X (where X is a supernatural number [a la Don E. Knuth style]), is still a big quantity; too big for an environmentalist ?)
So, what comes next ?
[... the satoshis are still on the table.]
Daniel Kane has brought to my attention that quantum computation -- the seemingly next paradigm shift in which again the role of TCS seem inextricably interwoven -- may lead to blockchain based systems being replaced by less expensive (at least in terms of energy consumption) quantum based systems. (Crypto might get replaced by Quantum (money). :-)) One such pioneering approach is masterfully articulated by Daniel Kane in "Quantum Money from Modular Forms.
(Guest Post by Evangelos Georgiadis)
We are experiencing a paradigm shift in finance as we are entering the era of algorithmic FinTech computation. (**And another yet to come. See **Future** below.) This era is marked by a shift in the role played by the theoretical computer scientist. In the not so distant past, the (financial) economist had the ultimate stamp of approval for how to study financial models, pricing models, mechanism design, etc. The economist was the ultimate gatekeeper of ideas and models, whereas the main role of the computer scientist was to turn these ideas or models into working code; in a sense, an obedient beaver/engineer. (In finance, the theoretical computer scientist more often than not wears the hat of the quant.)
In today's era, the role of the theoretical computer scientist has been elevated from the obedient engineer to the creative architect not only of models and mechanism designs but also of entire ecosystems. One example is blockchain based ecosystems. In the light of this promotion from obedient engineer to architect, we might need to re-hash the notion of 'sharing blame', as originally and elegantly voiced in On Quants by Professor Daniel W. Stroock, when things go wrong.)
The role change is also coupled by a shift in emphasis of computation that in turn necessitates a deeper understanding of (what this author would refer to as) distributed yet pragmatic complexity based crypto systems' that attempt to redefine 'trust' in terms of distributed computation.
This change necessitates an ability to think in terms of approximation (and lower/upper bounds) or other good-enough solutions that work on all inputs, rather than merely easy instances of problem types that usually lead to clean, exact formulas or solutions. Additionally, looking through the lens of approximation algorithms enables a different and often more insightful metric for dealing with intrinsically hard problems (for which often no exact or clean solutions exist.) Computer Scientists are trained in this way; however, financial economists are not. Might the economists actually get in the way?
Our tentative response: The economists are valuable and the solution to the dilemma is to equip them with the right 'computational toolkit'. Ideally, such a toolkit comprises computational tools and algorithms that enable automation of certain computational tasks which otherwise would necessitate more granular understanding at the level of a theoretical computer scientist (or mathematician)
OR be too cumbersome to perform by hand even for the expert.
Essentially, a toolkit even for the theoretical computer scientist that frees her from clerical work and enables computation to scale from clean cases, such as n=1, to pathological (yet far more realistic) cases, such as n=100000, all the way to the advanced and rather important (agnostic case or) symbolic case when n=k -- without much pain or agony.
The existence of such a toolkit would in turn do justice to the definition of FinTech Computation, which entails applying advanced computational techniques not necessarily information techniques) to financial computation. in fact, this author is part of building such an infrastructure solution which
necessitates the underlying programming language [R-E-CAS-T] to have intrinsic hybrid capabilities -- symbolic as well as numeric.
One step towards this "automation" conquest is shown in A combinatorial-probabilistic analysis of bitcoin attacks with Doron Zeilberger. The work illustrates an algorithmic risk analysis of the bitcoin protocol via symbolic computation, as opposed to the meticulous, yet more laborious by hand conquest shown by the European duo in Double spend races Heavy usage of the "Wilf-Zeilberger algorithmic proof theory" one of the cornerstones in applied symbolic computation, enabled automated recurrence discovery and algorithmic derivation of higher-order asymptotics. For example, in terms of asymptotics tools: the ability to internalize a very dense body of mathematics, such as the G.D. Birkhoff and W.J. Trjitzinsky method, symbolically, automates the process of computing asymptotics of solutions of recurrence equations; a swiss army knife for any user.
<**Future**>
What does the future entail for FinTech Computation ?
[My two satoshis on this]
Where are we headed in terms of type of computation ?
Blockchain based systems, even though some of us (including this author) have noticed fundamental flaws, seem to still have momentum, at least, judging from recent news articles about companies becoming blockchain technology friendly. Ranging from (of course) exchanges such as our friends at Binance and BitMEX, we have major smartphone makers such as Samsung, Huawei, and HTC. The favorable sentiment towards blockchain technology is shared even amongst top tier U.S. banks.
Can one deduce success or failure momentum from the citation count distribution of the paper that laid grounds to this technology ? Bitcoin: A Peer-to-Peer Electronic Cash System)
If we look at crypto(currencies), one of many challenges for these blockchain based systems is the high maintenance cost. Certainly in terms of energy consumption when it comes to the process of mining -- whether Proof-of-Work (PoW) is replaced by Proof-of-Stake (PoS) or some other more energy efficient consensus variant. (This author is aware of various types of optimizations that have been used.)
A few questions that have bugged this author every since ...
a) Is there a natural way to formalize the notion of energy consumption for consensus mechanisms?
b) What about formalizing an energy-efficient mechanism design ?)
(The idea of savings when PoW is replaced by PoS as intended by our friends at the Ethereum Foundation has been around for some time but the point of this author is, the value of 0.99*X (where X is a supernatural number [a la Don E. Knuth style]), is still a big quantity; too big for an environmentalist ?)
So, what comes next ?
[... the satoshis are still on the table.]
Daniel Kane has brought to my attention that quantum computation -- the seemingly next paradigm shift in which again the role of TCS seem inextricably interwoven -- may lead to blockchain based systems being replaced by less expensive (at least in terms of energy consumption) quantum based systems. (Crypto might get replaced by Quantum (money). :-)) One such pioneering approach is masterfully articulated by Daniel Kane in "Quantum Money from Modular Forms.
Thursday, January 24, 2019
Machine Learning and Wind Turbines
My daughter Molly spent six weeks on an environmental program in China last summer. When she got back she had to do a report on machine learning and wind turbines used for clean energy generation. What does machine learning have to do with wind turbines? Plenty it turns out and it tell us a lot about the future of programming.
Sudden changes in wind can cause damage to the blades of the turbine. Maintenance is very expensive especially for turbines in the sea and a broken turbine generates no electricity. To catch these changes ahead of time you can mount a Lidar on top of the turbine.
The Lidar can detect wind gusts from about 100 meters ahead, giving about 10 seconds to react. In that time you can rotate the blades, or the whole turbine itself to minimize any damage. Here's a video describing the situation.
How do you do the computations to convert the Lidar data into accurate representations of wind gusts and then how to best adjust for them? You could imagine some complex fluid dynamics computation, which gets even more complex when you several wind turbines in front of each other. Instead you can use the massive amount of data you have collected by sensors on the turbine and the Lidar information and train a neural network. Training takes a long time but a trained network can quickly determine a good course of action. Now neural networks can always make mistakes but unlike self-driving cars, a mistake won't kill anyone, just possibly cause more damage. Since on average you can save considerable maintenance costs, using ML here is a big win.
I've obviously over simplified the above but I really like this example. This is not an ML solution to a standard AI question like image recognition or playing chess. Rather we are using ML to make a difficult computation tractable mostly by using ML on available data and that changes how we think about programming complex tasks.
Sunday, January 20, 2019
ACM prize and some thoughts on the Godel Prize
(ADDED LATER: deadlines for some of these awards have passed but here are ones
coming up soon:
Godel Prize: Feb 15
Knuth Prize: Feb 15
SIGACT News Dist Service: March 1
)
As Lance Tweeted, and I will re-iterate, nominations for the following prizes
are due soon and you can nominate people here
Godel Prize for outstanding paper in TCS. (Godel mentioned P vs NP in a letter to Von Neumann. I've heard it said that its too bad they didn't work on it-- either it would be solved or we'd know its hard. Frankly, I think enough smart people have worked on it that we already know its hard.)
Knuth Prize for outstanding contributions to foundations of Computer Science. (its a greater honor to have a prize named after you in your lifetime then to win a prize!)
Dijkstra Prize (I wonder if having `ijk' in his name inspired him to work in algorithms)
Kanellakis Theory and Practice Award.
Lawler Award for Humanitarian Contributions within CS and Informatics.
ACM Distinguished Service Award
Danny Lewin Best Student Paper Award (best student paper at STOC)
The Best Paper award (Best paper at STOC, Best paper at FOCS)
(The last two I doubt you can nominate someone for.)
A few thoughts on the Godel Prize:
coming up soon:
Godel Prize: Feb 15
Knuth Prize: Feb 15
SIGACT News Dist Service: March 1
)
As Lance Tweeted, and I will re-iterate, nominations for the following prizes
are due soon and you can nominate people here
Godel Prize for outstanding paper in TCS. (Godel mentioned P vs NP in a letter to Von Neumann. I've heard it said that its too bad they didn't work on it-- either it would be solved or we'd know its hard. Frankly, I think enough smart people have worked on it that we already know its hard.)
Knuth Prize for outstanding contributions to foundations of Computer Science. (its a greater honor to have a prize named after you in your lifetime then to win a prize!)
Dijkstra Prize (I wonder if having `ijk' in his name inspired him to work in algorithms)
Kanellakis Theory and Practice Award.
Lawler Award for Humanitarian Contributions within CS and Informatics.
ACM Distinguished Service Award
Danny Lewin Best Student Paper Award (best student paper at STOC)
The Best Paper award (Best paper at STOC, Best paper at FOCS)
(The last two I doubt you can nominate someone for.)
A few thoughts on the Godel Prize:
1) You can win the Godel Prize twice and some people have: Goldwasser, Hastad, Arora, Szegedy, Spielman, Teng. Spielman-Teng have won it as a team twice.
2) GLAD there is no limit to how many can win. If a paper has a lot of people on it (and this has happened) then FINE, they're all winners! According to The Big Bang Theory (the TV show, not the theory) in Physics at most 3 can win a Nobel Prize in Physics for the same breakthrough in a given year. The show itself shows how stupid the policy is.
3) I either knew and forgot or never knew that DPDA Equiv is decidable! Glad to now it just in time for teaching Automata theory this spring.
4) Looking over the list reminded me that there are some papers in the intersection of those I want to read and those I am able to read! Though not many. Most I want to read but they seem hard.
5) The Kanellakis award is for theory that is PRACTICAL. Could someone win a Godel AND a Kannellakis award for the same paper (or set of papers). I found one sort-of case ( (a) below) and one definite case ( (b) below).
a) Moshe and Wolper won the 2000 Godel Prize for Temporal Logic and Finite Automata (I should also read that before my class starts)
Holtzmann, Kurshan, Vardi, and Wolpert won the 2005 Kanellakis prize for Formal Verification Tools.
I assume the two works are related.
b) Freund and Schapire won the 2003 Godel Prize and the 2004 Kanellakis Award, both for their work on boosting in Machine Learning.
6) Why is it the Godel Prize and the Kanellakis Award? What is the diff between a prize and an award? A quick Google Search says that an Award is a token of effort and merit, while a Prize is something you win in a competition. I doubt that applies. I suspect they are called Prize and Award from historical accident. Does anyone know?
Subscribe to:
Posts (Atom)