15 Search Results for "F�bregas, Ignacio"

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.12
Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks

Authors: Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead.
Cite as

Orestis Alpos, Ignacio Amores-Sesar, Christian Cachin, and Michelle Yeo. Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.OPODIS.2023.12,
  author =	{Alpos, Orestis and Amores-Sesar, Ignacio and Cachin, Christian and Yeo, Michelle},
  title =	{{Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.12},
  URN =		{urn:nbn:de:0030-drops-195029},
  doi =		{10.4230/LIPIcs.OPODIS.2023.12},
  annote =	{Keywords: Consensus, MEV, Byzantine behavior, Rational behavior}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.32
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

Authors: Olivier Lalonde, Nikhil S. Mande, and Ronald de Wolf

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting the optimal constant factors in the leading terms in various different models. The following are our results in the randomized model: - We give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error at a small additive cost. This is an improvement over Newman’s theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. - As a consequence we obtain a (log(n/ε²) + 4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε³) + O(1) upper bound implied by Newman’s theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive log log(1/ε) + O(1). The following are our results in various quantum models: - We exhibit a one-way protocol with log(n/ε) + 4 qubits of communication for the n-bit Equality function, to error ε, that uses only pure states. This bound was implicitly already shown by Nayak [PhD thesis'99]. - We give a near-matching lower bound: any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε) - log log(1/ε) - O(1) qubits. - We exhibit a one-way protocol with log(√n/ε) + 3 qubits of communication that uses mixed states. This is tight up to additive log log(1/ε) + O(1), which follows from Alon’s result. - We exhibit a one-way entanglement-assisted protocol achieving error probability ε with ⌈log(1/ε)⌉ + 1 classical bits of communication and ⌈log(√n/ε)⌉ + 4 shared EPR-pairs between Alice and Bob. This matches the communication cost of the classical public coin protocol achieving the same error probability while improving upon the amount of prior entanglement that is needed for this protocol, which is ⌈log(n/ε)⌉ + O(1) shared EPR-pairs. Our upper bounds also yield upper bounds on the approximate rank, approximate nonnegative-rank, and approximate psd-rank of the Identity matrix. As a consequence we also obtain improved upper bounds on these measures for a function that was recently used to refute the randomized and quantum versions of the log-rank conjecture (Chattopadhyay, Mande and Sherif [J. ACM'20], Sinha and de Wolf [FOCS'19], Anshu, Boddu and Touchette [FOCS'19]).
Cite as

Olivier Lalonde, Nikhil S. Mande, and Ronald de Wolf. Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lalonde_et_al:LIPIcs.FSTTCS.2023.32,
  author =	{Lalonde, Olivier and Mande, Nikhil S. and de Wolf, Ronald},
  title =	{{Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.32},
  URN =		{urn:nbn:de:0030-drops-194055},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.32},
  annote =	{Keywords: Communication complexity, quantum communication complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.10
When Is Spring Coming? A Security Analysis of Avalanche Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Avalanche is a blockchain consensus protocol with exceptionally low latency and high throughput. This has swiftly established the corresponding token as a top-tier cryptocurrency. Avalanche achieves such remarkable metrics by substituting proof of work with a random sampling mechanism. The protocol also differs from Bitcoin, Ethereum, and many others by forming a directed acyclic graph (DAG) instead of a chain. It does not totally order all transactions, establishes a partial order among them, and accepts transactions in the DAG that satisfy specific properties. Such parallelism is widely regarded as a technique that increases the efficiency of consensus. Despite its success, Avalanche consensus lacks a complete abstract specification and a matching formal analysis. To address this drawback, this work provides first a detailed formulation of Avalanche through pseudocode. This includes features that are omitted from the original whitepaper or are only vaguely explained in the documentation. Second, the paper gives an analysis of the formal properties fulfilled by Avalanche in the sense of a generic broadcast protocol that only orders related transactions. Last but not least, the analysis reveals a vulnerability that affects the liveness of the protocol. A possible solution that addresses the problem is also proposed.
Cite as

Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi. When Is Spring Coming? A Security Analysis of Avalanche Consensus. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2022.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Tedeschi, Enrico},
  title =	{{When Is Spring Coming? A Security Analysis of Avalanche Consensus}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.10},
  URN =		{urn:nbn:de:0030-drops-176307},
  doi =		{10.4230/LIPIcs.OPODIS.2022.10},
  annote =	{Keywords: Avalanche, security analysis, generic broadcast}
}
Document
DOI: 10.4230/OASIcs.FMBC.2022.3
Automatic Generation of Attacker Contracts in Solidity

