28 Search Results for "Miltersen, Peter Bro"


Document
On the Complexity of Reachability in Parametric Markov Decision Processes

Authors: Tobias Winkler, Sebastian Junges, Guillermo A. Pérez, and Joost-Pieter Katoen

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)


Abstract
This paper studies parametric Markov decision processes (pMDPs), an extension to Markov decision processes (MDPs) where transitions probabilities are described by polynomials over a finite set of parameters. Fixing values for all parameters yields MDPs. In particular, this paper studies the complexity of finding values for these parameters such that the induced MDP satisfies some reachability constraints. We discuss different variants depending on the comparison operator in the constraints and the domain of the parameter values. We improve all known lower bounds for this problem, and notably provide ETR-completeness results for distinct variants of this problem. Furthermore, we provide insights in the functions describing the induced reachability probabilities, and how pMDPs generalise concurrent stochastic reachability games.

Cite as

Tobias Winkler, Sebastian Junges, Guillermo A. Pérez, and Joost-Pieter Katoen. On the Complexity of Reachability in Parametric Markov Decision Processes. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{winkler_et_al:LIPIcs.CONCUR.2019.14,
  author =	{Winkler, Tobias and Junges, Sebastian and P\'{e}rez, Guillermo A. and Katoen, Joost-Pieter},
  title =	{{On the Complexity of Reachability in Parametric Markov Decision Processes}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.14},
  URN =		{urn:nbn:de:0030-drops-109162},
  doi =		{10.4230/LIPIcs.CONCUR.2019.14},
  annote =	{Keywords: Parametric Markov decision processes, Formal verification, ETR, Complexity}
}
Document
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

Authors: Surender Baswana, Shiv Gupta, and Ayush Tulsyan

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time, and still achieves better time complexity. This algorithm also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.

Cite as

Surender Baswana, Shiv Gupta, and Ayush Tulsyan. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.MFCS.2019.65,
  author =	{Baswana, Surender and Gupta, Shiv and Tulsyan, Ayush},
  title =	{{Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.65},
  URN =		{urn:nbn:de:0030-drops-110096},
  doi =		{10.4230/LIPIcs.MFCS.2019.65},
  annote =	{Keywords: Depth first search, DFS, Dynamic graph algorithms, Fault tolerant}
}
Document
Timed Basic Parallel Processes

Authors: Lorenzo Clemente, Piotr Hofman, and Patrick Totzke

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)


Abstract
Timed basic parallel processes (TBPP) extend communication-free Petri nets (aka. BPP or commutative context-free grammars) by a global notion of time. TBPP can be seen as an extension of timed automata (TA) with context-free branching rules, and as such may be used to model networks of independent timed automata with process creation. We show that the coverability and reachability problems (with unary encoded target multiplicities) are PSPACE-complete and EXPTIME-complete, respectively. For the special case of 1-clock TBPP, both are NP-complete and hence not more complex than for untimed BPP. This contrasts with known super-Ackermannian-completeness and undecidability results for general timed Petri nets. As a result of independent interest, and basis for our NP upper bounds, we show that the reachability relation of 1-clock TA can be expressed by a formula of polynomial size in the existential fragment of linear arithmetic, which improves on recent results from the literature.

Cite as

Lorenzo Clemente, Piotr Hofman, and Patrick Totzke. Timed Basic Parallel Processes. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{clemente_et_al:LIPIcs.CONCUR.2019.15,
  author =	{Clemente, Lorenzo and Hofman, Piotr and Totzke, Patrick},
  title =	{{Timed Basic Parallel Processes}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.15},
  URN =		{urn:nbn:de:0030-drops-109171},
  doi =		{10.4230/LIPIcs.CONCUR.2019.15},
  annote =	{Keywords: Timed Automata, Petri Nets}
}
Document
Walrasian Pricing in Multi-Unit Auctions

Authors: Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)


Abstract
Multi-unit auctions are a paradigmatic model, where a seller brings multiple units of a good, while several buyers bring monetary endowments. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. In this paper we design an optimal envy-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources, and in particular, is incompatible with (Pareto) efficiency.

