32 Search Results for "Krause, Matthias"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.39
Consumable Data via Quantum Communication

Authors: Dar Gilboa, Siddhartha Jain, and Jarrod R. McClean

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

Abstract
Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data x and Bob holds m inputs y_1, …, y_m. They want to compute m instances of a bipartite relation R(⋅,⋅) on every pair (x, y_1), …, (x, y_m). We call this the asymmetric direct sum question for one-way communication. We give examples where the quantum communication complexity of such problems scales polynomially with m, while the classical communication complexity depends at most logarithmically on m. Thus, for such problems, data behaves like a consumable resource that is effectively destroyed upon use when the owner stores and transmits it as quantum states, but not when transmitted classically. We show an application to a strategic data-selling game, and discuss other potential economic implications.
Cite as

Dar Gilboa, Siddhartha Jain, and Jarrod R. McClean. Consumable Data via Quantum Communication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gilboa_et_al:LIPIcs.APPROX/RANDOM.2025.39,
  author =	{Gilboa, Dar and Jain, Siddhartha and McClean, Jarrod R.},
  title =	{{Consumable Data via Quantum Communication}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{39:1--39:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.39},
  URN =		{urn:nbn:de:0030-drops-244059},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.39},
  annote =	{Keywords: quantum communication, one-time programs, data markets}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2025.5
Integrating Questions About Learners’ Code in an Automated Assessment System

Authors: Afonso B. Caniço and André L. Santos

Published in: OASIcs, Volume 133, 6th International Computer Programming Education Conference (ICPEC 2025)

Abstract
Questions about Learners' Code (QLCs) assess programming students' program comprehension skills by providing personalised questions targeting the students' own program code. We conducted a preliminary, experimental implementation of integrating QLCs in the Automated Assessment System (AAS) used in an introductory programming course using Java. QLCs targeted some of the code assignments which students had to complete during the course. We collected 889 answers to QLCs, answered by 13 students over five course modules. We found that as the complexity of exercises increases, the success rate of the same type of QLC may not improve, and even exhibit a decline over time. We further analysed incorrect answers individually to relate them to possible misconceptions.
Cite as

