Harry Buhrman on quantum algorithms and cryptography

 |   |  Conversations

Harry Buhrman portrait Harry Buhrman is head of the research group ‘Algorithms and Complexity’ at the Centrum Wiskunde & Informatica, Amsterdam, which he joined in 1994. Since 2000 he also has a joint appointment as full professor of computer science at the University of Amsterdam. Buhrman’s research focuses on quantum computing, algorithms, complexity theory, and computational biology. In 2003 he obtained a prestigious Vici award and was coordinator of several national and international projects.

Buhrman is editor of several international journals and is member of various advisory and scientific boards, such as the advisory board of the Institute for Quantum Computing (Waterloo, Canada).

Luke Muehlhauser: In theory, position-based quantum cryptography could ensure that certain tasks could only be performed at certain locations:

For example, a country could send a message in such a way that it can only be deciphered at the location of its embassy in another country.

In Buhrman et al. (2011), you and your co-authors showed that

if collaborating adversaries are allowed to pre-share an arbitrarily large entangled quantum state, then… position-based cryptography… is impossible… in the quantum setting.

On the positive side, we show that for adversaries that are restricted to not share any entangled quantum states, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in the bounded case of a bounded amount of entanglement.

What is the current state of our knowledge on whether secure position-verification is possible given a bounded amount of entanglement?


Harry Buhrman: Classically such schemes will always be insecure, also if one restricts the running time or other resources of the adversaries. Quantumly the situation is more complicated, although we and others have shown that with an exponential amount of entanglement, also quantum schemes can be broken and are insecure. The quest is thus on for schemes that 1) can be easily implemented by the honest parties 2) require unreasonable amounts of entanglement for adversaries to break the scheme. We have seen some partial progress along these lines. For example a paper by Beigi and Koenig shows that there are schemes where a linear amount of entanglement is necessary to break them. It turns out that the question whether such schemes exists and if they do, prove for certain schemes that they are secure, is a very hard problem that we are currently working on. It turns out that the approach we have taken implies, if successful, results in classical complexity theory, and thus are very hard. On the other hand, it may still be possible that there simply do not exist schemes that are secure in this sense.
Read more »

New paper: “Problems of self-reference in self-improving space-time embedded intelligence”

 |   |  News

Problems of self-referenceWe’ve released a new working paper by Benja Fallenstein and Nate Soares, “Problems of self-reference in self-improving space-time embedded intelligence.”

Abstract:

By considering agents to be a part of their environment, Orseau and Ring’s space-time embedded intelligence is a better fi t for the real world than the traditional agent framework. However, a self-modifying AGI that sees future versions of itself as an ordinary part of the environment may run into problems of self-reference. We show that in one particular model based on formal logic, naive approaches either lead to incorrect reasoning that allows an agent to put off an important task forever (the procrastination paradox), or fail to allow the agent to justify even obviously safe rewrites (the Löbian obstacle). We argue that these problems have relevance beyond our particular formalism, and discuss partial solutions.

This working paper also cites a brief new technical report by Fallenstein, “Procrastination in probabilistic logic.”

Update 05/14/14: This paper has been accepted to AGI-14.

Liveblogging the SV Gives Fundraiser

 |   |  News

SVGives logo lrgToday MIRI is participating in a massive 24-hour fundraiser called SV Gives. Strategy details here, donate here.

This blog post will be updated many times throughout the day.

Total donated to MIRI: $110,245.

Total prizes & matching won for MIRI: $61,330.

 

12:12am Pacific: That’s a wrap, folks! Our thanks once again to SVCF for putting together a thrilling fundraiser with a neck-and-neck race toward the end. Our thanks to everyone who participated in SV Gives. And of course many thanks to our dedicated, well-organized donors who made this such a surprising success for MIRI. And finally, my thanks to the MIRI staff who worked very long hours to run the fundraiser, especially Malo Bourgon, who worked 38 hours straight, and now must go to sleep. :)

12:07am Pacific: For the last hour, MIRI once again won both the $2,000 prize and the $150 prize! Total raised is $110,245 plus $61,330 in prizes and matching funds!

12:04am Pacific: Fundraiser complete! $7.9M raised for local nonprofits. Congrats to SVCF for a rather thrilling fundraiser, and to leaderboard winners Sankara Eye Foundation and Burlingame Community for Education!

11:58pm Pacific: With two minutes to spare, we passed 2000 total donations today!

11:06pm Pacific: Another $2,000! And also another $150 for a random winner, Samuel Brooks!

10:10pm Pacific: And another $2,000!

9:22pm Pacific: MIRI has won $2,000 again!

8:07pm Pacific: MIRI wins $2,000 again!

7:57pm Pacific: Wow, MIRI and Sankara are still neck-and-neck for Total Unique Donors! Right now Sankara has a 5 person lead.

7:09pm Pacific: MIRI won another $2,000 for unique donors last hour, plus $6,980 in matching! But in other news, Sankara Eye Foundation has now overtaken us in the race for the Grand Prize!

6:21pm Pacific: MIRI won $3,030 in matching at 6pm. Thanks, everyone!

6:05pm Pacific: MIRI won another $2,000 for unique donors last hour. Great job everyone! Get ready for more matching funds being avilable at 7pm sharp!

5:54pm Pacific: Hurray! MIRI was one of 50 organizations to win $1,000 from the 5pm matching funds. The 6pm matching funds are coming up, so try to send your donation in the first ~2 seconds after the hour!

5:11pm Pacific: We won the hour again ($2,000), and we also won a 2nd randomly chosen $150 Golden Ticket, courtesy of a donation by Simon Safar!

4:36pm Pacific: Amazingly, MIRI is now 12% of all donations so far during SV Gives day.

4:27pm Pacific: We’ve reached 250 unique donors for the day; thanks so much! As it happens, there’s a MIRI research workshop going on right now, so here is a photo of what you’re all funding (several times over)!

4:06pm Pacific: Another $2,000 for MIRI. Note that we’re coming up on the 5pm matching opportunity, so you should try to donate in the first 5 seconds after 5pm to try to win the match!

3:16pm Pacific: KFOX will be covering SV Gives between 5-7pm today.

3:06pm Pacific: Another $2,000! The strategy is still working!

2:10pm Pacific: MIRI won the hourly $2,000 again. Thanks, everyone!

1:36pm Pacific: Noon matching results have been released. MIRI got $2910 of the $50,000 in matching, which was apparently all taken in less than 4 seconds!

1:11pm Pacific: Another $2,000 prize won. Our deep and sincere thanks to SVCF for organizing SV Gives, and to MIRI’s donors for being so dedicated and well-organized!

12:06pm Pacific: And we won the $2,000 again! Many thanks to our astoundingly well-coordinated donors.

11:07am Pacific: We’ve won the $2,000 Most Unique Donors Each Hour prize again. Who will break MIRI’s winning streak?

10:34am Pacific: We’ve hit the 200 unique donors (for the whole day) mark!

10:08am Pacific: And yet another $2,000 prize for Most Unique Donors Each Hour! I bet the very gracious Sobrato Family Foundation wasn’t expecting to be one of MIRI’s largest donors of the year so far.

9:29am Pacific: On Twitter, SVCF asked us: “What’s your secret? You’ve just got the 9 a.m. $2,000 Golden Ticket prize for a sixth time! Congrats!” We replied: “Our secret is: 70+ person-hours of planning and donor coordination, 10+ energy drinks, and many enthusiastic supporters!” Seriously, I think our participation in SV Gives should be sponsored by Rockstar energy drinks, given how many of them we are consuming over here!

9:07am Pacific: MIRI wins another $2,000. Three cheers for donor coordination!

8:22am Pacific: $1,970 more in matching came in at the beginning of this hour! (The first 14 seconds of this hour, to be precise.)

8:10am Pacific: Another hour, another $2,000 prize for MIRI! Thanks again, everyone.

7:48am Pacific: In the first ~30 seconds after 7am, we captured $2,340 in matching. Thanks, everyone!

7:07am Pacific: MIRI wins the $2,000 prize once again! (For the 6am-7am hour.)

6:16am Pacific: 150 unique donors today so far.

6:08am Pacific: Excellent work, everyone! MIRI won the $2,000 prize for “Most Unique Donors Each Hour” for a third time! (For the 5am-6am hour.)

5:27am Pacific: According to SV Gives’ twitter account, NBC will be covering the SV Gives fundraiser in 3 minutes.

5:18am Pacific: Our thanks to Mick Porter, whose donation won the $150 prize for “random winner” during the 4am hour! We also won the $2,000 “Most Unique Donors Each Hour” again for the 4am-5am hour!

4:41am Pacific: So far we’ve won the $2,000 prize for Most Unique Donors Each Hour once, but not yet twice, so it looks like marginal donors giving as little as $10 each hour can make a difference!

3:50am Pacific: If you’re visiting this page due to MIRI’s SV Gives participation, and would like to know what it looks like to do technical work on ensuring good outcomes from future self-improving AI programs, check out our just-released new working paper, “Problems of self-reference in self-improving space-time embedded intelligence.”

3:04am Pacific: Here’s a live feed of MIRI HQ. Louie, Malo, myself, and Nate are there now.

2:23am Pacific: We won the $2,000 Golden Ticket for the 1am-2am hour! We also won the $2500 “Local Area Code Prize” by way of Patrick LaVictoire making the 408th donation (to any charity) of the day! Our thanks to the Sobrato Family Foundation and the Shackleton Family Foundation, respectively.

Calling all MIRI supporters for unique giving opportunity!

 |   |  News

Update: We are liveblogging the fundraiser here.

Read our strategy below, then give here!

SVGives logo lrg

 

As previously announced, MIRI is participating in a massive 24-hour fundraiser on May 6th, called SV Gives. This is a unique opportunity for all MIRI supporters to increase the impact of their donations. To be successful we’ll need to pre-commit to a strategy and see it through. If you plan to give at least $10 to MIRI sometime this year, during this event would be the best time to do it!

The plan

We need all hands on deck to help us win the following prize as many times as possible:

$2,000 prize for the nonprofit that has the most individual donors in an hour, every hour for 24 hours.

To paraphrase, every hour, there is a $2,000 prize for the organization that has the most individual donors during that hour. That’s a total of $48,000 in prizes, from sources that wouldn’t normally give to MIRI. 

The minimum donation is $10, and an individual donor can give as many times as they want. Therefore we ask our supporters to:

  1. give $10 an hour, during every hour of the fundraiser that they are awake (I’ll be up and donating for all 24 hours!);
  2. for those whose giving budgets won’t cover all those hours, see below for list of which hours you should privilege; and
  3. publicize this effort as widely as possible.

International donors, we especially need your help!

MIRI has a strong community of international supporters, and this gives us a distinct advantage! While North America sleeps, you’ll be awake, ready to target all of the overnight $2,000 hourly prizes.

Hours to target in order of importance

To increase our chances of winning these prizes we want to preferentially target the hours that will see the least donation traffic from donors of other participating organizations. Below are the top 12 hours we’d like to target in order of importance. Remember that all times are in Pacific Time. (Click on an hour to see what time it is in your timezone.)

For the 5 pm hour there is an additional prize I think we can win:

$1,000 golden ticket added to the first 50 organizations receiving gifts in the 5 pm hour.

So if you are giving in the 5 pm hour try and give right at the beginning of the hour.

Bottom line, for every hour you are awake, give $10 an hour.

 Give preferentially to the hours above, if unable to give during all waking hours.

We also have plans to target the $300,000 in matching funds up for grabs during the event. If you would like to contribute $500 or more to this effort, shoot me an email at malo@intelligence.org.

For those who want to follow along and contribute to the last minute planning, as well as receive updates and giving reminders during the event, sign up below.

