179 Search Results for "R�, Christopher"

Document
DOI: 10.4230/DagRep.13.11.103
Defining and Fortifying Against Cognitive Vulnerabilities in Social Engineering (Dagstuhl Seminar 23462)

Authors: Yomna Abdelrahman, Florian Alt, Tilman Dingler, Christopher Hadnagy, Abbie Maroño, and Verena Distler

Published in: Dagstuhl Reports, Volume 13, Issue 11 (2024)

Abstract
Social engineering has become the main vector for human-centered cyber attacks, resulting from an unparalleled level of professionalization in the cybercrime industry over the past years. Hereby, through manipulation, criminals seek to make victims take actions that compromise security, such as revealing credentials, issuing payments, or disclosing confidential information. Little effective means for protection exist today against such attacks beyond raising awareness through education. At the same time, the proliferation of sensors in our everyday lives - both in personal devices and in our (smart) environments - provides an unprecedented opportunity for developing solutions assessing the cognitive vulnerabilities of users and serves as a basis for novel means of protection. This report documents the program and the outcomes of the Dagstuhl Seminar 23462 "Defining and Fortifying Against Cognitive Vulnerabilities in Social Engineering". This 3-day seminar brought together experts from academia, industry, and the authorities working on social engineering. During the seminar, participants developed a common understanding of social engineering, identified grand challenges, worked on a research agenda, and identified ideas for collaborations in the form of research projects and joint initiatives.
Cite as

Yomna Abdelrahman, Florian Alt, Tilman Dingler, Christopher Hadnagy, Abbie Maroño, and Verena Distler. Defining and Fortifying Against Cognitive Vulnerabilities in Social Engineering (Dagstuhl Seminar 23462). In Dagstuhl Reports, Volume 13, Issue 11, pp. 103-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{abdelrahman_et_al:DagRep.13.11.103,
  author =	{Abdelrahman, Yomna and Alt, Florian and Dingler, Tilman and Hadnagy, Christopher and Maro\~{n}o, Abbie and Distler, Verena},
  title =	{{Defining and Fortifying Against Cognitive Vulnerabilities in Social Engineering (Dagstuhl Seminar 23462)}},
  pages =	{103--129},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{11},
  editor =	{Abdelrahman, Yomna and Alt, Florian and Dingler, Tilman and Hadnagy, Christopher and Maro\~{n}o, Abbie and Distler, Verena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.11.103},
  URN =		{urn:nbn:de:0030-drops-198461},
  doi =		{10.4230/DagRep.13.11.103},
  annote =	{Keywords: Social Engineering, Cognitive Vulnerabilities, Phishing, Vishing}
}
Document
DOI: 10.4230/DagRep.13.11.151
MAD: Microarchitectural Attacks and Defenses (Dagstuhl Seminar 23481)

Authors: Christopher W. Fletcher, Marco Guarnieri, David Kohlbrenner, and Clémentine Maurice

Published in: Dagstuhl Reports, Volume 13, Issue 11 (2024)

Abstract
Microarchitectural attacks subvert the security assumptions many software-level security mechanisms rely upon, thereby threatening the security of our IT systems. These attacks exploit the side-effects (like subtle timing differences in a program’s execution time) resulting from a processor’s internal optimizations to leak sensitive information and compromise a system’s security. Building systems that are resistant against such attacks requires fundamentally rethinking the design of hardware and software security mechanisms. This seminar gathered together leading researchers that are working on security at the hardware-software interface spanning four different communities: computer security, computer architectures, programming languages and verification, and applied cryptography. The goals were to (1) present a comprehensive overview of current advances in microarchitectural attacks and defenses, (2) foster interaction and future collaboration between researchers from different research communities, and (3) identify interesting research directions and open challenges that need to be addressed to build the next generation of systems that are resistant to microarchitectural attacks.
Cite as

Christopher W. Fletcher, Marco Guarnieri, David Kohlbrenner, and Clémentine Maurice. MAD: Microarchitectural Attacks and Defenses (Dagstuhl Seminar 23481). In Dagstuhl Reports, Volume 13, Issue 11, pp. 151-166, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{fletcher_et_al:DagRep.13.11.151,
  author =	{Fletcher, Christopher W. and Guarnieri, Marco and Kohlbrenner, David and Maurice, Cl\'{e}mentine},
  title =	{{MAD: Microarchitectural Attacks and Defenses (Dagstuhl Seminar 23481)}},
  pages =	{151--166},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{11},
  editor =	{Fletcher, Christopher W. and Guarnieri, Marco and Kohlbrenner, David and Maurice, Cl\'{e}mentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.11.151},
  URN =		{urn:nbn:de:0030-drops-198488},
  doi =		{10.4230/DagRep.13.11.151},
  annote =	{Keywords: hardware-software co-design for security, microarchitectural attacks, security architectures, side-channel analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.13
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra

Authors: Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, and David P. Woodruff

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Let S ∈ ℝ^{n × n} be any matrix satisfying ‖1-S‖₂ ≤ εn, where 1 is the all ones matrix and ‖⋅‖₂ is the spectral norm. It is well-known that there exists S with just O(n/ε²) non-zero entries achieving this guarantee: we can let 𝐒 be the scaled adjacency matrix of a Ramanujan expander graph. We show that, beyond giving a sparse approximation to the all ones matrix, 𝐒 yields a universal sparsifier for any positive semidefinite (PSD) matrix. In particular, for any PSD A ∈ ℝ^{n×n} which is normalized so that its entries are bounded in magnitude by 1, we show that ‖A-A∘S‖₂ ≤ ε n, where ∘ denotes the entrywise (Hadamard) product. Our techniques also yield universal sparsifiers for non-PSD matrices. In this case, we show that if S satisfies ‖1-S‖₂ ≤ (ε²n)/(c log²(1/ε)) for some sufficiently large constant c, then ‖A-A∘S‖₂ ≤ ε⋅max(n,‖ A‖₁), where ‖A‖₁ is the nuclear norm. Again letting 𝐒 be a scaled Ramanujan graph adjacency matrix, this yields a sparsifier with Õ(n/ε⁴) entries. We prove that the above universal sparsification bounds for both PSD and non-PSD matrices are tight up to logarithmic factors. Since 𝐀∘𝐒 can be constructed deterministically without reading all of A, our result for PSD matrices derandomizes and improves upon established results for randomized matrix sparsification, which require sampling a random subset of O((n log n)/ε²) entries and only give an approximation to any fixed A with high probability. We further show that any randomized algorithm must read at least Ω(n/ε²) entries to spectrally approximate general A to error εn, thus proving that these existing randomized algorithms are optimal up to logarithmic factors. We leverage our deterministic sparsification results to give the first {deterministic algorithms} for several problems, including singular value and singular vector approximation and positive semidefiniteness testing, that run in faster than matrix multiplication time. This partially addresses a significant gap between randomized and deterministic algorithms for fast linear algebraic computation. Finally, if A ∈ {-1,0,1}^{n × n} is PSD, we show that a spectral approximation à with ‖A-Ã‖₂ ≤ ε n can be obtained by deterministically reading Õ(n/ε) entries of A. This improves the 1/ε dependence on our result for general PSD matrices by a quadratic factor and is information-theoretically optimal up to a logarithmic factor.
Cite as

Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, and David P. Woodruff. Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 13:1-13:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.ITCS.2024.13,
  author =	{Bhattacharjee, Rajarshi and Dexter, Gregory and Musco, Cameron and Ray, Archan and Sachdeva, Sushant and Woodruff, David P.},
  title =	{{Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{13:1--13:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.13},
  URN =		{urn:nbn:de:0030-drops-195415},
  doi =		{10.4230/LIPIcs.ITCS.2024.13},
  annote =	{Keywords: sublinear algorithms, randomized linear algebra, spectral sparsification, expanders}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.62
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems

Authors: Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.
Cite as

Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye. On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 62:1-62:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ITCS.2024.62,
  author =	{Henzinger, Monika and Saha, Barna and Seybold, Martin P. and Ye, Christopher},
  title =	{{On the Complexity of Algorithms with Predictions for Dynamic Graph Problems}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{62:1--62:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.62},
  URN =		{urn:nbn:de:0030-drops-195907},
  doi =		{10.4230/LIPIcs.ITCS.2024.62},
  annote =	{Keywords: Dynamic Graph Algorithms, Algorithms with Predictions}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.22
Languages Given by Finite Automata over the Unary Alphabet

Authors: Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michał Skrzypczak, Frank Stephan, and Christopher Tan

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

Abstract
This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary and n the number of states of the finite automata considered. The following main results are obtained: 1) Equality and inclusion of NFAs can be decided within time 2^O((n log n)^{1/3}); previous upper bound 2^O((n log n)^{1/2}) was by Chrobak (1986) via DFA conversion. 2) The state complexity of operations of UFAs (unambiguous finite automata) increases for complementation and union at most by quasipolynomial; however, for concatenation of two n-state UFAs, the worst case is an UFA of at least 2^Ω(n^{1/6}) states. Previously the upper bounds for complementation and union were exponential-type and this lower bound for concatenation is new.
Cite as

Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michał Skrzypczak, Frank Stephan, and Christopher Tan. Languages Given by Finite Automata over the Unary Alphabet. 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. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{czerwinski_et_al:LIPIcs.FSTTCS.2023.22,
  author =	{Czerwi\'{n}ski, Wojciech and D\k{e}bski, Maciej and Gogasz, Tomasz and Hoi, Gordon and Jain, Sanjay and Skrzypczak, Micha{\l} and Stephan, Frank and Tan, Christopher},
  title =	{{Languages Given by Finite Automata over the Unary Alphabet}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{22:1--22:20},
  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.22},
  URN =		{urn:nbn:de:0030-drops-193959},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.22},
  annote =	{Keywords: Nondeterministic Finite Automata, Unambiguous Finite Automata, Upper Bounds on Runtime, Conditional Lower Bounds, Languages over the Unary Alphabet}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.17
Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities

Authors: Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
When a transportation service accommodates both people and goods, operators sometimes opt for vehicles that can be dynamically reconfigured for different demands. Motivated by air service in remote communities in Canada’s north, we define a pickup-and-delivery problem in which aircraft can add or remove seats during a multi-stop trip to accommodate varying demands. Given the demand for people and cargo as well as a seat inventory at each location, the problem consists in finding a tour that picks up and delivers all demand while potentially reconfiguring the vehicle capacity at each location by adding or removing seats. We develop a total of six models using three different approaches: constraint programming, mixed integer programming, and domain-independent dynamic programming. Our numerical experiments indicate that domain-independent dynamic programming is able to substantially outperform the other technologies on both solution quality and run-time on a set of randomly generated instances spanning the size of real problems in northern Canada.
Cite as

Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck. Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golestanian_et_al:LIPIcs.CP.2023.17,
  author =	{Golestanian, Arnoosh and Bianco, Giovanni Lo and Tao, Chengyu and Beck, J. Christopher},
  title =	{{Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.17},
  URN =		{urn:nbn:de:0030-drops-190542},
  doi =		{10.4230/LIPIcs.CP.2023.17},
  annote =	{Keywords: Pickup and delivery, Dial-a-ride problem, Optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.23
Large Neighborhood Beam Search for Domain-Independent Dynamic Programming

Authors: Ryo Kuroiwa and J. Christopher Beck

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Large neighborhood search (LNS) is an algorithmic framework that removes a part of a solution and performs search in the induced search space to find a better solution. While LNS shows strong performance in constraint programming, little work has combined LNS with state space search. We propose large neighborhood beam search (LNBS), a combination of LNS and state space search. Given a solution path, LNBS removes a partial path between two states and then performs beam search to find a better partial path. We apply LNBS to domain-independent dynamic programming (DIDP), a recently proposed generic framework for combinatorial optimization based on dynamic programming. We empirically show that LNBS finds better quality solutions than a state-of-the-art DIDP solver in five out of nine benchmark problem types with a total of 8570 problem instances. In particular, LNBS shows a significant improvement over the existing state-of-the-art DIDP solver in routing and scheduling problems.
Cite as

Ryo Kuroiwa and J. Christopher Beck. Large Neighborhood Beam Search for Domain-Independent Dynamic Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kuroiwa_et_al:LIPIcs.CP.2023.23,
  author =	{Kuroiwa, Ryo and Beck, J. Christopher},
  title =	{{Large Neighborhood Beam Search for Domain-Independent Dynamic Programming}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.23},
  URN =		{urn:nbn:de:0030-drops-190605},
  doi =		{10.4230/LIPIcs.CP.2023.23},
  annote =	{Keywords: Large Neighborhood Search, Dynamic Programming, State Space Search, Combinatorial Optimization}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2023.42
Predict-Then-Optimise Strategies for Water Flow Control (Short Paper)

Authors: Vincent Barbosa Vaz, James Bailey, Christopher Leckie, and Peter J. Stuckey

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
A pressure sewer system is a network of pump stations used to collect and manage sewage from individual properties that cannot be directly connected to the gravity driven sewer network due to the topography of the terrain. We consider a common scenario for a pressure sewer system, where individual sites collect sewage in a local tank, and then pump it into the gravity fed sewage network. Standard control systems simply wait until the local tank reaches (near) capacity and begin pumping out. Unfortunately such simple control usually leads to peaks in sewage flow in the morning and evening, corresponding to peak water usage in the properties. High peak flows require equalization basins or overflow systems, or larger capacity sewage treatment plants. In this paper we investigate combining prediction and optimisation to better manage peak sewage flows. We use simple prediction methods to generate realistic possible future scenarios, and then develop optimisation models to generate pumping plans that try to smooth out flows into the network. The solutions of these models create a policy for pumping out that is specialized to individual properties and which overall is able to substantially reduce peak flows.
Cite as

Vincent Barbosa Vaz, James Bailey, Christopher Leckie, and Peter J. Stuckey. Predict-Then-Optimise Strategies for Water Flow Control (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{barbosavaz_et_al:LIPIcs.CP.2023.42,
  author =	{Barbosa Vaz, Vincent and Bailey, James and Leckie, Christopher and J. Stuckey, Peter},
  title =	{{Predict-Then-Optimise Strategies for Water Flow Control}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{42:1--42:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.42},
  URN =		{urn:nbn:de:0030-drops-190795},
  doi =		{10.4230/LIPIcs.CP.2023.42},
  annote =	{Keywords: Water Flow Control, Optimization, Machine Learning}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.103
Efficient Block Approximate Matrix Multiplication

Authors: Chuhan Yang and Christopher Musco

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Randomized matrix algorithms have had significant recent impact on numerical linear algebra. One especially powerful class of methods are algorithms for approximate matrix multiplication based on sampling. Such methods typically sample individual matrix rows and columns using carefully chosen importance sampling probabilities. However, due to practical considerations like memory locality and the preservation of matrix structure, it is often preferable to sample contiguous blocks of rows and columns all together. Recently, (Wu, 2018) addressed this setting by developing an approximate matrix multiplication method based on block sampling. However, the method is inefficient, as it requires knowledge of optimal importance sampling probabilities that are expensive to compute. We address this issue by showing that the method of Wu can be accelerated through the use of a randomized implicit trace estimation method. Doing so allows us to provably reduce the cost of sampling to near-linear in the size of the matrices being multiplied, without impacting the accuracy of the final approximate matrix multiplication. Overall, this yields a fast practical algorithm, which we test on a number of synthetic and real-world data sets. We complement our algorithmic contribution with the first extensive empirical comparison of block algorithms for randomized matrix multiplication. Our method offers a significant runtime advantage over the method of (Wu, 2018) and also outperforms basic uniform sampling of blocks. However, we find another recent method of (Charalambides, 2021) which uses sub-optimal but efficiently computable sampling probabilities often (but not always) offers the best trade-off between speed and accuracy.
Cite as

Chuhan Yang and Christopher Musco. Efficient Block Approximate Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 103:1-103:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.ESA.2023.103,
  author =	{Yang, Chuhan and Musco, Christopher},
  title =	{{Efficient Block Approximate Matrix Multiplication}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{103:1--103:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.103},
  URN =		{urn:nbn:de:0030-drops-187562},
  doi =		{10.4230/LIPIcs.ESA.2023.103},
  annote =	{Keywords: Approximate matrix multiplication, randomized numerical linear algebra, trace estimation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.80
Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work

Authors: Jonas Schmidt and Thomas Schwentick

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

Abstract
The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and 𝒪(n^{1/2+ε}) work on the CRCW PRAM model. The work of these algorithms almost matches the work of the 𝒪(log n) time algorithm for connectivity by Kopelowitz et al. (2018) on the EREW PRAM model and the time of the sequential algorithm for bipartiteness by Eppstein et al. (1997). In particular, we show that the sparsification technique, which has been used in both mentioned papers, can in principle also be used for constant time algorithms in the CRCW PRAM model, despite the logarithmic depth of sparsification trees.
Cite as

Jonas Schmidt and Thomas Schwentick. Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 80:1-80:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:LIPIcs.MFCS.2023.80,
  author =	{Schmidt, Jonas and Schwentick, Thomas},
  title =	{{Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{80:1--80:15},
  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.80},
  URN =		{urn:nbn:de:0030-drops-186140},
  doi =		{10.4230/LIPIcs.MFCS.2023.80},
  annote =	{Keywords: Dynamic parallel algorithms, Undirected connectivity, Bipartiteness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.81
On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages

Authors: Jonas Schmidt, Thomas Schwentick, and Jennifer Todtenhoefer

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

Abstract
Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the goal to minimise work (or, equivalently, the number of processors). In fact, their inspection yields the work bounds 𝒪(n²) and 𝒪(n⁷) per change operation, respectively. In this paper, dynamic algorithms for regular tree languages are proposed that generalise the previous algorithms in that they allow unbounded node rank and leaf insertions, while improving the work bound from 𝒪(n²) to 𝒪(n^ε), for arbitrary ε > 0. For context-free languages, algorithms with better work bounds (compared with 𝒪(n⁷)) for restricted classes are proposed: for every ε > 0 there are such algorithms for deterministic context-free languages with work bound 𝒪(n^{3+ε}) and for visibly pushdown languages with work bound 𝒪(n^{2+ε}).
Cite as

Jonas Schmidt, Thomas Schwentick, and Jennifer Todtenhoefer. On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:LIPIcs.MFCS.2023.81,
  author =	{Schmidt, Jonas and Schwentick, Thomas and Todtenhoefer, Jennifer},
  title =	{{On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{81:1--81:15},
  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.81},
  URN =		{urn:nbn:de:0030-drops-186152},
  doi =		{10.4230/LIPIcs.MFCS.2023.81},
  annote =	{Keywords: Dynamic complexity, work, parallel constant time}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.ITP.2023.36
Fermat’s Last Theorem for Regular Primes (Short Paper)

Authors: Alex J. Best, Christopher Birkbeck, Riccardo Brasca, and Eric Rodriguez Boidi

Published in: LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023)

Abstract
We formalise the proof of the first case of Fermat’s Last Theorem for regular primes using the Lean theorem prover and its mathematical library mathlib. This is an important 19th century result that motivated the development of modern algebraic number theory. Besides explaining the mathematics behind this result, we analyze in this paper the difficulties we faced in the formalisation process and how we solved them. For example, we had to deal with a diamond about characteristic zero fields and problems arising from multiple nested coercions related to number fields. We also explain how we integrated our work to mathlib.
Cite as

Alex J. Best, Christopher Birkbeck, Riccardo Brasca, and Eric Rodriguez Boidi. Fermat’s Last Theorem for Regular Primes (Short Paper). In 14th International Conference on Interactive Theorem Proving (ITP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 268, pp. 36:1-36:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{best_et_al:LIPIcs.ITP.2023.36,
  author =	{Best, Alex J. and Birkbeck, Christopher and Brasca, Riccardo and Rodriguez Boidi, Eric},
  title =	{{Fermat’s Last Theorem for Regular Primes}},
  booktitle =	{14th International Conference on Interactive Theorem Proving (ITP 2023)},
  pages =	{36:1--36:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-284-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{268},
  editor =	{Naumowicz, Adam and Thiemann, Ren\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.36},
  URN =		{urn:nbn:de:0030-drops-184115},
  doi =		{10.4230/LIPIcs.ITP.2023.36},
  annote =	{Keywords: Fermat’s Last Theorem, Cyclotomic fields, Interactive theorem proving, Lean}
}
Document
DOI: 10.4230/OASIcs.WCET.2023.8
Analyzing the Stability of Relative Performance Differences Between Cloud and Embedded Environments

Authors: Rumen Rumenov Kolev and Christopher Helpa

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)

Abstract
There has been a shift towards the software-defined vehicle in the automotive industry in recent years. In order to enable the correct behaviour of critical as well as non-critical software functions, like those found in Autonomous Driving/Driver Assistance subsystems, extensive software testing needs to be performed. The usage of embedded hardware for these tests is either very expensive or takes a prohibitively long time in relation to the fast development cycles in the industry. To reduce development bottlenecks, test frameworks executed in cloud environments that leverage the scalability of the cloud are an essential part of the development process. However, relying on more performant cloud hardware for the majority of tests means that performance problems will only become apparent in later development phases when software is deployed to the real target. However, if the performance relation between executing in the cloud and on the embedded target can be approximated with sufficient precision, the expressiveness of the executed tests can be improved. Moreover, as a fully integrated system consists of a large number of software components that, at any given time, exhibit an unknown mix of best-/average-/worst-case behaviour, it is critical to know whether the performance relation differs depending on the inputs. In this paper, we examine the relative performance differences between a physical ARM-based chipset and a cloud-based ARM-based virtual machine, using a generic benchmark and 2 algorithms representative of typical automotive workloads, modified to generate best-/average-/worst-case behaviour in a reproducible and controlled way and assess the performance differences. We determine that the performance difference factor is between 1.8 and 3.6 for synthetic benchmarks and around 2.0-2.8 for more representative benchmarks. These results indicate that it may be possible to relate cloud to embedded performance with acceptable precision, especially when workload characterization is taken into account.
Cite as

Rumen Rumenov Kolev and Christopher Helpa. Analyzing the Stability of Relative Performance Differences Between Cloud and Embedded Environments. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kolev_et_al:OASIcs.WCET.2023.8,
  author =	{Kolev, Rumen Rumenov and Helpa, Christopher},
  title =	{{Analyzing the Stability of Relative Performance Differences Between Cloud and Embedded Environments}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{8:1--8:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.8},
  URN =		{urn:nbn:de:0030-drops-184373},
  doi =		{10.4230/OASIcs.WCET.2023.8},
  annote =	{Keywords: Performance Benchmarking, Performance Factor Stability, Software Development, Cloud Computing, WCET}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.1
Engineering a Preprocessor for Symmetry Detection

Authors: Markus Anders, Pascal Schweitzer, and Julian Stieß

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
State-of-the-art solvers for symmetry detection in combinatorial objects are becoming increasingly sophisticated software libraries. Most of the solvers were initially designed with inputs from combinatorics in mind (nauty, bliss, Traces, dejavu). They excel at dealing with a complicated core of the input. Others focus on practical instances that exhibit sparsity. They excel at dealing with comparatively easy but extremely large substructures of the input (saucy). In practice, these differences manifest in significantly diverging performances on different types of graph classes. We engineer a preprocessor for symmetry detection. The result is a tool designed to shrink sparse, large substructures of the input graph. On most of the practical instances, the preprocessor improves the overall running time significantly for many of the state-of-the-art solvers. At the same time, our benchmarks show that the additional overhead is negligible. Overall we obtain single algorithms with competitive performance across all benchmark graphs. As such, the preprocessor bridges the disparity between solvers that focus on combinatorial graphs and large practical graphs. In fact, on most of the practical instances the combined setup significantly outperforms previous state-of-the-art.
Cite as

Markus Anders, Pascal Schweitzer, and Julian Stieß. Engineering a Preprocessor for Symmetry Detection. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{anders_et_al:LIPIcs.SEA.2023.1,
  author =	{Anders, Markus and Schweitzer, Pascal and Stie{\ss}, Julian},
  title =	{{Engineering a Preprocessor for Symmetry Detection}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.1},
  URN =		{urn:nbn:de:0030-drops-183511},
  doi =		{10.4230/LIPIcs.SEA.2023.1},
  annote =	{Keywords: graph isomorphism, automorphism groups, symmetry detection, preprocessors}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.21
Sublinear Time Eigenvalue Approximation via Random Sampling

Authors: Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco, and Archan Ray

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the problem of approximating the eigenspectrum of a symmetric matrix A ∈ ℝ^{n×n} with bounded entries (i.e., ‖A‖_∞ ≤ 1). We present a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error ±εn using those of a randomly sampled Õ((log³ n)/ε³)×Õ((log³ n)/ε³) principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of ± ε √{nnz(A)} and ±ε‖A‖_F when the rows of A can be sampled with probabilities proportional to their sparsities or their squared 𝓁₂ norms respectively. Here nnz(A) is the number of non-zero entries in A and ‖A‖_F is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of A. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.
Cite as

Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco, and Archan Ray. Sublinear Time Eigenvalue Approximation via Random Sampling. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.ICALP.2023.21,
  author =	{Bhattacharjee, Rajarshi and Dexter, Gregory and Drineas, Petros and Musco, Cameron and Ray, Archan},
  title =	{{Sublinear Time Eigenvalue Approximation via Random Sampling}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.21},
  URN =		{urn:nbn:de:0030-drops-180733},
  doi =		{10.4230/LIPIcs.ICALP.2023.21},
  annote =	{Keywords: sublinear algorithms, eigenvalue approximation, randomized linear algebra}
}
  • Refine by Author
  • 8 Umans, Christopher
  • 6 Schwentick, Thomas
  • 6 Thierauf, Thomas
  • 6 Weyand, Christopher
  • 5 Bläsius, Thomas
  • Show More...

  • Refine by Classification
  • 5 Computing methodologies → Machine learning
  • 5 Mathematics of computing → Graph algorithms
  • 3 Computing methodologies → Natural language processing
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Sketching and sampling
  • Show More...

  • Refine by Keyword
  • 7 Intrusion detection and prevention
  • 7 attack response and countermeasures
  • 7 automated security
  • 7 denial of service detection and response
  • 7 event correlation
  • Show More...

  • Refine by Type
  • 179 document

  • Refine by Publication Year
  • 42 2010
  • 22 2018
  • 18 2023
  • 15 2022
  • 14 2021
  • 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