Afonso B. Caniço and André L. Santos. Integrating Questions About Learners’ Code in an Automated Assessment System. In 6th International Computer Programming Education Conference (ICPEC 2025). Open Access Series in Informatics (OASIcs), Volume 133, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canico_et_al:OASIcs.ICPEC.2025.5,
  author =	{Cani\c{c}o, Afonso B. and Santos, Andr\'{e} L.},
  title =	{{Integrating Questions About Learners’ Code in an Automated Assessment System}},
  booktitle =	{6th International Computer Programming Education Conference (ICPEC 2025)},
  pages =	{5:1--5:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-393-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{133},
  editor =	{Queir\'{o}s, Ricardo and Pinto, M\'{a}rio and Portela, Filipe and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2025.5},
  URN =		{urn:nbn:de:0030-drops-240353},
  doi =		{10.4230/OASIcs.ICPEC.2025.5},
  annote =	{Keywords: programming education, student assessment, program comprehension, questions about learners’ code}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.6
Vantage Point Selection Algorithms for Bottleneck Capacity Estimation

Authors: Vikrant Ashvinkumar, Rezaul Chowdhury, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph G = (V, E) whose edges E have unknown capacity values that are to be discovered. Probes from a vantage point, i.e, a vertex v ∈ V, along shortest paths from v to all other vertices, reveal bottleneck edge capacities along each path. Our goal is to select k vantage points from V that reveal the maximum number of bottleneck edge capacities. We consider both a non-adaptive setting where all k vantage points are selected before any bottleneck capacity is revealed, and an adaptive setting where each vantage point selection instantly reveals bottleneck capacities along all shortest paths starting from that point. In the non-adaptive setting, by considering a relaxed model where edge capacities are drawn from a random permutation (which still leaves the problem of maximizing the expected number of revealed edges NP-hard), we are able to give a 1-1/e approximate algorithm. In the adaptive setting we work with the least permissive model where edge capacities are arbitrarily fixed but unknown. We compare with the best solution for the particular input instance (i.e. by enumerating all choices of k tuples), and provide both lower bounds on instance optimal approximation algorithms and upper bounds for trees and planar graphs.
Cite as

Vikrant Ashvinkumar, Rezaul Chowdhury, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk. Vantage Point Selection Algorithms for Bottleneck Capacity Estimation. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ashvinkumar_et_al:LIPIcs.WADS.2025.6,
  author =	{Ashvinkumar, Vikrant and Chowdhury, Rezaul and Gao, Jie and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{Vantage Point Selection Algorithms for Bottleneck Capacity Estimation}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.6},
  URN =		{urn:nbn:de:0030-drops-242376},
  doi =		{10.4230/LIPIcs.WADS.2025.6},
  annote =	{Keywords: Bottleneck capacity, Approximation algorithms, Instance optimality}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.12
Online Knapsack Problems with Estimates

Authors: Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ± δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.
Cite as

Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker. Online Knapsack Problems with Estimates. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.12,
  author =	{Balab\'{a}n, Jakub and Gehnen, Matthias and Lotze, Henri and Seesemann, Finn and Stocker, Moritz},
  title =	{{Online Knapsack Problems with Estimates}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.12},
  URN =		{urn:nbn:de:0030-drops-241190},
  doi =		{10.4230/LIPIcs.MFCS.2025.12},
  annote =	{Keywords: Knapsack, Online Knapsack, Removability, Estimate, Prediction}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.32
Efficient Certified Reasoning for Binarized Neural Networks

Authors: Jiong Yang, Yong Kiam Tan, Mate Soos, Magnus O. Myreen, and Kuldeep S. Meel

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Neural networks have emerged as essential components in safety-critical applications - these use cases demand complex, yet trustworthy computations. Binarized Neural Networks (BNNs) are a type of neural network where each neuron is constrained to a Boolean value; they are particularly well-suited for safety-critical tasks because they retain much of the computational capacities of full-scale (floating-point or quantized) deep neural networks, but remain compatible with satisfiability solvers for qualitative verification and with model counters for quantitative reasoning. However, existing methods for BNN analysis suffer from either limited scalability or susceptibility to soundness errors, which hinders their applicability in real-world scenarios. In this work, we present a scalable and trustworthy approach for both qualitative and quantitative verification of BNNs. Our approach introduces a native representation of BNN constraints in a custom-designed solver for qualitative reasoning, and in an approximate model counter for quantitative reasoning. We further develop specialized proof generation and checking pipelines with native support for BNN constraint reasoning, ensuring trustworthiness for all of our verification results. Empirical evaluations on a BNN robustness verification benchmark suite demonstrate that our certified solving approach achieves a 9× speedup over prior certified CNF and PB-based approaches, and our certified counting approach achieves a 218× speedup over the existing CNF-based baseline. In terms of coverage, our pipeline produces fully certified results for 99% and 86% of the qualitative and quantitative reasoning queries on BNNs, respectively. This is in sharp contrast to the best existing baselines which can fully certify only 62% and 4% of the queries, respectively.
Cite as

Jiong Yang, Yong Kiam Tan, Mate Soos, Magnus O. Myreen, and Kuldeep S. Meel. Efficient Certified Reasoning for Binarized Neural Networks. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.SAT.2025.32,
  author =	{Yang, Jiong and Tan, Yong Kiam and Soos, Mate and Myreen, Magnus O. and Meel, Kuldeep S.},
  title =	{{Efficient Certified Reasoning for Binarized Neural Networks}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.32},
  URN =		{urn:nbn:de:0030-drops-237665},
  doi =		{10.4230/LIPIcs.SAT.2025.32},
  annote =	{Keywords: Neural network verification, proof certification, SAT solving, approximate model counting}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.3
Sparsity Lower Bounds for Probabilistic Polynomials

Authors: Josh Alman, Arkadev Chattopadhyay, and Ryan Williams

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

Abstract
Probabilistic polynomials over commutative rings offer a powerful way of representing Boolean functions. Although many degree lower bounds for such representations have been proved, sparsity lower bounds (counting the number of monomials in the polynomials) have not been so common. Sparsity upper bounds are of great interest for potential algorithmic applications, since sparse probabilistic polynomials are the key technical tool behind the best known algorithms for many core problems, including dense All-Pairs Shortest Paths, and the existence of sparser polynomials would lead to breakthrough algorithms for these problems. In this paper, we prove several strong lower bounds on the sparsity of probabilistic and approximate polynomials computing Boolean functions when 0 means "false". Our main result is that the AND of n ORs of c log n variables requires probabilistic polynomials (over any commutative ring which isn't too large) of sparsity n^Ω(log c) to achieve even 1/4 error. The lower bound is tight, and it rules out a large class of polynomial-method approaches for refuting the APSP and SETH conjectures via matrix multiplication. Our other results include: - Every probabilistic polynomial (over a commutative ring) for the disjointness function on two n-bit vectors requires exponential sparsity in order to achieve exponentially low error. - A generic lower bound that any function requiring probabilistic polynomials of degree d must require probabilistic polynomials of sparsity Ω(2^d). - Building on earlier work, we consider the probabilistic rank of Boolean functions which generalizes the notion of sparsity for probabilistic polynomials, and prove separations of probabilistic rank and probabilistic sparsity. Some of our results and lemmas are basis independent. For example, over any basis {a,b} for true and false where a ≠ b, and any commutative ring R, the AND function on n variables has no probabilistic R-polynomial with 2^o(n) sparsity, o(n) degree, and 1/2^o(n) error simultaneously. This AND lower bound is our main technical lemma used in the above lower bounds.
Cite as

Josh Alman, Arkadev Chattopadhyay, and Ryan Williams. Sparsity Lower Bounds for Probabilistic Polynomials. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 3:1-3:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alman_et_al:LIPIcs.ITCS.2025.3,
  author =	{Alman, Josh and Chattopadhyay, Arkadev and Williams, Ryan},
  title =	{{Sparsity Lower Bounds for Probabilistic Polynomials}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{3:1--3:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.3},
  URN =		{urn:nbn:de:0030-drops-226316},
  doi =		{10.4230/LIPIcs.ITCS.2025.3},
  annote =	{Keywords: Probabilistic Polynomials, Sparsity, Orthogonal Vectors, Probabilistic Rank}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.8
Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges

Authors: Claudia d'Amato, Louis Mahon, Pierre Monnin, and Giorgos Stamou

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
The graph model is nowadays largely adopted to model a wide range of knowledge and data, spanning from social networks to knowledge graphs (KGs), representing a successful paradigm of how symbolic and transparent AI can scale on the World Wide Web. However, due to their unprecedented volume, they are generally tackled by Machine Learning (ML) and mostly numeric based methods such as graph embedding models (KGE) and deep neural networks (DNNs). The latter methods have been proved lately very efficient, leading the current AI spring. In this vision paper, we introduce some of the main existing methods for combining KGs and ML, divided into two categories: those using ML to improve KGs, and those using KGs to improve results on ML tasks. From this introduction, we highlight research gaps and perspectives that we deem promising and currently under-explored for the involved research communities, spanning from KG support for LLM prompting, integration of KG semantics in ML models to symbol-based methods, interpretability of ML models, and the need for improved benchmark datasets. In our opinion, such perspectives are stepping stones in an ultimate view of KGs as central assets for neuro-symbolic and explainable AI.
Cite as

Claudia d'Amato, Louis Mahon, Pierre Monnin, and Giorgos Stamou. Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 8:1-8:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{damato_et_al:TGDK.1.1.8,
  author =	{d'Amato, Claudia and Mahon, Louis and Monnin, Pierre and Stamou, Giorgos},
  title =	{{Machine Learning and Knowledge Graphs: Existing Gaps and Future Research Challenges}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{8:1--8:35},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.8},
  URN =		{urn:nbn:de:0030-drops-194824},
  doi =		{10.4230/TGDK.1.1.8},
  annote =	{Keywords: Graph-based Learning, Knowledge Graph Embeddings, Large Language Models, Explainable AI, Knowledge Graph Completion \& Curation}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.4
Knowledge Graph Embeddings: Open Challenges and Opportunities

Authors: Russa Biswas, Lucie-Aimée Kaffee, Michael Cochez, Stefania Dumbrava, Theis E. Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Mencía, Heiko Paulheim, Harald Sack, Edlira Kalemi Vakaj, and Gerard de Melo

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
While Knowledge Graphs (KGs) have long been used as valuable sources of structured knowledge, in recent years, KG embeddings have become a popular way of deriving numeric vector representations from them, for instance, to support knowledge graph completion and similarity search. This study surveys advances as well as open challenges and opportunities in this area. For instance, the most prominent embedding models focus primarily on structural information. However, there has been notable progress in incorporating further aspects, such as semantics, multi-modal, temporal, and multilingual features. Most embedding techniques are assessed using human-curated benchmark datasets for the task of link prediction, neglecting other important real-world KG applications. Many approaches assume a static knowledge graph and are unable to account for dynamic changes. Additionally, KG embeddings may encode data biases and lack interpretability. Overall, this study provides an overview of promising research avenues to learn improved KG embeddings that can address a more diverse range of use cases.
Cite as

Russa Biswas, Lucie-Aimée Kaffee, Michael Cochez, Stefania Dumbrava, Theis E. Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Mencía, Heiko Paulheim, Harald Sack, Edlira Kalemi Vakaj, and Gerard de Melo. Knowledge Graph Embeddings: Open Challenges and Opportunities. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 4:1-4:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{biswas_et_al:TGDK.1.1.4,
  author =	{Biswas, Russa and Kaffee, Lucie-Aim\'{e}e and Cochez, Michael and Dumbrava, Stefania and Jendal, Theis E. and Lissandrini, Matteo and Lopez, Vanessa and Menc{\'\i}a, Eneldo Loza and Paulheim, Heiko and Sack, Harald and Vakaj, Edlira Kalemi and de Melo, Gerard},
  title =	{{Knowledge Graph Embeddings: Open Challenges and Opportunities}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:32},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.4},
  URN =		{urn:nbn:de:0030-drops-194783},
  doi =		{10.4230/TGDK.1.1.4},
  annote =	{Keywords: Knowledge Graphs, KG embeddings, Link prediction, KG applications}
}
Document
DOI: 10.4230/DagSemProc.09031.3
Algebraic Attacks against Linear RFID Authentication Protocols

Authors: Matthias Krause and Dirk Stegemann

Published in: Dagstuhl Seminar Proceedings, Volume 9031, Symmetric Cryptography (2009)

Abstract
The limited computational resources available on RFID tags imply a need for specially designed authentication protocols. The light weight authentication protocol $extsf{HB}^+$ proposed by Juels and Weis seems currently secure for several RFID applications, but is too slow for many practical settings. As a possible alternative, authentication protocols based on choosing random elements from $L$ secret linear $n$-dimensional subspaces of $GF(2)^{n+k}$ (so called linear $(n,k,L)$-protocols), have been considered. We show that to a certain extent, these protocols are vulnerable to algebraic attacks. Particularly, our approach allows to break Cicho'{n}, Klonowski and Kutyl owski's $ extsf{CKK}^2$-protocol, a special linear $(n,k,2)$-protocol, for practically recommended parameters in less than a second on a standard PC. Moreover, we show that even unrestricted $(n,k,L)$-protocols can be efficiently broken if $L$ is too small.
Cite as

Matthias Krause and Dirk Stegemann. Algebraic Attacks against Linear RFID Authentication Protocols. In Symmetric Cryptography. Dagstuhl Seminar Proceedings, Volume 9031, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.09031.3,
  author =	{Krause, Matthias and Stegemann, Dirk},
  title =	{{Algebraic Attacks against Linear RFID Authentication Protocols}},
  booktitle =	{Symmetric Cryptography},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9031},
  editor =	{Helena Handschuh and Stefan Lucks and Bart Preneel and Phillip Rogaway},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09031.3},
  URN =		{urn:nbn:de:0030-drops-19576},
  doi =		{10.4230/DagSemProc.09031.3},
  annote =	{Keywords: RFID Authentication, HB+, CKK, CKK2}
}
Document
DOI: 10.4230/DagSemProc.06111.2
06111 Executive Summary – Complexity of Boolean Functions

Authors: Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We briefly describe the state of the art concerning the complexity of discrete functions. Computational models and analytical techniques are summarized. After describing the formal organization of the Dagstuhl seminar "Complexity of Boolean Functions" held in March 2006, we introduce the different topics that have been discussed there and mention some of the major achievements. The summary closes with an outlook on the development of discrete computational complexity in the future.
Cite as

Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk. 06111 Executive Summary – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.2,
  author =	{Krause, Matthias and van Melkebeek, Dieter and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger},
  title =	{{06111 Executive Summary – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.2},
  URN =		{urn:nbn:de:0030-drops-8409},
  doi =		{10.4230/DagSemProc.06111.2},
  annote =	{Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning}
}
Document
DOI: 10.4230/DagSemProc.06111.1
06111 Abstracts Collection – Complexity of Boolean Functions

Authors: Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
From 12.03.06 to 17.03.06, the Dagstuhl Seminar 06111 ``Complexity of Boolean Functions'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. 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

Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek. 06111 Abstracts Collection – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.1,
  author =	{Krause, Matthias and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger and van Melkebeek, Dieter},
  title =	{{06111 Abstracts Collection – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.1},
  URN =		{urn:nbn:de:0030-drops-7593},
  doi =		{10.4230/DagSemProc.06111.1},
  annote =	{Keywords: Complexity of Boolean functions, Boolean circuits, binary decision diagrams, lower bound proof techniques, combinatorics of Boolean functions, communi algorithmic learning, cryptography, derandomization}
}
Document
DOI: 10.4230/DagSemProc.06111.6
Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space

Authors: Andreas Jakoby and Till Tantau

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
Series-parallel graphs, which are built by repeatedly applying series or parallel composition operations to paths, play an important role in computer science as they model the flow of information in many types of programs. For directed series-parallel graphs, we study the problem of finding a shortest path between two given vertices. Our main result is that we can find such a path in logarithmic space, which shows that the distance problem for series-parallel graphs is L-complete. Previously, it was known that one can compute some path in logarithmic space; but for other graph types, like undirected graphs or tournament graphs, constructing some path between given vertices is possible in logarithmic space while constructing a shortest path is NL-complete.
Cite as

Andreas Jakoby and Till Tantau. Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{jakoby_et_al:DagSemProc.06111.6,
  author =	{Jakoby, Andreas and Tantau, Till},
  title =	{{Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.6},
  URN =		{urn:nbn:de:0030-drops-6185},
  doi =		{10.4230/DagSemProc.06111.6},
  annote =	{Keywords: Series-parallel graphs, shortest path, logspace}
}
Document
DOI: 10.4230/DagSemProc.06111.8
Graphs and Circuits: Some Further Remarks

Authors: Stasys Jukna

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We consider the power of single level circuits in the context of graph complexity. We first prove that the single level conjecture fails for fanin-$2$ circuits over the basis ${oplus,land,1}$. This shows that the (surpisingly tight) phenomenon, established by Mirwald and Schnorr (1992) for quadratic functions, has no analogon for graphs. We then show that the single level conjecture fails for unbounded fanin circuits over ${lor,land,1}$. This partially answers the question of Pudl'ak, R"odl and Savick'y (1986). We also prove that $Sigma_2 eq Pi_2$ in a restricted version of the hierarhy of communication complexity classes introduced by Babai, Frankl and Simon (1986). Further, we show that even depth-$2$ circuits are surprisingly powerful: every bipartite $n imes n$ graph of maximum degree $Delta$ can be represented by a monotone CNF with $O(Deltalog n)$ clauses. We also discuss a relation between graphs and $ACC$-circuits.
Cite as

Stasys Jukna. Graphs and Circuits: Some Further Remarks. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{jukna:DagSemProc.06111.8,
  author =	{Jukna, Stasys},
  title =	{{Graphs and Circuits: Some Further Remarks}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.8},
  URN =		{urn:nbn:de:0030-drops-6218},
  doi =		{10.4230/DagSemProc.06111.8},
  annote =	{Keywords: Graph complexity, single level conjecture, Sylvester graphs, communication complexity, ACC-circuits}
}
Document
DOI: 10.4230/DagSemProc.06111.10
Incremental branching programs

Authors: Anna Gál, Pierre McKenzie, and Michal Koucký

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We propose a new model of restricted branching programs which we call {em incremental branching programs}. We show that {em syntactic} incremental branching programs capture previously studied structured models of computation for the problem GEN, namely marking machines [Cook74]. and Poon's extension [Poon93] of jumping automata on graphs [CookRackoff80]. We then prove exponential size lower bounds for our syntactic incremental model, and for some other restricted branching program models as well. We further show that nondeterministic syntactic incremental branching programs are provably stronger than their deterministic counterpart when solving a natural NL-complete GEN subproblem. It remains open if syntactic incremental branching programs are as powerful as unrestricted branching programs for GEN problems. Joint work with Anna Gál and Michal Koucký
Cite as

Anna Gál, Pierre McKenzie, and Michal Koucký. Incremental branching programs. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:DagSemProc.06111.10,
  author =	{G\'{a}l, Anna and McKenzie, Pierre and Kouck\'{y}, Michal},
  title =	{{Incremental branching programs}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.10},
  URN =		{urn:nbn:de:0030-drops-6230},
  doi =		{10.4230/DagSemProc.06111.10},
  annote =	{Keywords: Complexity theory, branching programs, logarithmic space, marking machines}
}
Document
DOI: 10.4230/DagSemProc.06111.11
On Probabilistic Time versus Alternating Time

Authors: Emanuele Viola

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
Sipser and Gács, and independently Lautemann, proved in '83 that probabilistic polynomial time is contained in the second level of the polynomial-time hierarchy, i.e. BPP is in Sigma_2 P. This is essentially the only non-trivial upper bound that we have on the power of probabilistic computation. More precisely, the Sipser-Gács-Lautemann simulation shows that probabilistic time can be simulated deterministically, using two quantifiers, **with a quadratic blow-up in the running time**. That is, BPTime(t) is contained in Sigma_2 Time(t^2). In this talk we discuss whether this quadratic blow-up in the running time is necessary. We show that the quadratic blow-up is indeed necessary for black-box simulations that use two quantifiers, such as those of Sipser, Gács, and Lautemann. To obtain this result, we prove a new circuit lower bound for computing **approximate majority**, i.e. computing the majority of a given bit-string whose fraction of 1's is bounded away from 1/2 (by a constant): We show that small depth-3 circuits for approximate majority must have bottom fan-in Omega(log n). On the positive side, we obtain that probabilistic time can be simulated deterministically, using three quantifiers, in quasilinear time. That is, BPTime(t) is contained in Sigma_3 Time(t polylog t). Along the way, we show that approximate majority can be computed by uniform polynomial-size depth-3 circuits. This is a uniform version of a striking result by Ajtai that gives *non-uniform* polynomial-size depth-3 circuits for approximate majority. If time permits, we will discuss some applications of our results to proving lower bounds on randomized Turing machines.
Cite as

Emanuele Viola. On Probabilistic Time versus Alternating Time. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{viola:DagSemProc.06111.11,
  author =	{Viola, Emanuele},
  title =	{{On Probabilistic Time versus Alternating Time}},
  booktitle =	{Complexity of Boolean Functions},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.11},
  URN =		{urn:nbn:de:0030-drops-6194},
  doi =		{10.4230/DagSemProc.06111.11},
  annote =	{Keywords: Probabilistic time, alternating time, polynomial-time hierarchy, approximate majority, constant-depth circuit}
}
  • Refine by Type
  • 32 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 6 2025
  • 2 2023
  • 1 2009
  • 22 2006
  • 1 2002

  • Refine by Author
  • 4 Krause, Matthias
  • 4 van Melkebeek, Dieter
  • 3 Gál, Anna
  • 3 Reischuk, Rüdiger
  • 2 Andreev, Alexander E.
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 OASIcs
  • 2 TGDK
  • 1 DagSemRep
  • 23 DagSemProc

  • Refine by Classification
  • 2 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Machine learning approaches
  • 1 Computing methodologies → Neural networks
  • 1 Computing methodologies → Semantic networks
  • 1 Information systems → World Wide Web
  • Show More...

  • Refine by Keyword
  • 4 lower bounds
  • 2 communication complexity
  • 2 cryptography
  • 2 derandomization
  • 2 polynomial-time hierarchy
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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