Powered by
49th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2017),
June 19–23, 2017,
Montreal, Canada
Invited Talks
Recent Trends in Decentralized Cryptocurrencies (Invited Talk)
Aviv Zohar
(Hebrew University of Jerusalem, Israel)
Following Bitcoin's introduction, decentralized cryptocurrencies began to emerge as a new application domain for computer science. Bitcoin's protocol has been researched and improved upon along many fronts: from its underlying incentives, through to its cryptographic primitives and its security. Many research questions and challenges still remain as cryptocurrencies and other financial systems that rely on similar principles gain wider adoption.
@InProceedings{STOC17p1,
author = {Aviv Zohar},
title = {Recent Trends in Decentralized Cryptocurrencies (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1--1},
doi = {},
year = {2017},
}
Why Prices Need Algorithms (Invited Talk)
Tim Roughgarden and
Inbal Talgam-Cohen
(Stanford University, USA; Hebrew University of Jerusalem, Israel)
Computational complexity has already had plenty to say about the computation of economic equilibria. However, understanding when equilibria are guaranteed to exist is a central theme in economic theory, seemingly unrelated to computation. In this talk we survey our main results presented at EC’15, which show that the existence of equilibria in markets is inextricably connected to the computational complexity of related optimization problems, such as revenue or welfare maximization. We demonstrate how this relationship implies, under suitable complexity assumptions, a host of impossibility results. We also suggest a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept: such extensions seem to require the invention of novel polynomial-time algorithms for welfare maximization.
@InProceedings{STOC17p2,
author = {Tim Roughgarden and Inbal Talgam-Cohen},
title = {Why Prices Need Algorithms (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {2--2},
doi = {},
year = {2017},
}
Optimizing Tree Pattern Queries: Why Cutting Is Not Enough (Invited Talk)
Wim Martens
(University of Bayreuth, Germany)
Tree pattern queries are a natural language for querying graph- and tree-structured data. A central question for understanding their optimization problem was whether they can be minimized by cutting away redundant parts. This question has been studied since the early 2000's and was recently resolved.
@InProceedings{STOC17p3,
author = {Wim Martens},
title = {Optimizing Tree Pattern Queries: Why Cutting Is Not Enough (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {3--3},
doi = {},
year = {2017},
}
Answering FAQs in CSPs, Probabilistic Graphical Models, Databases, Logic and Matrix Operations (Invited Talk)
Atri Rudra
(SUNY Buffalo, USA)
In this talk we will discuss a general framework to solve certain sums of products of functions over semi-rings. This captures many well-known problems in disparate areas such as CSPs, Probabilistic Graphical Models, Databases, Logic and Matrix Operations. This talk is based on joint work titled FAQ: Questions Asked Frequently with Mahmoud Abo Khamis and Hung Q. Ngo, which appeared in PODS 2016.
@InProceedings{STOC17p4,
author = {Atri Rudra},
title = {Answering FAQs in CSPs, Probabilistic Graphical Models, Databases, Logic and Matrix Operations (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {4--4},
doi = {},
year = {2017},
}
Fast Convergence of Learning in Games (Invited Talk)
Vasilis Syrgkanis
(Microsoft Research, USA)
A plethora of recent work has analyzed properties of outcomes in games when each player employs a no-regret learning algorithm. Many algorithms achieve regret against the best fixed action in hindisght that decays at a rate of O(1/√T), when the game is played for T iterations. The latter rate is optimal in adversarial settings. However, in a game a player’s opponents are minimizing their own regret, rather than maximizing the player’s regret. (Daskalakis et al. 2014) and (Rakhlin and Sridharan 2013) showed that in two player zero-sum games O(1/T) rates are achievable. In (Syrgkanis et al. 2015), we show that O(1/T3/4) rates are achievable in general multi-player games and also analyze convergence of the dynamics to approximately optimal social welfare, where we show a convergence rate of O(1/T). The latter result was subsequently generalized to a broader class of learning algorithms by (Foster et al. 2016). This is based on joint work with Alekh Agarwal, Haipeng Luo and Robert E. Schapire.
@InProceedings{STOC17p5,
author = {Vasilis Syrgkanis},
title = {Fast Convergence of Learning in Games (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {5--5},
doi = {},
year = {2017},
}
Examining Classical Graph-Theory Problems from the Viewpoint of Formal-Verification Methods (Invited Talk)
Orna Kupferman
(Hebrew University of Jerusalem, Israel)
The talk surveys a series of works that lift the rich semantics and structure of graphs, and the experience of the formal-verification community in reasoning about them, to classical graph-theoretical problems.
@InProceedings{STOC17p6,
author = {Orna Kupferman},
title = {Examining Classical Graph-Theory Problems from the Viewpoint of Formal-Verification Methods (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {6--6},
doi = {},
year = {2017},
}
The Next 700 Network Programming Languages (Invited Talk)
Nate Foster
(Cornell University, USA)
Specification and verification of computer networks has become a reality in recent years, with the emergence of domain-specific programming languages and automated reasoning tools. But the design of these frameworks has been largely ad hoc, driven more by the needs of applications and the capabilities of hardware than by any foundational principles. This talk will present NetKAT, a language for programming networks based on a well-studied mathematical foundation: regular languages and finite automata. The talk will describe the design of the language, discuss its semantic underpinnings, and present highlights from ongoing work extending the language with stateful and probabilistic features.
@InProceedings{STOC17p7,
author = {Nate Foster},
title = {The Next 700 Network Programming Languages (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {7--7},
doi = {},
year = {2017},
}
Practical Post-quantum Key Agreement from Generic Lattices (Invited Talk)
Valeria Nikolaenko
(Stanford University, USA)
Lattice-based cryptography offers some of the most attractive primitives believed to be resistant to quantum computers. This work introduces "Frodo" - a concrete instantiation of a key agreement mechanism based on hard problems in generic lattices.
@InProceedings{STOC17p8,
author = {Valeria Nikolaenko},
title = {Practical Post-quantum Key Agreement from Generic Lattices (Invited Talk)},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {8--8},
doi = {},
year = {2017},
}
proc time: 1.32