Kasper Stoy on self-reconfigurable robots

 |   |  Conversations

Kasper Støy portrait Kasper Stoy is a robotics and embodied artificial intelligence researcher holding an associate professor position at the Software and Systems Section of the IT University of Copenhagen. He is interested in the construction and design of complete robot systems, but being a computer scientist he has made most of his personal contributions in distributed control of multi-robot systems and modular robotics. He has published more than sixty papers in international conference proceedings or journals and is the author of the book “Self-Reconfigurable Robots: An Introduction” published by MIT Press. He also co-founded Universal Robots, a company focuses on user-friendly robot arms for industry. He is an active player in the international robot research community and reviews for all major journals and conferences in robotics. He has stayed for extended periods at University of Southern California, Harvard University, University of Tarapacá (Chile), and Seam Reap (Cambodia). He holds a M.Sc. degree in computer science and physics from the University of Aarhus, Denmark (1999) and a Ph.D. degree in computer system engineering from the University of Southern Denmark (2003) where he also worked as assistant professor (2003-2006) and associate professor (2006-2013). He is married and has two kids.

Luke Muehlhauser: In Larsen et al. (2013), you and your co-authors write:

Using a bottom-up, model-free approach when building robots [is] often seen as a less scientific way, compared to a top-down model-based approach, because the results are not easily generalizable to other systems… In this paper we will show how the use of well-known experimental methods from bio-mechanics are used to measure and locate weaknesses in our bottom-up, model-free implementation of a quadruped walker and come up with a better solution.

From looking at the paper I could see how your experimental method allowed you to find a better solution for your walker robot, but I couldn’t understand how you addressed the challenge of generalizing the solution to other systems despite the bottom-up, model-free approach. Could you explain that part?


Kasper Stoy: The problem is that researchers who are doing cutting edge robotics want to explore how materials and their interaction can aid the movement of the robot. For instance, researchers have been working on passive-dynamic walkers for a long time now that exploit the mechanical system to achieve walking without using sensors or actuators. The energy comes from walking downhill and the control is open-looped – the mechanical system itself is self-stabilising. For these systems our current engineering approach is ok, but not great. We can just about model these kinds of walkers so we can get a good guess of the initial parameters to get the system walking, but there is still an extended phase of tinkering before the system actually walks. It is in this tinkering phase that our precise motion capture as used in biomechanics comes into play. Given measured paths of all parts of the robot we can analyse the data and come up with reasonable hypotheses about how to improve the robot. Hence, the tinkering becomes much more systematic even though the underlying physical processes are too complex to be modelled. It may not be apparent, but just modelling the impact of a foot with the ground which takes all types of frictions into account, the deformation of the foot, the spring effect, and so on is largely intractable. Hence, the underlying assumption of our work is that all models of locomotion are fundamentally wrong. They may give a high-level picture of what is going on, but fundamentally they cannot be used to predict what will happen just two steps later. However, if we turn this around and we have gotten our robot to walk and we record the data of how it walks. Although difficult, we can build a model that match this data which is based on the ground truth and where there is no modelling bias on the part of the researcher. We now have a better informed model that can be used to build the next generation of robots. Hence, the model is a generalisation of our specific implementation which you can copy, but you can also replace elements of which you have better implementations. In locomotion research like many other fields the models and physical systems are drifting apart because it is researchers with different skill and interests who work on them. In our work, we are clearly working on physical systems and just provide a hint to how our experimental results can be generalised in a way that is meaningful to modelling oriented researchers. We hope.
Read more »

MIRI’s May 2014 Newsletter

 |   |  Newsletters

Machine Intelligence Research Institute

On May 6th, there is $250,000+ in matching funds and prizes available from sources that normally wouldn’t contribute to MIRI at all. Details here.

Research Updates

News Updates

Other Updates

As always, please don’t hesitate to let us know if you have any questions or comments.

Best,
Luke Muehlhauser
Executive Director

 

New Paper: “The errors, insights, and lessons of famous AI predictions”

 |   |  News

AI predictions paperDuring his time as a MIRI researcher, Kaj Sotala contributed to a paper now published in the Journal of Experimental & Theoretical Artificial Intelligence: “The errors, insights and lessons of famous AI predictions – and what they mean for the future.”

Abstract:

Predicting the development of artificial intelligence (AI) is a difficult project – but a vital one, according to some analysts. AI predictions are already abound: but are they reliable? This paper starts by proposing a decomposition schema for classifying them. Then it constructs a variety of theoretical tools for analysing, judging and improving them. These tools are demonstrated by careful analysis of five famous AI predictions: the initial Dartmouth conference, Dreyfus’s criticism of AI, Searle’s Chinese room paper, Kurzweil’s predictions in the Age of Spiritual Machines, and Omohundro’s ‘AI drives’ paper. These case studies illustrate several important principles, such as the general overconfidence of experts, the superiority of models over expert judgement and the need for greater uncertainty in all types of predictions. The general reliability of expert judgement in AI timeline predictions is shown to be poor, a result that fits in with previous studies of expert competence.

Suresh Jagannathan on higher-order program verification

 |   |  Conversations

Suresh Jagannathan portrait Dr. Suresh Jagannathan joined DARPA in September 2013. His research interests include programming languages, compilers, program verification, and concurrent and distributed systems.

Prior to joining DARPA, Dr. Jagannathan was a professor of computer science at Purdue University. He has also served as visiting faculty at Cambridge University, where he spent a sabbatical year in 2010; and as a senior research scientist at the NEC Research Institute in Princeton, N.J.

Dr. Jagannathan has published more than 125 peer-reviewed conference and journal publications and has co-authored one textbook. He holds three patents. He serves on numerous program and steering committees, and is on the editorial boards of several journals.

Dr. Jagannathan holds Doctor of Philosophy and Master of Science degrees in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology. He earned a Bachelor of Science degree in Computer Science from the State University of New York, Stony Brook.

Luke Muehlhauser: From your perspective, what are some of the most interesting or important developments in higher-order verification in the past decade?


Suresh Jagannathan: I would classify the developments of the past decade into four broad categories:

  1. The development of higher-order recursion schemes (or higher-order model checking). This approach is based on defining a language semantics in terms of a (recursive) tree grammar. We can now ask whether the tree generated by the grammar satisfies a particular safety property. Because recursion schemes are very general and expressive structures, they can be viewed as natural extensions of model checkers based on pushdown automata or finite-state systems. In the past decade, there have been substantial advances that have made higher-order model checking a practical endeavor, accompanied by realistic implementations.
  2. Liquid Types combine facets of classic type inference techniques found in functional language with predicate abstraction techniques used in model checkers to automatically infer dependent type refinements with sufficient precision to prove useful safety properties about higher-order functional programs. Implementations of this approach found in OCaml, SML, and Haskell have demonstrated that it is indeed to possible to verify non-trivial program properties without significant type annotation burden.
  3. There have been substantial advances in the development of new languages built around rich dependent type systems that enable the expression and static verification of rich safety and security specifications and properties of higher-order programs. These include the languages that support mechanized proof assistants like Coq, Agda, or Epigram, languages like F* geared towards secure distributed programming, libraries like Ynot that encapsulate imperative (stateful) features and Hoare-logic pre/post-conditions within a higher-order dependent type framework, and features such as GADTs and type classes found in languages like GHC.
  4. Polyvariant control-flow analyses like CFA2 or higher-order contracts are two techniques that facilitate verification and analysis of dynamic higher-order languages. CFA2 adopts pushdown models used in program analyses for first-order languages to a higher-order setting, enabling precise matching of call/return sequences. Higher-order contracts allow runtime verification and blame assignment of higher-order programs and are fully incorporated into Racket, a multi-paradigm dialect of Lisp/Scheme.

Read more »

As featured in:     Gizmodo   The Guardian   NPR   Popular Science   Technology Review