5 Search Results for "Brânzei, Simina"

Document
DOI: 10.4230/LIPIcs.STACS.2026.14
Computing Tarski Fixed Points in Financial Networks

Authors: Leander Besting, Martin Hoefer, and Lars Huth

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Modern financial networks are highly connected and result in complex interdependencies of the involved institutions. In the prominent Eisenberg-Noe model [Eisenberg and Noe, 2001], a fundamental aspect is clearing - to determine the amount of assets available to each financial institution in the presence of potential defaults and bankruptcy. A clearing state represents a fixed point that satisfies a set of natural axioms. Existence can be established (even in broad generalizations of the model) using Tarski’s theorem. While a maximal fixed point can be computed in polynomial time, the complexity of computing other fixed points is open. In this paper, we provide an efficient algorithm to compute a minimal fixed point. Our algorithm applies in a broad generalization of the Eisenberg-Noe model with any monotone, piecewise-linear payment functions and default costs. We also study claims trading, a local network adjustment to improve clearing, when networks are evaluated with minimal clearing. We provide an efficient algorithm to decide existence of Pareto-improving trades and compute optimal ones if they exist.
Cite as

Leander Besting, Martin Hoefer, and Lars Huth. Computing Tarski Fixed Points in Financial Networks. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{besting_et_al:LIPIcs.STACS.2026.14,
  author =	{Besting, Leander and Hoefer, Martin and Huth, Lars},
  title =	{{Computing Tarski Fixed Points in Financial Networks}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.14},
  URN =		{urn:nbn:de:0030-drops-255038},
  doi =		{10.4230/LIPIcs.STACS.2026.14},
  annote =	{Keywords: Tarski Fixed Points, Financial Networks, Minimal Clearing, Claims Trade}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.52
Tarski Lower Bounds from Multi-Dimensional Herringbones

Authors: Simina Brânzei, Reed C. Phillips, and Nicholas J. Recker

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

Abstract
Tarski’s theorem states that every monotone function from a complete lattice to itself has a fixed point. We analyze the query complexity of finding such a fixed point on the k-dimensional grid of side length n under the ≤ relation. In this setting, there is an unknown monotone function f: {0,1,…, n-1}^k → {0,1,…, n-1}^k and an algorithm must query a vertex v to learn f(v). The goal is to find a fixed point of f using as few oracle queries as possible. We show that the randomized query complexity of this problem is Ω((k⋅log²n)/log k) for all n,k ≥ 2. This unifies and improves upon two prior results: a lower bound of Ω(log²n) from [Etessami et al., 2020] and a lower bound of Ω((k⋅log(n)/log(k)) from [Brânzei et al., 2024], respectively.
Cite as

Simina Brânzei, Reed C. Phillips, and Nicholas J. Recker. Tarski Lower Bounds from Multi-Dimensional Herringbones. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{branzei_et_al:LIPIcs.APPROX/RANDOM.2025.52,
  author =	{Br\^{a}nzei, Simina and Phillips, Reed C. and Recker, Nicholas J.},
  title =	{{Tarski Lower Bounds from Multi-Dimensional Herringbones}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.52},
  URN =		{urn:nbn:de:0030-drops-244186},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.52},
  annote =	{Keywords: Tarski’s theorem, monotone functions, lattices, fixed points, computational complexity, oracle model, query complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.84
Quantum Communication Complexity of Classical Auctions

Authors: Aviad Rubinstein and Zixin Zhou

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the fundamental, classical mechanism design problem of single-buyer multi-item Bayesian revenue-maximizing auctions under the lens of communication complexity between the buyer and the seller. Specifically, we ask whether using quantum communication can be more efficient than classical communication. We have two sets of results, revealing a surprisingly rich landscape - which looks quite different from both quantum communication in non-strategic parties, and classical communication in mechanism design. We first study the expected communication complexity of approximately optimal auctions. We give quantum auction protocols for buyers with unit-demand or combinatorial valuations that obtain an arbitrarily good approximation of the optimal revenue while running in exponentially more efficient communication compared to classical approximately optimal auctions. However, these auctions come with the caveat that they may require the seller to charge exponentially large payments from a deviating buyer. We show that this caveat is necessary - we give an exponential lower bound on the product of the expected quantum communication and the maximum payment. We then study the worst-case communication complexity of exactly optimal auctions in an extremely simple setting: additive buyer’s valuations over two items. We show the following separations: - There exists a prior where the optimal classical auction protocol requires infinitely many bits, but a one-way message of 1 qubit and 2 classical bits suffices. - There exists a prior where no finite one-way quantum auction protocol can obtain the optimal revenue. However, there is a barely-interactive revenue-optimal quantum auction protocol with the following simple structure: the seller prepares a pair of qubits in the EPR state, sends one of them to the buyer, and then the buyer sends 1 qubit and 2 classical bits. - There exists a prior where no multi-round quantum auction protocol with a finite bound on communication complexity can obtain the optimal revenue.
Cite as

Aviad Rubinstein and Zixin Zhou. Quantum Communication Complexity of Classical Auctions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 84:1-84:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2025.84,
  author =	{Rubinstein, Aviad and Zhou, Zixin},
  title =	{{Quantum Communication Complexity of Classical Auctions}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{84:1--84:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.84},
  URN =		{urn:nbn:de:0030-drops-227124},
  doi =		{10.4230/LIPIcs.ITCS.2025.84},
  annote =	{Keywords: Mechanism design, Communication complexity, Quantum computing}
}
Document
DOI: 10.4230/LIPIcs.ITC.2021.16
P₄-free Partition and Cover Numbers & Applications

Authors: Alexander R. Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract
P₄-free graphs- also known as cographs, complement-reducible graphs, or hereditary Dacey graphs-have been well studied in graph theory. Motivated by computer science and information theory applications, our work encodes (flat) joint probability distributions and Boolean functions as bipartite graphs and studies bipartite P₄-free graphs. For these applications, the graph properties of edge partitioning and covering a bipartite graph using the minimum number of these graphs are particularly relevant. Previously, such graph properties have appeared in leakage-resilient cryptography and (variants of) coloring problems. Interestingly, our covering problem is closely related to the well-studied problem of product (a.k.a., Prague) dimension of loopless undirected graphs, which allows us to employ algebraic lower-bounding techniques for the product/Prague dimension. We prove that computing these numbers is NP-complete, even for bipartite graphs. We establish a connection to the (unsolved) Zarankiewicz problem to show that there are bipartite graphs with size-N partite sets such that these numbers are at least ε⋅N^{1-2ε}, for ε ∈ {1/3,1/4,1/5,...}. Finally, we accurately estimate these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, such as set intersection, set disjointness, and inequality. For applications in information theory and communication & cryptographic complexity, we consider a system where a setup samples from a (flat) joint distribution and gives the participants, Alice and Bob, their portion from this joint sample. Alice and Bob’s objective is to non-interactively establish a shared key and extract the left-over entropy from their portion of the samples as independent private randomness. A genie, who observes the joint sample, provides appropriate assistance to help Alice and Bob with their objective. Lower bounds to the minimum size of the genie’s assistance translate into communication and cryptographic lower bounds. We show that (the log₂ of) the P₄-free partition number of a graph encoding the joint distribution that the setup uses is equivalent to the size of the genie’s assistance. Consequently, the joint distributions corresponding to the bipartite graphs constructed above with high P₄-free partition numbers correspond to joint distributions requiring more assistance from the genie. As a representative application in non-deterministic communication complexity, we study the communication complexity of nondeterministic protocols augmented by access to the equality oracle at the output. We show that (the log₂ of) the P₄-free cover number of the bipartite graph encoding a Boolean function f is equivalent to the minimum size of the nondeterministic input required by the parties (referred to as the communication complexity of f in this model). Consequently, the functions corresponding to the bipartite graphs with high P₄-free cover numbers have high communication complexity. Furthermore, there are functions with communication complexity close to the naïve protocol where the nondeterministic input reveals a party’s input. Finally, the access to the equality oracle reduces the communication complexity of computing set disjointness by a constant factor in contrast to the model where parties do not have access to the equality oracle. To compute the inequality function, we show an exponential reduction in the communication complexity, and this bound is optimal. On the other hand, access to the equality oracle is (nearly) useless for computing set intersection.
Cite as

Alexander R. Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen. P₄-free Partition and Cover Numbers & Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 16:1-16:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{block_et_al:LIPIcs.ITC.2021.16,
  author =	{Block, Alexander R. and Br\^{a}nzei, Simina and Maji, Hemanta K. and Mehta, Himanshi and Mukherjee, Tamalika and Nguyen, Hai H.},
  title =	{{P₄-free Partition and Cover Numbers \& Applications}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{16:1--16:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.16},
  URN =		{urn:nbn:de:0030-drops-143357},
  doi =		{10.4230/LIPIcs.ITC.2021.16},
  annote =	{Keywords: Secure keys, Secure private randomness, Gray-Wyner system, Cryptographic complexity, Nondeterministic communication complexity, Leakage-resilience, Combinatorial optimization, Product dimension, Zarankiewicz problem, Algebraic lower-bounding techniques, P₄-free partition number, P₄-free cover number}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.80
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}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2021
  • 1 2017

  • Refine by Author
  • 3 Brânzei, Simina
  • 1 Besting, Leander
  • 1 Block, Alexander R.
  • 1 Filos-Ratsikas, Aris
  • 1 Hoefer, Martin
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Communication complexity
  • 1 Mathematics of computing → Graph theory
  • 1 Networks → Network algorithms
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Security and privacy → Mathematical foundations of cryptography
  • Show More...

  • Refine by Keyword
  • 1 Algebraic lower-bounding techniques
  • 1 Claims Trade
  • 1 Combinatorial optimization
  • 1 Communication complexity
  • 1 Cryptographic complexity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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