4 Search Results for "Sanders, William"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.22
Lower Bound Methods for Sign-Rank and Their Limitations

Authors: Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao

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

Abstract
The sign-rank of a matrix A with ±1 entries is the smallest rank of a real matrix with the same sign pattern as A. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is at least the VC-dimension; (ii) Forster’s method, which states that sign-rank is at least the inverse of the largest possible average margin among the representations of the matrix by points and half-spaces; (iii) Sign-rank is at least a logarithmic function of the density of the largest monochromatic rectangle. We prove several results regarding the limitations of these methods. - We prove that, qualitatively, the monochromatic rectangle density is the strongest of these three lower bounds. If it fails to provide a super-constant lower bound for the sign-rank of a matrix, then the other two methods will fail as well. - We show that there exist n × n matrices with sign-rank n^Ω(1) for which none of these methods can provide a super-constant lower bound. - We show that sign-rank is at most an exponential function of the deterministic communication complexity with access to an equality oracle. We combine this result with Green and Sanders' quantitative version of Cohen’s idempotent theorem to show that for a large class of sign matrices (e.g., xor-lifts), sign-rank is at most an exponential function of the γ₂ norm of the matrix. We conjecture that this holds for all sign matrices. - Towards answering a question of Linial, Mendelson, Schechtman, and Shraibman regarding the relation between sign-rank and discrepancy, we conjecture that sign-ranks of the ±1 adjacency matrices of hypercube graphs can be arbitrarily large. We prove that none of the three lower bound techniques can resolve this conjecture in the affirmative.
Cite as

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower Bound Methods for Sign-Rank and Their Limitations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 22:1-22:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hatami_et_al:LIPIcs.APPROX/RANDOM.2022.22,
  author =	{Hatami, Hamed and Hatami, Pooya and Pires, William and Tao, Ran and Zhao, Rosie},
  title =	{{Lower Bound Methods for Sign-Rank and Their Limitations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{22:1--22:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.22},
  URN =		{urn:nbn:de:0030-drops-171445},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.22},
  annote =	{Keywords: Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Sign-rank, Unbounded-error communication complexity, VC-dimension}
}
Document
DOI: 10.4230/OASIcs.Tokenomics.2020.8
Parasite Chain Detection in the IOTA Protocol

Authors: Andreas Penzkofer, Bartosz Kusmierz, Angelo Capossele, William Sanders, and Olivia Saa

Published in: OASIcs, Volume 82, 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)

Abstract
In recent years several distributed ledger technologies based on directed acyclic graphs (DAGs) have appeared on the market. Similar to blockchain technologies, DAG-based systems aim to build an immutable ledger and are faced with security concerns regarding the irreversibility of the ledger state. However, due to their more complex nature and recent popularity, the study of adversarial actions has received little attention so far. In this paper we are concerned with a particular type of attack on the IOTA cryptocurrency, more specifically a Parasite Chain attack that attempts to revert the history stored in the DAG structure, also called the Tangle. In order to improve the security of the Tangle, we present a detection mechanism for this type of attack. In this mechanism, we embrace the complexity of the DAG structure by sampling certain aspects of it, more particularly the distribution of the number of approvers. We initially describe models that predict the distribution that should be expected for a Tangle without any malicious actors. We then introduce metrics that compare this reference distribution with the measured distribution. Upon detection, measures can then be taken to render the attack unsuccessful. We show that due to a form of the Parasite Chain that is different from the main Tangle it is possible to detect certain types of malicious chains. We also show that although the attacker may change the structure of the Parasite Chain to avoid detection, this is done so at a significant cost since the attack is rendered less efficient.
Cite as

Andreas Penzkofer, Bartosz Kusmierz, Angelo Capossele, William Sanders, and Olivia Saa. Parasite Chain Detection in the IOTA Protocol. In 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020). Open Access Series in Informatics (OASIcs), Volume 82, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{penzkofer_et_al:OASIcs.Tokenomics.2020.8,
  author =	{Penzkofer, Andreas and Kusmierz, Bartosz and Capossele, Angelo and Sanders, William and Saa, Olivia},
  title =	{{Parasite Chain Detection in the IOTA Protocol}},
  booktitle =	{2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)},
  pages =	{8:1--8:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-157-3},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{82},
  editor =	{Anceaume, Emmanuelle and Bisi\`{e}re, Christophe and Bouvard, Matthieu and Bramas, Quentin and Casamatta, Catherine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2020.8},
  URN =		{urn:nbn:de:0030-drops-135306},
  doi =		{10.4230/OASIcs.Tokenomics.2020.8},
  annote =	{Keywords: Distributed ledger technology, cryptocurrency, directed acyclic graph, security, attack detection algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.42
A Polynomial Kernel for Line Graph Deletion

Authors: Eduard Eiben and William Lochet

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some graph. We study the Line-Graph-Edge Deletion problem, which asks whether we can delete at most k edges from the input graph G such that the resulting graph is a line graph. More precisely, we give a polynomial kernel for Line-Graph-Edge Deletion with O(k⁵) vertices. This answers an open question posed by Falk Hüffner at Workshop on Kernels (WorKer) in 2013.
Cite as

Eduard Eiben and William Lochet. A Polynomial Kernel for Line Graph Deletion. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ESA.2020.42,
  author =	{Eiben, Eduard and Lochet, William},
  title =	{{A Polynomial Kernel for Line Graph Deletion}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.42},
  URN =		{urn:nbn:de:0030-drops-129088},
  doi =		{10.4230/LIPIcs.ESA.2020.42},
  annote =	{Keywords: Kernelization, line graphs, H-free editing, graph modification problem}
}
Document
DOI: 10.4230/DagRep.4.1.36
Randomized Timed and Hybrid Models for Critical Infrastructures (Dagstuhl Seminar 14031)

Authors: Erika Ábrahám, Alberto Avritzer, Anne Remke, and William H. Sanders

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

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14031 "Randomized Timed and Hybrid Models for Critical Infrastructures". Critical Infrastructures, such as power grid and water and gas distribution networks, are essential for the functioning of our society and economy. Randomized Timed and Hybrid Models appear as a natural choice for their modeling, and come with existing algorithms and tool support for their analysis. However, on the one hand, the Critical Infrastructures community does not yet make full use of recent advances for Randomized Timed and Hybrid Models. On the other hand, existing algorithms are not yet readily applicable to the special kind of problems arising in Critical Infrastructures. This seminar brought together researchers from these fields to communicate with each other and to exchange knowledge, experiences and needs.
Cite as

Erika Ábrahám, Alberto Avritzer, Anne Remke, and William H. Sanders. Randomized Timed and Hybrid Models for Critical Infrastructures (Dagstuhl Seminar 14031). In Dagstuhl Reports, Volume 4, Issue 1, pp. 36-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{abraham_et_al:DagRep.4.1.36,
  author =	{\'{A}brah\'{a}m, Erika and Avritzer, Alberto and Remke, Anne and Sanders, William H.},
  title =	{{Randomized Timed and Hybrid Models for Critical Infrastructures (Dagstuhl Seminar 14031)}},
  pages =	{36--82},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{1},
  editor =	{\'{A}brah\'{a}m, Erika and Avritzer, Alberto and Remke, Anne and Sanders, William H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.1.36},
  URN =		{urn:nbn:de:0030-drops-45355},
  doi =		{10.4230/DagRep.4.1.36},
  annote =	{Keywords: Critical Infrastructures, Smart Grids, Modeling, Randomized Timed and Hybrid Models, Analysis}
}
  • Refine by Author
  • 1 Avritzer, Alberto
  • 1 Capossele, Angelo
  • 1 Eiben, Eduard
  • 1 Hatami, Hamed
  • 1 Hatami, Pooya
  • Show More...

  • Refine by Classification
  • 1 Networks → Security protocols
  • 1 Theory of computation → Boolean function learning
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Analysis
  • 1 Average Margin
  • 1 Communication complexity
  • 1 Critical Infrastructures
  • 1 Distributed ledger technology
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2014
  • 1 2020
  • 1 2021
  • 1 2022

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