Cite as

Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng. Walrasian Pricing in Multi-Unit Auctions. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 80:1-80:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{branzei_et_al:LIPIcs.MFCS.2017.80,
  author =	{Br\^{a}nzei, Simina and Filos-Ratsikas, Aris and Miltersen, Peter Bro and Zeng, Yulong},
  title =	{{Walrasian Pricing in Multi-Unit Auctions}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.80},
  URN =		{urn:nbn:de:0030-drops-81197},
  doi =		{10.4230/LIPIcs.MFCS.2017.80},
  annote =	{Keywords: mechanism design, multi-unit auctions, Walrasian pricing, market share}
}
Document
Simple Priced Timed Games are not That Simple

Authors: Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, and Benjamin Monmege

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modeling the costs of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary (positive and negative) weights and show that, for an important subclass of theirs (the so-called simple priced timed games), one can compute, in exponential time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called reset-acyclic priced timed games (with arbitrary weights and one-clock).

Cite as

Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, and Benjamin Monmege. Simple Priced Timed Games are not That Simple. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 278-292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{brihaye_et_al:LIPIcs.FSTTCS.2015.278,
  author =	{Brihaye, Thomas and Geeraerts, Gilles and Haddad, Axel and Lefaucheux, Engel and Monmege, Benjamin},
  title =	{{Simple Priced Timed Games are not That Simple}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{278--292},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.278},
  URN =		{urn:nbn:de:0030-drops-56235},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.278},
  annote =	{Keywords: Priced timed games, real-time systems, game theory}
}
Document
On the Value Problem in Weighted Timed Games

Authors: Patricia Bouyer, Samy Jaziri, and Nicolas Markey

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)


Abstract
A weighted timed game is a timed game with extra quantitative information representing e.g. energy consumption. Optimizing the weight for reaching a target is a natural question, which has already been investigated for ten years. Existence of optimal strategies is known to be undecidable in general, and only very restricted classes of games have been identified for which optimal weight and almost-optimal strategies can be computed. In this paper, we show that the value problem is undecidable in weighted timed games. We then introduce a large subclass of weighted timed games (for which the undecidability proof above applies), and provide an algorithm to compute arbitrary approximations of the value in such games. To the best of our knowledge, this is the first approximation scheme for an undecidable class of weighted timed games.

Cite as

Patricia Bouyer, Samy Jaziri, and Nicolas Markey. On the Value Problem in Weighted Timed Games. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 311-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bouyer_et_al:LIPIcs.CONCUR.2015.311,
  author =	{Bouyer, Patricia and Jaziri, Samy and Markey, Nicolas},
  title =	{{On the Value Problem in Weighted Timed Games}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{311--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.311},
  URN =		{urn:nbn:de:0030-drops-53863},
  doi =		{10.4230/LIPIcs.CONCUR.2015.311},
  annote =	{Keywords: Timed games, undecidability, approximation}
}
Document
Restricted Isometry Property for General p-Norms

Authors: Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya Razenshteyn

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)


Abstract
The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an m x n matrix satisfies RIP of order k for the L_p norm, if |Ax|_p is approximately |x|_p for every x with at most k non-zero coordinates. For every 1 <= p < infty we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this work, only the cases p = 1, 1 + 1/log(k), and 2 were studied. Interestingly, our results show that the case p=2 is a "singularity" point: the optimal number of rows m is Theta(k^p) for all p in [1, infty)-{2}, as opposed to Theta(k) for k=2. We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss implications of our results for the Stable Sparse Recovery problem.

Cite as

Zeyuan Allen-Zhu, Rati Gelashvili, and Ilya Razenshteyn. Restricted Isometry Property for General p-Norms. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 451-460, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{allenzhu_et_al:LIPIcs.SOCG.2015.451,
  author =	{Allen-Zhu, Zeyuan and Gelashvili, Rati and Razenshteyn, Ilya},
  title =	{{Restricted Isometry Property for General p-Norms}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{451--460},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.451},
  URN =		{urn:nbn:de:0030-drops-51273},
  doi =		{10.4230/LIPIcs.SOCG.2015.451},
  annote =	{Keywords: compressive sensing, dimension reduction, linear algebra, high-dimensional geometry}
}
Document
How to Compress Asymmetric Communication

Authors: Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If I^A denotes the number of bits of information revealed by the first party, I^B denotes the information revealed by the second party, and C is the number of bits of communication in the protocol, we show that i) one can simulate the protocol using order I^A + (C^3 * I^B)^(1/4) * log(C) + (C * I^B)^(1/2) * log(C) bits of communication, ii) one can simulate the protocol using order I^A * 2^(O(I^B)) bits of communication The first result gives the best known bound on the complexity of a simulation when I^A >> I^B,C^(3/4). The second gives the best known bound when I^B << log C. In addition we show that if a function is computed by a protocol with asymmetric information complexity, then the inputs must have a large, nearly monochromatic rectangle of the right dimensions, a fact that is useful for proving lower bounds on lopsided communication problems.

Cite as

Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao. How to Compress Asymmetric Communication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 102-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{natarajanramamoorthy_et_al:LIPIcs.CCC.2015.102,
  author =	{Natarajan Ramamoorthy, Sivaramakrishnan and Rao, Anup},
  title =	{{How to Compress Asymmetric Communication}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{102--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.102},
  URN =		{urn:nbn:de:0030-drops-50679},
  doi =		{10.4230/LIPIcs.CCC.2015.102},
  annote =	{Keywords: Communication Complexity, Interactive Compression, Information Complexity}
}
Document
On The I/O Complexity of Dynamic Distinct Counting

Authors: Xiaocheng Hu, Yufei Tao, Yi Yang, Shengyu Zhang, and Shuigeng Zhou

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)


Abstract
In dynamic distinct counting, we want to maintain a multi-set S of integers under insertions to answer efficiently the query: how many distinct elements are there in S? In external memory, the problem admits two standard solutions. The first one maintains $S$ in a hash structure, so that the distinct count can be incrementally updated after each insertion using O(1) expected I/Os. A query is answered for free. The second one stores S in a linked list, and thus supports an insertion in O(1/B) amortized I/Os. A query can be answered in O(N/B log_{M/B} (N/B)) I/Os by sorting, where N=|S|, B is the block size, and M is the memory size. In this paper, we show that the above two naive solutions are already optimal within a polylog factor. Specifically, for any Las Vegas structure using N^{O(1)} blocks, if its expected amortized insertion cost is o(1/log B}), then it must incur Omega(N/(B log B)) expected I/Os answering a query in the worst case, under the (realistic) condition that N is a polynomial of B. This means that the problem is repugnant to update buffering: the query cost jumps from 0 dramatically to almost linearity as soon as the insertion cost drops slightly below Omega(1).

Cite as

Xiaocheng Hu, Yufei Tao, Yi Yang, Shengyu Zhang, and Shuigeng Zhou. On The I/O Complexity of Dynamic Distinct Counting. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 265-276, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.ICDT.2015.265,
  author =	{Hu, Xiaocheng and Tao, Yufei and Yang, Yi and Zhang, Shengyu and Zhou, Shuigeng},
  title =	{{On The I/O Complexity of Dynamic Distinct Counting}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{265--276},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.265},
  URN =		{urn:nbn:de:0030-drops-49895},
  doi =		{10.4230/LIPIcs.ICDT.2015.265},
  annote =	{Keywords: distinct counting, lower bound, external memory}
}
Document
On the Complexity of Computing Maximum Entropy for Markovian Models

Authors: Taolue Chen and Tingting Han

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)


Abstract
We investigate the complexity of computing entropy of various Markovian models including Markov Chains (MCs), Interval Markov Chains (IMCs) and Markov Decision Processes (MDPs). We consider both entropy and entropy rate for general MCs, and study two algorithmic questions, i.e., entropy approximation problem and entropy threshold problem. The former asks for an approximation of the entropy/entropy rate within a given precision, whereas the latter aims to decide whether they exceed a given threshold. We give polynomial-time algorithms for the approximation problem, and show the threshold problem is in P^CH_3 (hence in PSPACE) and in P assuming some number-theoretic conjectures. Furthermore, we study both questions for IMCs and MDPs where we aim to maximise the entropy/entropy rate among an infinite family of MCs associated with the given model. We give various conditional decidability results for the threshold problem, and show the approximation problem is solvable in polynomial-time via convex programming.

Cite as

Taolue Chen and Tingting Han. On the Complexity of Computing Maximum Entropy for Markovian Models. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 571-583, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.FSTTCS.2014.571,
  author =	{Chen, Taolue and Han, Tingting},
  title =	{{On the Complexity of Computing Maximum Entropy for Markovian Models}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{571--583},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.571},
  URN =		{urn:nbn:de:0030-drops-48725},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.571},
  annote =	{Keywords: Markovian Models, Entropy, Complexity, Probabilistic Verification}
}
Document
Certifying Equality With Limited Interaction

Authors: Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
The EQUALITY problem is usually one’s first encounter with communication complexity and is one of the most fundamental problems in the field. Although its deterministic and randomized communication complexity were settled decades ago, we find several new things to say about the problem by focusing on three subtle aspects. The first is to consider the expected communication cost (at a worst-case input) for a protocol that uses limited interaction—i.e., a bounded number of rounds of communication—and whose error probability is zero or close to it. The second is to treat the false negative error rate separately from the false positive error rate. The third is to consider the information cost of such protocols. We obtain asymptotically optimal rounds-versus-cost tradeoffs for EQUALITY: both expected communication cost and information cost scale as Theta(log log ... log n), with r-1 logs, where r is the number of rounds. These bounds hold even when the false negative rate approaches 1. For the case of zero-error communication cost, we obtain essentially matching bounds, up to a tiny additive constant. We also provide some applications.

Cite as

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Certifying Equality With Limited Interaction. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 545-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{brody_et_al:LIPIcs.APPROX-RANDOM.2014.545,
  author =	{Brody, Joshua and Chakrabarti, Amit and Kondapally, Ranganath and Woodruff, David P. and Yaroslavtsev, Grigory},
  title =	{{Certifying Equality With Limited Interaction}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{545--581},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.545},
  URN =		{urn:nbn:de:0030-drops-47229},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.545},
  annote =	{Keywords: equality, communication complexity, information complexity}
}
Document
Deterministic Coupon Collection and Better Strong Dispersers

Authors: Raghu Meka, Omer Reingold, and Yuan Zhou

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
Hashing is one of the main techniques in data processing and algorithm design for very large data sets. While random hash functions satisfy most desirable properties, it is often too expensive to store a fully random hash function. Motivated by this, much attention has been given to designing small families of hash functions suitable for various applications. In this work, we study the question of designing space-efficient hash families H = {h:[U] -> [N]} with the natural property of 'covering': H is said to be covering if any set of Omega(N log N) distinct items from the universe (the "coupon-collector limit") are hashed to cover all N bins by most hash functions in H. We give an explicit covering family H of size poly(N) (which is optimal), so that hash functions in H can be specified efficiently by O(log N) bits. We build covering hash functions by drawing a connection to "dispersers", which are quite well-studied and have a variety of applications themselves. We in fact need strong dispersers and we give new constructions of strong dispersers which may be of independent interest. Specifically, we construct strong dispersers with optimal entropy loss in the high min-entropy, but very small error (poly(n)/2^n for n bit sources) regimes. We also provide a strong disperser construction with constant error but for any min-entropy. Our constructions achieve these by using part of the source to replace seed from previous non-strong constructions in surprising ways. In doing so, we take two of the few constructions of dispersers with parameters better than known extractors and make them strong.

Cite as

Raghu Meka, Omer Reingold, and Yuan Zhou. Deterministic Coupon Collection and Better Strong Dispersers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 872-884, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{meka_et_al:LIPIcs.APPROX-RANDOM.2014.872,
  author =	{Meka, Raghu and Reingold, Omer and Zhou, Yuan},
  title =	{{Deterministic Coupon Collection and Better Strong Dispersers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{872--884},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.872},
  URN =		{urn:nbn:de:0030-drops-47440},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.872},
  annote =	{Keywords: Coupon collection; dispersers, strong dispersers, hashing, pseudorandomness}
}
Document
Invited Talk
Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk)

Authors: Peter Bro Miltersen

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)


Abstract
We survey recent applications of real algebraic and semi-algebraic geometry in (computational) game theory.

Cite as

Peter Bro Miltersen. Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 11-12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{miltersen:LIPIcs.STACS.2014.11,
  author =	{Miltersen, Peter Bro},
  title =	{{Semi-algebraic geometry in computational game theory - a consumer's perspective}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{11--12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.11},
  URN =		{urn:nbn:de:0030-drops-44994},
  doi =		{10.4230/LIPIcs.STACS.2014.11},
  annote =	{Keywords: Real Algebraic Geometry, Computational Game Theory}
}
Document
10171 Abstracts Collection – Equilibrium Computation

Authors: Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)


Abstract
From April 25 to April 30, 2010, the Dagstuhl Seminar 10171 ``Equilibrium Computation'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani. 10171 Abstracts Collection – Equilibrium Computation. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{elkind_et_al:DagSemProc.10171.1,
  author =	{Elkind, Edith and Megiddo, Nimrod and Miltersen, Peter Bro and von Stengel, Bernhard and Vazirani, Vijay V.},
  title =	{{10171 Abstracts Collection – Equilibrium Computation}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.1},
  URN =		{urn:nbn:de:0030-drops-26738},
  doi =		{10.4230/DagSemProc.10171.1},
  annote =	{Keywords: Equilibrium computation, algorithmic game theory}
}
Document
Improved Algorithms for Computing Fisher's Market Clearing Prices

Authors: James B. Orlin

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)


Abstract
We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set $B$ of buyers and a set $G$ of divisible goods. Each buyer $i$ starts with an initial integral allocation $e_i$ of money. The integral utility for buyer $i$ of good $j$ is $U_{ij}$. We first develop a weakly polynomial time algorithm that runs in $O(n^4 log U_{max} + n^3 e_{max})$ time, where $n = |B| + |G|$. We further modify the algorithm so that it runs in $O(n^4 log n)$ time. These algorithms improve upon the previous best running time of $O(n^8 log U_{max} + n^7 log e_{max})$, due to Devanur et al.

Cite as

James B. Orlin. Improved Algorithms for Computing Fisher's Market Clearing Prices. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{orlin:DagSemProc.10171.2,
  author =	{Orlin, James B.},
  title =	{{Improved Algorithms for Computing Fisher's Market Clearing Prices}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2},
  URN =		{urn:nbn:de:0030-drops-26720},
  doi =		{10.4230/DagSemProc.10171.2},
  annote =	{Keywords: Market equilibrium, Fisher, strongly polynomial}
}
  • Refine by Author
  • 7 Miltersen, Peter Bro
  • 2 Herings, P. Jean-Jacques
  • 2 Reischuk, Rüdiger
  • 2 Schnitger, Georg
  • 2 van Melkebeek, Dieter
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Logic and verification
  • 1 Theory of computation → Markov decision processes
  • 1 Theory of computation → Probabilistic computation
  • 1 Theory of computation → Timed and hybrid models

  • Refine by Keyword
  • 3 Equilibrium computation
  • 3 communication complexity
  • 3 pseudorandomness
  • 2 Complexity
  • 2 Computational complexity
  • Show More...

  • Refine by Type
  • 28 document

  • Refine by Publication Year
  • 10 2008
  • 5 2015
  • 4 2014
  • 3 2010
  • 3 2019
  • Show More...

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