Authors: Ignacio Ballesteros, Clara Benac-Earle, Luis Eduardo Bueso de Barrio, Lars-Åke Fredlund, Ángel Herranz, and Julio Mariño

Published in: OASIcs, Volume 105, 4th International Workshop on Formal Methods for Blockchains (FMBC 2022)

Abstract
Smart contracts on the Ethereum blockchain continue to suffer from well-published problems. A particular example is the well-known smart contract reentrancy vulnerability, which continues to be exploited. In this article, we present preliminary work on a method which, given a smart contract that may be vulnerable to such a reentrancy attack, proceeds to attempt to automatically derive an "attacker" contract which can be used to successfully attack the vulnerable contract. The method uses property-based testing to generate, semi-randomly, large numbers of potential attacker contracts, and then proceeds to check whether any of them is a successful attacker. The method is illustrated using a case study where an attack is derived for a vulnerable contract.
Cite as

Ignacio Ballesteros, Clara Benac-Earle, Luis Eduardo Bueso de Barrio, Lars-Åke Fredlund, Ángel Herranz, and Julio Mariño. Automatic Generation of Attacker Contracts in Solidity. In 4th International Workshop on Formal Methods for Blockchains (FMBC 2022). Open Access Series in Informatics (OASIcs), Volume 105, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ballesteros_et_al:OASIcs.FMBC.2022.3,
  author =	{Ballesteros, Ignacio and Benac-Earle, Clara and de Barrio, Luis Eduardo Bueso and Fredlund, Lars-\r{A}ke and Herranz, \'{A}ngel and Mari\~{n}o, Julio},
  title =	{{Automatic Generation of Attacker Contracts in Solidity}},
  booktitle =	{4th International Workshop on Formal Methods for Blockchains (FMBC 2022)},
  pages =	{3:1--3:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-250-1},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{105},
  editor =	{Dargaye, Zaynah and Schneidewind, Clara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.FMBC.2022.3},
  URN =		{urn:nbn:de:0030-drops-171840},
  doi =		{10.4230/OASIcs.FMBC.2022.3},
  annote =	{Keywords: Property-Based Testing, Smart Contracts, Reentrancy Attack}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.10
Security Analysis of Ripple Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes. Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions.
Cite as

Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić. Security Analysis of Ripple Consensus. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2020.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Mi\'{c}i\'{c}, Jovana},
  title =	{{Security Analysis of Ripple Consensus}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.10},
  URN =		{urn:nbn:de:0030-drops-134956},
  doi =		{10.4230/LIPIcs.OPODIS.2020.10},
  annote =	{Keywords: Ripple, Blockchain, Quorums, Consensus}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.46
A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems

Authors: Andrés Fielbaum, Ignacio Morales, and José Verschae

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Obtaining strong linear relaxations of capacitated covering problems constitute a significant technical challenge even for simple settings. For one of the most basic cases, the Knapsack-Cover (Min-Knapsack) problem, the relaxation based on knapsack-cover inequalities has an integrality gap of 2. These inequalities are exploited in more general problems, many of which admit primal-dual approximation algorithms. Inspired by problems from power and transport systems, we introduce a general setting in which items can be taken fractionally to cover a given demand. The cost incurred by an item is given by an arbitrary non-decreasing function of the chosen fraction. We generalize the knapsack-cover inequalities to this setting an use them to obtain a (2+ε)-approximate primal-dual algorithm. Our procedure has a natural interpretation as a bucket-filling algorithm which effectively overcomes the difficulties implied by having different slopes in the cost functions. More precisely, when some superior segment of an item presents a low slope, it helps to increase the priority of inferior segments. We also present a rounding algorithm with an approximation guarantee of 2. We generalize our algorithm to the Unsplittable Flow-Cover problem on a line, also for the setting of fractional items with non-linear costs. For this problem we obtain a (4+ε)-approximation algorithm in polynomial time, almost matching the 4-approximation algorithm known for the classical setting.
Cite as

Andrés Fielbaum, Ignacio Morales, and José Verschae. A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fielbaum_et_al:LIPIcs.ICALP.2020.46,
  author =	{Fielbaum, Andr\'{e}s and Morales, Ignacio and Verschae, Jos\'{e}},
  title =	{{A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.46},
  URN =		{urn:nbn:de:0030-drops-124531},
  doi =		{10.4230/LIPIcs.ICALP.2020.46},
  annote =	{Keywords: Knapsack-Cover Inequalities, Non-Linear Knapsack-Cover, Primal-Dual, Water-Filling Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.25
Distributional Property Testing in a Quantum World

Authors: András Gilyén and Tongyang Li

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. We also introduce a novel access model for quantum distributions, enabling the coherent preparation of quantum samples, and propose a general framework that can naturally handle both classical and quantum distributions in a unified manner. Our framework generalizes and improves previous quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. For classical distributions our algorithms significantly improve the precision dependence of some earlier results. We also show that in our framework procedures for classical distributions can be directly lifted to the more general case of quantum distributions, and thus obtain the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling.
Cite as

András Gilyén and Tongyang Li. Distributional Property Testing in a Quantum World. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gilyen_et_al:LIPIcs.ITCS.2020.25,
  author =	{Gily\'{e}n, Andr\'{a}s and Li, Tongyang},
  title =	{{Distributional Property Testing in a Quantum World}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.25},
  URN =		{urn:nbn:de:0030-drops-117100},
  doi =		{10.4230/LIPIcs.ITCS.2020.25},
  annote =	{Keywords: distributional property testing, quantum algorithms, quantum query complexity}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2017.10
Rule Formats for Nominal Process Calculi

Authors: Luca Aceto, Ignacio Fábregas, Álvaro García-Pérez, Anna Ingólfsdóttir, and Yolanda Ortega-Mallén

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
The nominal transition systems (NTSs) of Parrow et al. describe the operational semantics of nominal process calculi. We study NTSs in terms of the nominal residual transition systems (NRTSs) that we introduce. We provide rule formats for the specifications of NRTSs that ensure that the associated NRTS is an NTS and apply them to the operational specification of the early pi-calculus. Our study stems from the recent Nominal SOS of Cimini et al. and from earlier works in nominal sets and nominal logic by Gabbay, Pitts and their collaborators.
Cite as

Luca Aceto, Ignacio Fábregas, Álvaro García-Pérez, Anna Ingólfsdóttir, and Yolanda Ortega-Mallén. Rule Formats for Nominal Process Calculi. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aceto_et_al:LIPIcs.CONCUR.2017.10,
  author =	{Aceto, Luca and F\'{a}bregas, Ignacio and Garc{\'\i}a-P\'{e}rez, \'{A}lvaro and Ing\'{o}lfsd\'{o}ttir, Anna and Ortega-Mall\'{e}n, Yolanda},
  title =	{{Rule Formats for Nominal Process Calculi}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.10},
  URN =		{urn:nbn:de:0030-drops-77869},
  doi =		{10.4230/LIPIcs.CONCUR.2017.10},
  annote =	{Keywords: nominal sets, nominal structural operational semantics, process algebra, nominal transition systems, scope opening, rule formats}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.37
On the Complexity of Partial Derivatives

Authors: Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace method", recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.
Cite as

Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the Complexity of Partial Derivatives. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{garciamarco_et_al:LIPIcs.STACS.2017.37,
  author =	{Garcia-Marco, Ignacio and Koiran, Pascal and Pecatte, Timoth\'{e}e and Thomass\'{e}, St\'{e}phan},
  title =	{{On the Complexity of Partial Derivatives}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.37},
  URN =		{urn:nbn:de:0030-drops-69964},
  doi =		{10.4230/LIPIcs.STACS.2017.37},
  annote =	{Keywords: counting complexity, simplicial complex, lower bounds, arithmetic circuits}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.39
How Many Quantum Correlations Are Not Local?

Authors: Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We study how generic is the property of nonlocality among the set of quantum correlations for bipartite dichotomic measurements. To do so, we consider the characterization of these quantum correlations as those of the form gamma = ( < u_i , v_j > )_{i,j=1}^n , where the vectors u_i and v_j are in the unit sphere of a real Hilbert space. The important parameters in this description are the number of vectors n and the dimension of the Hilbert space m. Thus, it is natural to study the probability of a quantum correlation being nonlocal as a function of alpha = m/n , where the previous vectors are independent and uniformly distributed in the unit sphere of R^m. In this situation, our main result shows the existence of two completely different regimes: There exists an alpha_0 > 0 such that if alpha leq alpha_0, then gamma is nonlocal with probability tending to 1 as n rightarrow infty. On the other hand, if alpha geq 2 then gamma is local with probability tending to 1 as n rightarrow infty.
Cite as

Carlos E. González-Guillén, C. Hugo Jiménez, Carlos Palazuelos, and Ignacio Villanueva. How Many Quantum Correlations Are Not Local?. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 39-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gonzalezguillen_et_al:LIPIcs.TQC.2015.39,
  author =	{Gonz\'{a}lez-Guill\'{e}n, Carlos E. and Jim\'{e}nez, C. Hugo and Palazuelos, Carlos and Villanueva, Ignacio},
  title =	{{How Many Quantum Correlations Are Not Local?}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{39--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.39},
  URN =		{urn:nbn:de:0030-drops-55475},
  doi =		{10.4230/LIPIcs.TQC.2015.39},
  annote =	{Keywords: nonlocality, quantum correlations, Bell inequalities, random matrices}
}
Document
DOI: 10.4230/DagRep.4.7.52
Information-Centric Networking 3 (Dagstuhl Seminar 14291)

Authors: Dirk Kutscher, Taekyoung Kwon, and Ignacio Solis

Published in: Dagstuhl Reports, Volume 4, Issue 7 (2014)

Abstract
This report documents the presentations and discussions of the 3rd Dagstuhl seminar on Information-Centric Networks. This seminar was focused on the deployment and scalability of ICNs. An overview of various ICN projects was used as a starting point for discussions. Participants provided a set of starting questions to cover with the rest of the group. The seminar increased the awareness on the state of the art in ICN research. Various topics on deployment and scalability were discussed. The opinions and comments presented here came directly from the notes taken at the seminar.
Cite as

Dirk Kutscher, Taekyoung Kwon, and Ignacio Solis. Information-Centric Networking 3 (Dagstuhl Seminar 14291). In Dagstuhl Reports, Volume 4, Issue 7, pp. 52-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{kutscher_et_al:DagRep.4.7.52,
  author =	{Kutscher, Dirk and Kwon, Taekyoung and Solis, Ignacio},
  title =	{{Information-Centric Networking 3 (Dagstuhl Seminar 14291)}},
  pages =	{52--61},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{7},
  editor =	{Kutscher, Dirk and Kwon, Taekyoung and Solis, Ignacio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.7.52},
  URN =		{urn:nbn:de:0030-drops-47854},
  doi =		{10.4230/DagRep.4.7.52},
  annote =	{Keywords: Information-Centric, Content-Centric, Name-Based, Content-Based, Networks}
}
Document
DOI: 10.4230/DagRep.2.9.1
Information-centric networking -- Ready for the real world? (Dagstuhl Seminar 12361)

Authors: Ali Ghodsi, Börje Ohlman, Jörg Ott, Ignacio Solis, and Matthias Wählisch

Published in: Dagstuhl Reports, Volume 2, Issue 9 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12361 ``Information-centric networking -- Ready for the real world?''. The outcome of this seminar is based on individual talks, group work, and significant discussions among all participants. The topics range from application and performance aspects up to business, legal, and deployment questions. Even though significant progress is visible from the last Dagstuhl Seminar about ICN, there are still thrilling open research questions in all topic areas.
Cite as

Ali Ghodsi, Börje Ohlman, Jörg Ott, Ignacio Solis, and Matthias Wählisch. Information-centric networking -- Ready for the real world? (Dagstuhl Seminar 12361). In Dagstuhl Reports, Volume 2, Issue 9, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{ghodsi_et_al:DagRep.2.9.1,
  author =	{Ghodsi, Ali and Ohlman, B\"{o}rje and Ott, J\"{o}rg and Solis, Ignacio and W\"{a}hlisch, Matthias},
  title =	{{Information-centric networking -- Ready for the real world? (Dagstuhl Seminar 12361)}},
  pages =	{1--14},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{9},
  editor =	{Ghodsi, Ali and Ohlman, B\"{o}rje and Ott, J\"{o}rg and Solis, Ignacio and W\"{a}hlisch, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.9.1},
  URN =		{urn:nbn:de:0030-drops-37877},
  doi =		{10.4230/DagRep.2.9.1},
  annote =	{Keywords: Information-centric, Network architecture, Application structure, Internet business models}
}
Document
DOI: 10.4230/DagSemProc.10492.1
10492 Abstracts Collection – Information-Centric Networking

Authors: Dirk Kutscher, Bengt Ahlgren, Holger Karl, Börje Ohlman, Sara Oueslati, and Ignacio Solis

Published in: Dagstuhl Seminar Proceedings, Volume 10492, Information-Centric Networking (2011)

Abstract
From December 5th to 8th 2010, the Dagstuhl Seminar 10492 on "Information-Centric Networking" 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

Dirk Kutscher, Bengt Ahlgren, Holger Karl, Börje Ohlman, Sara Oueslati, and Ignacio Solis. 10492 Abstracts Collection – Information-Centric Networking. In Information-Centric Networking. Dagstuhl Seminar Proceedings, Volume 10492, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kutscher_et_al:DagSemProc.10492.1,
  author =	{Kutscher, Dirk and Ahlgren, Bengt and Karl, Holger and Ohlman, B\"{o}rje and Oueslati, Sara and Solis, Ignacio},
  title =	{{10492 Abstracts Collection – Information-Centric Networking}},
  booktitle =	{Information-Centric Networking},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10492},
  editor =	{Bengt Ahlgren and Holger Karl and Dirk Kutscher and B\"{o}rje Ohlman and Sara Oueslati and Ignacio Solis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10492.1},
  URN =		{urn:nbn:de:0030-drops-29437},
  doi =		{10.4230/DagSemProc.10492.1},
  annote =	{Keywords: Information-Centric Networking, ICN, Content-Centric Networking, CCN, Data-Oriented Networking, DONA, NetInf, 4WARD, SAIL}
}
Document
DOI: 10.4230/DagSemProc.10492.2
10492 Executive Summary – Information-Centric Networking

Authors: Dirk Kutscher, Bengt Ahlgren, Holger Karl, Börje Ohlman, Sara Oueslati, and Ignacio Solis

Published in: Dagstuhl Seminar Proceedings, Volume 10492, Information-Centric Networking (2011)

Abstract
This document provides the executive summary of Dagstuhl seminar 10492 on Information-Centric Networking, which took place from December 5th to 8th 2010.
Cite as

Dirk Kutscher, Bengt Ahlgren, Holger Karl, Börje Ohlman, Sara Oueslati, and Ignacio Solis. 10492 Executive Summary – Information-Centric Networking. In Information-Centric Networking. Dagstuhl Seminar Proceedings, Volume 10492, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kutscher_et_al:DagSemProc.10492.2,
  author =	{Kutscher, Dirk and Ahlgren, Bengt and Karl, Holger and Ohlman, B\"{o}rje and Oueslati, Sara and Solis, Ignacio},
  title =	{{10492 Executive Summary – Information-Centric Networking}},
  booktitle =	{Information-Centric Networking},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10492},
  editor =	{Bengt Ahlgren and Holger Karl and Dirk Kutscher and B\"{o}rje Ohlman and Sara Oueslati and Ignacio Solis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10492.2},
  URN =		{urn:nbn:de:0030-drops-29422},
  doi =		{10.4230/DagSemProc.10492.2},
  annote =	{Keywords: Information-Centric Networking, ICN, Content-Centric Networking, CCN, Data-Oriented Networking, DONA, NetInf, 4WARD, SAIL}
}
Document
DOI: 10.4230/DagSemProc.10492.3
A Survey of Information-Centric Networking (Draft)

Authors: Bengt Ahlgren, Christian Dannewitz, Claudio Imbrenda, Dirk Kutscher, and Börje Ohlman

Published in: Dagstuhl Seminar Proceedings, Volume 10492, Information-Centric Networking (2011)

Abstract
In this paper we compare and discuss some of the features and design choices of the 4WARD Networking of Information architecture (NetInf), PARC's Content Centric Networking(CCN), the Publish-Subscribe Internet Routing Paradigm (PSIRP), and the Data Oriented Network Architecture (DONA). All four projects take an information-centric approach to designing a future network architecture, where the information objects themselves are the primary focus rather than the network nodes.
Cite as

Bengt Ahlgren, Christian Dannewitz, Claudio Imbrenda, Dirk Kutscher, and Börje Ohlman. A Survey of Information-Centric Networking (Draft). In Information-Centric Networking. Dagstuhl Seminar Proceedings, Volume 10492, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{ahlgren_et_al:DagSemProc.10492.3,
  author =	{Ahlgren, Bengt and Dannewitz, Christian and Imbrenda, Claudio and Kutscher, Dirk and Ohlman, B\"{o}rje},
  title =	{{A Survey of Information-Centric Networking (Draft)}},
  booktitle =	{Information-Centric Networking},
  pages =	{1--26},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10492},
  editor =	{Bengt Ahlgren and Holger Karl and Dirk Kutscher and B\"{o}rje Ohlman and Sara Oueslati and Ignacio Solis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10492.3},
  URN =		{urn:nbn:de:0030-drops-29410},
  doi =		{10.4230/DagSemProc.10492.3},
  annote =	{Keywords: ICN, CCN, NetInf, DONA, PSIRP}
}
  • Refine by Author
  • 4 Kutscher, Dirk
  • 4 Ohlman, Börje
  • 4 Solis, Ignacio
  • 3 Ahlgren, Bengt
  • 3 Amores-Sesar, Ignacio
  • Show More...

  • Refine by Classification
  • 2 Software and its engineering → Distributed systems organizing principles
  • 2 Theory of computation → Cryptographic protocols
  • 1 Mathematics of computing → Discrete optimization
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Linear programming
  • Show More...

  • Refine by Keyword
  • 3 CCN
  • 3 DONA
  • 3 ICN
  • 3 NetInf
  • 2 4WARD
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 3 2011
  • 2 2017
  • 2 2020
  • 2 2023
  • 1 2013
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact