6 Search Results for "Br�zdil, Tom�s"


Document
On Property Testing of the Binary Rank

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
Let M be an n × m (0,1)-matrix. We define the s-binary rank, denoted as br_s(M), of M as the minimum integer d such that there exist d monochromatic rectangles covering all the 1-entries in the matrix, with each 1-entry being covered by at most s rectangles. When s = 1, this corresponds to the binary rank, denoted as br(M), which is well-known in the literature and has many applications. Let R(M) and C(M) denote the sets of rows and columns of M, respectively. Using the result of Sgall [Jiří Sgall, 1999], we establish that if M has an s-binary rank at most d, then |R(M)| ⋅ |C(M)| ≤ binom(d, ≤ s)2^d, where binom(d, ≤ s) = ∑_{i=0}^s binom(d,i). This bound is tight, meaning that there exists a matrix M' with an s-binary rank of d, for which |R(M')| ⋅ |C(M')| = binom(d, ≤ s)2^d. Using this result, we present novel one-sided adaptive and non-adaptive testers for (0,1)-matrices with an s-binary rank at most d (and exactly d). These testers require Õ(binom(d, ≤ s)2^d/ε) and Õ(binom(d, ≤ s)2^d/ε²) queries, respectively. For a fixed s, this improves upon the query complexity of the tester proposed by Parnas et al. in [Michal Parnas et al., 2021] by a factor of Θ(2^d).

Cite as

Nader H. Bshouty. On Property Testing of the Binary Rank. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.MFCS.2023.27,
  author =	{Bshouty, Nader H.},
  title =	{{On Property Testing of the Binary Rank}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.27},
  URN =		{urn:nbn:de:0030-drops-185616},
  doi =		{10.4230/LIPIcs.MFCS.2023.27},
  annote =	{Keywords: Property testing, binary rank, Boolean rank}
}
Document
Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities

Authors: Tom Demeulemeester and Jannik Peters

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
We study relationships between different relaxed notions of core stability in hedonic games. In particular, we study (i) q-size core stable outcomes in which no deviating coalition of size at most q exists and (ii) k-improvement core stable outcomes in which no coalition can improve by a factor of more than k. For a large class of hedonic games, including fractional and additively separable hedonic games, we derive upper bounds on the maximum factor by which a coalition of a certain size can improve in a q-size core stable outcome. We further provide asymptotically tight lower bounds for a large class of hedonic games. Finally, our bounds allow us to confirm two conjectures by Fanelli et al. [Angelo Fanelli et al., 2021][IJCAI'21] for symmetric fractional hedonic games (S-FHGs): (i) every q-size core stable outcome in an S-FHG is also q/(q-1)-improvement core stable and (ii) the price of anarchy of q-size stability in S-FHGs is precisely 2q/q-1.

Cite as

Tom Demeulemeester and Jannik Peters. Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{demeulemeester_et_al:LIPIcs.MFCS.2023.41,
  author =	{Demeulemeester, Tom and Peters, Jannik},
  title =	{{Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.41},
  URN =		{urn:nbn:de:0030-drops-185759},
  doi =		{10.4230/LIPIcs.MFCS.2023.41},
  annote =	{Keywords: hedonic games, core stability, algorithmic game theory, computational social choice}
}
Document
Short Paper
Towards Verifying the Bitcoin-S Library (Short Paper)

Authors: Ramon Boss, Kai Brünnler, and Anna Doukmak

Published in: OASIcs, Volume 84, 2nd Workshop on Formal Methods for Blockchains (FMBC 2020)


Abstract
We try to verify properties of the Bitcoin-S library, a Scala implementation of parts of the Bitcoin protocol. We use the Stainless verifier which supports programs in a fragment of Scala called Pure Scala. Since Bitcoin-S is not written in this fragment, we extract the relevant code from it and rewrite it until we arrive at code that we successfully verify. In that process we find and fix two bugs in Bitcoin-S.

Cite as

Ramon Boss, Kai Brünnler, and Anna Doukmak. Towards Verifying the Bitcoin-S Library (Short Paper). In 2nd Workshop on Formal Methods for Blockchains (FMBC 2020). Open Access Series in Informatics (OASIcs), Volume 84, pp. 8:1-8:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{boss_et_al:OASIcs.FMBC.2020.8,
  author =	{Boss, Ramon and Br\"{u}nnler, Kai and Doukmak, Anna},
  title =	{{Towards Verifying the Bitcoin-S Library}},
  booktitle =	{2nd Workshop on Formal Methods for Blockchains (FMBC 2020)},
  pages =	{8:1--8:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-169-6},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{84},
  editor =	{Bernardo, Bruno and Marmsoler, Diego},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.FMBC.2020.8},
  URN =		{urn:nbn:de:0030-drops-134212},
  doi =		{10.4230/OASIcs.FMBC.2020.8},
  annote =	{Keywords: Bitcoin, Scala, Bitcoin-S, Stainless}
}
Document
Solvency Markov Decision Processes with Interest

Authors: Tomás Brázdil, Taolue Chen, Vojtech Forejt, Petr Novotný, and Aistis Simaitis

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


Abstract
Solvency games, introduced by Berger et al., provide an abstract framework for modelling decisions of a risk-averse investor, whose goal is to avoid ever going broke. We study a new variant of this model, where, in addition to stochastic environment and fixed increments and decrements to the investor's wealth, we introduce interest, which is earned or paid on the current level of savings or debt, respectively. We study problems related to the minimum initial wealth sufficient to avoid bankruptcy (i.e. steady decrease of the wealth) with probability at least p. We present an exponential time algorithm which approximates this minimum initial wealth, and show that a polynomial time approximation is not possible unless P=NP. For the qualitative case, i.e. p=1, we show that the problem whether a given number is larger than or equal to the minimum initial wealth belongs to NP \cap coNP, and show that a polynomial time algorithm would yield a polynomial time algorithm for mean-payoff games, existence of which is a longstanding open problem. We also identify some classes of solvency MDPs for which this problem is in P. In all above cases the algorithms also give corresponding bankruptcy avoiding strategies.

Cite as

Tomás Brázdil, Taolue Chen, Vojtech Forejt, Petr Novotný, and Aistis Simaitis. Solvency Markov Decision Processes with Interest. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 487-499, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2013.487,
  author =	{Br\'{a}zdil, Tom\'{a}s and Chen, Taolue and Forejt, Vojtech and Novotn\'{y}, Petr and Simaitis, Aistis},
  title =	{{Solvency Markov Decision Processes with Interest}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{487--499},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.487},
  URN =		{urn:nbn:de:0030-drops-43959},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.487},
  annote =	{Keywords: Markov decision processes, algorithms, complexity, market models.}
}
Document
Stabilization of Branching Queueing Networks

Authors: Tomáš Brázdil and Stefan Kiefer

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)


Abstract
Queueing networks are gaining attraction for the performance analysis of parallel computer systems. A Jackson network is a set of interconnected servers, where the completion of a job at server i may result in the creation of a new job for server j. We propose to extend Jackson networks by "branching" and by "control" features. Both extensions are new and substantially expand the modelling power of Jackson networks. On the other hand, the extensions raise computational questions, particularly concerning the stability of the networks, i.e, the ergodicity of the underlying Markov chain. We show for our extended model that it is decidable in polynomial time if there exists a controller that achieves stability. Moreover, if such a controller exists, one can efficiently compute a static randomized controller which stabilizes the network in a very strong sense; in particular, all moments of the queue sizes are finite.

Cite as

Tomáš Brázdil and Stefan Kiefer. Stabilization of Branching Queueing Networks. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 507-518, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{brazdil_et_al:LIPIcs.STACS.2012.507,
  author =	{Br\'{a}zdil, Tom\'{a}\v{s} and Kiefer, Stefan},
  title =	{{Stabilization of Branching Queueing Networks}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{507--518},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.507},
  URN =		{urn:nbn:de:0030-drops-34133},
  doi =		{10.4230/LIPIcs.STACS.2012.507},
  annote =	{Keywords: continuous-time Markov decision processes, infinite-state systems, performance analysis}
}
Document
One-Counter Stochastic Games

Authors: Tomás Brázdil, Václav Brozek, and Kousha Etessami

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


Abstract
We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stochastic games played on the transition graph of classic one-counter automata. We study primarily the termination objective, where the goal of one player is to maximize the probability of reaching counter value 0, while the other player wishes to avoid this. Partly motivated by the goal of understanding termination objectives, we also study certain ``limit'' and ``long run average'' reward objectives that are closely related to some well-studied objectives for stochastic games with rewards. Examples of problems we address include: does player 1 have a strategy to ensure that the counter eventually hits 0, i.e., terminates, almost surely, regardless of what player 2 does? Or that the $liminf$ (or $limsup$) counter value equals $infty$ with a desired probability? Or that the long run average reward is $>0$ with desired probability? We show that the qualitative termination problem for OC-SSGs is in $NP$ intersect $coNP$, and is in P-time for 1-player OC-SSGs, or equivalently for one-counter Markov Decision Processes (OC-MDPs). Moreover, we show that quantitative limit problems for OC-SSGs are in $NP$ intersect $coNP$, and are in P-time for 1-player OC-MDPs. Both qualitative limit problems and qualitative termination problems for OC-SSGs are already at least as hard as Condon's quantitative decision problem for finite-state SSGs.

Cite as

Tomás Brázdil, Václav Brozek, and Kousha Etessami. One-Counter Stochastic Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 108-119, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2010.108,
  author =	{Br\'{a}zdil, Tom\'{a}s and Brozek, V\'{a}clav and Etessami, Kousha},
  title =	{{One-Counter Stochastic Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{108--119},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.108},
  URN =		{urn:nbn:de:0030-drops-28571},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.108},
  annote =	{Keywords: one-counter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward}
}
  • Refine by Author
  • 2 Brázdil, Tomás
  • 1 Boss, Ramon
  • 1 Brozek, Václav
  • 1 Brázdil, Tomáš
  • 1 Brünnler, Kai
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Multi-agent systems
  • 1 Theory of computation
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 1 Bitcoin
  • 1 Bitcoin-S
  • 1 Boolean rank
  • 1 Markov decision process
  • 1 Markov decision processes
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2023
  • 1 2010
  • 1 2012
  • 1 2013
  • 1 2020

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