Search Results

Documents authored by Madry, Aleksander

Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2016.4
Continuous Optimization: The “Right” Language for Graph Algorithms? (Invited Talk)

Authors: Aleksander Madry

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
Traditionally, we view graphs as purely combinatorial objects and tend to design our graph algorithms to be combinatorial as well. In fact, in the context of algorithms, "combinatorial" became a synonym of "fast". Recent work, however, shows that a number of such "inherently combinatorial" graph problems can be solved much faster using methods that are very "non-combinatorial". Specifically, by approaching these problems with tools and notions borrowed from linear algebra and, more broadly, from continuous optimization. A notable examples here are the recent lines of work on the maximum flow problem, the bipartite matching problem, and the shortest path problem in graphs with negative-length arcs. This raises an intriguing question: Is continuous optimization a more suitable and principled optics for fast graph algorithms than the classic combinatorial view? In this talk, I will discuss this question as well as the developments that motivated it.
Cite as

Aleksander Madry. Continuous Optimization: The “Right” Language for Graph Algorithms? (Invited Talk). In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 4:1-4:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{madry:LIPIcs.FSTTCS.2016.4,
  author =	{Madry, Aleksander},
  title =	{{Continuous Optimization: The “Right” Language for Graph Algorithms?}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{4:1--4:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.4},
  URN =		{urn:nbn:de:0030-drops-68890},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.4},
  annote =	{Keywords: maximum flow problem, bipartite matchings, interior-point methods, gradient decent method, Laplacian linear systems}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.134
On the Resiliency of Randomized Routing Against Multiple Edge Failures

Authors: Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Shapira, and Scott Shenker

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s to the destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link.
Cite as

Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Shapira, and Scott Shenker. On the Resiliency of Randomized Routing Against Multiple Edge Failures. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 134:1-134:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chiesa_et_al:LIPIcs.ICALP.2016.134,
  author =	{Chiesa, Marco and Gurtov, Andrei and Madry, Aleksander and Mitrovic, Slobodan and Nikolaevskiy, Ilya and Shapira, Michael and Shenker, Scott},
  title =	{{On the Resiliency of Randomized Routing Against Multiple Edge Failures}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{134:1--134:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.134},
  URN =		{urn:nbn:de:0030-drops-62692},
  doi =		{10.4230/LIPIcs.ICALP.2016.134},
  annote =	{Keywords: Randomized, Routing, Resilience, Connectivity, Arborescenses}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.300
The Semi-stochastic Ski-rental Problem

Authors: Aleksander Madry and Debmalya Panigrahi

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
In this paper, we introduce the semi-stochastic model for dealing with input uncertainty in optimization problems. This model is a hybrid between the overly pessimistic online model and the highly optimistic stochastic (or Bayesian) model. In this model, the algorithm can obtain only limited stochastic information about the future (i.e. about the input distribution)---as the amount of stochastic information we make available to the algorithm grows from no information to full information, we interpolate between the online and stochastic models. The central question in this framework is the trade-off between the performance of an algorithm, and the stochastic information that it can access. As a first step towards understanding this trade-off, we consider the ski-rental problem in the semi-stochastic setting. More precisely, given a desired competitive ratio, we give upper and lower bounds on the amount of stochastic information required by a deterministic algorithm for the ski-rental problem to achieve that competitive ratio.
Cite as

Aleksander Madry and Debmalya Panigrahi. The Semi-stochastic Ski-rental Problem. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 300-311, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{madry_et_al:LIPIcs.FSTTCS.2011.300,
  author =	{Madry, Aleksander and Panigrahi, Debmalya},
  title =	{{The Semi-stochastic Ski-rental Problem}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{300--311},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.300},
  URN =		{urn:nbn:de:0030-drops-33305},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.300},
  annote =	{Keywords: online optimization, stochastic algorithm}
}
Document
DOI: 10.4230/DagSemProc.06111.21
Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

Authors: Andreas Jakoby, Maciej Liskiewicz, and Aleksander Madry

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We define $(varepsilon,delta)$-secure quantum computations between two parties that can play dishonestly to maximise advantage $delta$, however keeping small the probability $varepsilon$ that the computation fails in evaluating correct value. We present a simple quantum protocol for computing one-out-of-two oblivious transfer that is $(O(sqrt{varepsilon}),varepsilon)$-secure. Using the protocol as a black box we construct a scheme for cheat sensitive quantum bit commitment which guarantee that a mistrustful party has a nonzero probability of detecting a cheating.
Cite as

Andreas Jakoby, Maciej Liskiewicz, and Aleksander Madry. Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{jakoby_et_al:DagSemProc.06111.21,
  author =	{Jakoby, Andreas and Liskiewicz, Maciej and Madry, Aleksander},
  title =	{{Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.21},
  URN =		{urn:nbn:de:0030-drops-6223},
  doi =		{10.4230/DagSemProc.06111.21},
  annote =	{Keywords: Two-Party Computations, Quantum Protocols, Bit Commitment, Oblivious Transfer.}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact