22 Search Results for "K�hnberger, Kai-Uwe"


Document
Structural Operational Semantics for Heterogeneously Typed Coalgebras

Authors: Harald König, Uwe Wolter, and Tim Kräuter

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)


Abstract
Concurrently interacting components of a modular software architecture are heterogeneously structured behavioural models. We consider them as coalgebras based on different endofunctors. We formalize the composition of these coalgebras as specially tailored segments of distributive laws of the bialgebraic approach of Turi and Plotkin. The resulting categorical rules for structural operational semantics involve many-sorted algebraic specifications, which leads to a description of the components together with the composed system as a single holistic behavioural system. We evaluate our approach by showing that observational equivalence is a congruence with respect to the algebraic composition operation.

Cite as

Harald König, Uwe Wolter, and Tim Kräuter. Structural Operational Semantics for Heterogeneously Typed Coalgebras. In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{konig_et_al:LIPIcs.CALCO.2023.7,
  author =	{K\"{o}nig, Harald and Wolter, Uwe and Kr\"{a}uter, Tim},
  title =	{{Structural Operational Semantics for Heterogeneously Typed Coalgebras}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.7},
  URN =		{urn:nbn:de:0030-drops-188048},
  doi =		{10.4230/LIPIcs.CALCO.2023.7},
  annote =	{Keywords: Coalgebra, Bialgebra, Structural operational semantics, Compositionality}
}
Document
The Cost of Statistical Security in Proofs for Repeated Squaring

Authors: Cody Freitag and Ilan Komargodski

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
In recent years, the number of applications of the repeated squaring assumption has been growing rapidly. The assumption states that, given a group element x, an integer T, and an RSA modulus N, it is hard to compute x^2^T mod N - or even decide whether y?=x^2^T mod N - in parallel time less than the trivial approach of simply computing T squares. This rise has been driven by efficient proof systems for repeated squaring, opening the door to more efficient constructions of verifiable delay functions, various secure computation primitives, and proof systems for more general languages. In this work, we study the complexity of statistically sound proofs for the repeated squaring relation. Technically, we consider proofs where the prover sends at most k ≥ 0 elements and the (probabilistic) verifier performs generic group operations over the group ℤ_N^⋆. As our main contribution, we show that for any (one-round) proof with a randomized verifier (i.e., an MA proof) the verifier either runs in parallel time Ω(T/(k+1)) with high probability, or is able to factor N given the proof provided by the prover. This shows that either the prover essentially sends p,q such that N = p⋅ q (which is infeasible or undesirable in most applications), or a variant of Pietrzak’s proof of repeated squaring (ITCS 2019) has optimal verifier complexity O(T/(k+1)). In particular, it is impossible to obtain a statistically sound one-round proof of repeated squaring with efficiency on par with the computationally-sound protocol of Wesolowski (EUROCRYPT 2019), with a generic group verifier. We further extend our one-round lower bound to a natural class of recursive interactive proofs for repeated squaring. For r-round recursive proofs where the prover is allowed to send k group elements per round, we show that the verifier either runs in parallel time Ω(T/(k+1)^r) with high probability, or is able to factor N given the proof transcript.

Cite as

Cody Freitag and Ilan Komargodski. The Cost of Statistical Security in Proofs for Repeated Squaring. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{freitag_et_al:LIPIcs.ITC.2023.4,
  author =	{Freitag, Cody and Komargodski, Ilan},
  title =	{{The Cost of Statistical Security in Proofs for Repeated Squaring}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.4},
  URN =		{urn:nbn:de:0030-drops-183326},
  doi =		{10.4230/LIPIcs.ITC.2023.4},
  annote =	{Keywords: Cryptographic Proofs, Repeated Squaring, Lower Bounds}
}
Document
Quantum Security of Subset Cover Problems

Authors: Samuel Bouaziz-Ermann, Alex B. Grilo, and Damien Vergnaud

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
The subset cover problem for k ≥ 1 hash functions, which can be seen as an extension of the collision problem, was introduced in 2002 by Reyzin and Reyzin to analyse the security of their hash-function based signature scheme HORS. The security of many hash-based signature schemes relies on this problem or a variant of this problem (e.g. HORS, SPHINCS, SPHINCS+, ...). Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset cover problem, called restricted subset cover, and proposed a quantum algorithm for this problem. In this work, we prove that any quantum algorithm needs to make Ω((k+1)^{-(2^k)/(2^{k+1}-1})⋅ N^{(2^{k}-1})/(2^{k+1}-1)}) queries to the underlying hash functions with codomain size N to solve the restricted subset cover problem, which essentially matches the query complexity of the algorithm proposed by Yuan, Tibouchi and Abe. We also analyze the security of the general (r,k)-subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a r-chosen message attack (for r ≥ 1). We prove that a generic quantum algorithm needs to make Ω(N^{k/5}) queries to the underlying hash functions to find a (1,k)-subset cover. We also propose a quantum algorithm that finds a (r,k)-subset cover making O (N^{k/(2+2r)}) queries to the k hash functions.

Cite as

Samuel Bouaziz-Ermann, Alex B. Grilo, and Damien Vergnaud. Quantum Security of Subset Cover Problems. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bouazizermann_et_al:LIPIcs.ITC.2023.9,
  author =	{Bouaziz-Ermann, Samuel and Grilo, Alex B. and Vergnaud, Damien},
  title =	{{Quantum Security of Subset Cover Problems}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.9},
  URN =		{urn:nbn:de:0030-drops-183378},
  doi =		{10.4230/LIPIcs.ITC.2023.9},
  annote =	{Keywords: Cryptography, Random oracle model, Quantum information}
}
Document
Distributed Shuffling in Adversarial Environments

Authors: Kasper Green Larsen, Maciej Obremski, and Mark Simkin

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
We study mix-nets in the context of cryptocurrencies. Here we have many computationally weak shufflers that speak one after another and want to joinlty shuffle a list of ciphertexts (c₁, … , c_n). Each shuffler can only permute k << n ciphertexts at a time. An adversary A can track some of the ciphertexts and adaptively corrupt some of the shufflers. We present a simple protocol for shuffling the list of ciphertexts efficiently. The main technical contribution of this work is to prove that our simple shuffling strategy does indeed provide good anonymity guarantees and at the same time terminates quickly. Our shuffling algorithm provides a strict improvement over the current shuffling strategy in Ethereum’s block proposer elections. Our algorithm is secure against a stronger adversary, provides provable security guarantees, and is comparably in efficiency to the current approach.

Cite as

Kasper Green Larsen, Maciej Obremski, and Mark Simkin. Distributed Shuffling in Adversarial Environments. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{larsen_et_al:LIPIcs.ITC.2023.10,
  author =	{Larsen, Kasper Green and Obremski, Maciej and Simkin, Mark},
  title =	{{Distributed Shuffling in Adversarial Environments}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.10},
  URN =		{urn:nbn:de:0030-drops-183385},
  doi =		{10.4230/LIPIcs.ITC.2023.10},
  annote =	{Keywords: Distributed Computing, Shuffling}
}
Document
MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More

Authors: Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized" by the protocol participants. Orlandi et al. [Orlandi et al., 2022] initiated the study of BC-efficient protocols from simple assumptions in the correlated randomness model and for semi-honest adversaries. In this work, we extend the study of [Orlandi et al., 2022] in two primary directions: (a) to a larger and more general class of functions and (b) to the information-theoretic setting. In particular, we offer semi-honest secure protocols for the useful function classes of abelian programs, "read-k" non-abelian programs, and "read-k" generalized formulas. Our constructions use a novel abstraction, called incremental function secret-sharing (IFSS), that can be instantiated with unconditional security or from one-way functions (with different efficiency trade-offs).

Cite as

Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi. MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{keller_et_al:LIPIcs.ITC.2023.11,
  author =	{Keller, Hannah and Orlandi, Claudio and Paskin-Cherniavsky, Anat and Ravi, Divya},
  title =	{{MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.11},
  URN =		{urn:nbn:de:0030-drops-183391},
  doi =		{10.4230/LIPIcs.ITC.2023.11},
  annote =	{Keywords: Secure Multiparty Computation, Bottleneck Complexity, Information-theoretic}
}
Document
Secure Communication in Dynamic Incomplete Networks

Authors: Ivan Damgård, Divya Ravi, Daniel Tschudi, and Sophia Yakoubov

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
In this paper, we explore the feasibility of reliable and private communication in dynamic networks, where in each round the adversary can choose which direct peer-to-peer links are available in the network graph, under the sole condition that the graph is k-connected at each round (for some k). We show that reliable communication is possible in such a dynamic network if and only if k > 2t. We also show that if k = cn > 2 t for a constant c, we can achieve reliable communication with polynomial round and communication complexity. For unconditionally private communication, we show that for a passive adversary, k > t is sufficient (and clearly necessary). For an active adversary, we show that k > 2t is sufficient for statistical security (and clearly necessary), while k > 3t is sufficient for perfect security. We conjecture that, in contrast to the static case, k > 2t is not enough for perfect security, and we give evidence that the conjecture is true. Once we have reliable and private communication between each pair of parties, we can emulate a complete network with secure channels, and we can use known protocols to do secure computation.

Cite as

Ivan Damgård, Divya Ravi, Daniel Tschudi, and Sophia Yakoubov. Secure Communication in Dynamic Incomplete Networks. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2023.13,
  author =	{Damg\r{a}rd, Ivan and Ravi, Divya and Tschudi, Daniel and Yakoubov, Sophia},
  title =	{{Secure Communication in Dynamic Incomplete Networks}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.13},
  URN =		{urn:nbn:de:0030-drops-183419},
  doi =		{10.4230/LIPIcs.ITC.2023.13},
  annote =	{Keywords: Secure Communication, Dynamic Incomplete Network, Information-theoretic}
}
Document
Locally Covert Learning

Authors: Justin Holmgren and Ruta Jawale

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
The goal of a covert learning algorithm is to learn a function f by querying it, while ensuring that an adversary, who sees all queries and their responses, is unable to (efficiently) learn any more about f than they could learn from random input-output pairs. We focus on a relaxation that we call local covertness, in which queries are distributed across k servers and we only limit what is learnable by k - 1 colluding servers. For any constant k, we give a locally covert algorithm for efficiently learning any Fourier-sparse function (technically, our notion of learning is improper, agnostic, and with respect to the uniform distribution). Our result holds unconditionally and for computationally unbounded adversaries. Prior to our work, such an algorithm was known only for the special case of O(log n)-juntas, and only with k = 2 servers [Yuval Ishai et al., 2019]. Our main technical observation is that the original Goldreich-Levin algorithm only utilizes i.i.d. pairs of correlated queries, where each half of every pair is uniformly random. We give a simple generalization of this algorithm in which pairs are replaced by k-tuples in which any k - 1 components are jointly uniform. The cost of this generalization is that the number of queries needed grows exponentially with k.

Cite as

Justin Holmgren and Ruta Jawale. Locally Covert Learning. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{holmgren_et_al:LIPIcs.ITC.2023.14,
  author =	{Holmgren, Justin and Jawale, Ruta},
  title =	{{Locally Covert Learning}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.14},
  URN =		{urn:nbn:de:0030-drops-183421},
  doi =		{10.4230/LIPIcs.ITC.2023.14},
  annote =	{Keywords: learning theory, adversarial machine learning, zero knowledge, Fourier analysis of boolean functions, Goldreich-Levin algorithm, Kushilevitz-Mansour algorithm}
}
Document
Lower Bounds for Secret-Sharing Schemes for k-Hypergraphs

Authors: Amos Beimel

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
A secret-sharing scheme enables a dealer, holding a secret string, to distribute shares to parties such that only pre-defined authorized subsets of parties can reconstruct the secret. The collection of authorized sets is called an access structure. There is a huge gap between the best known upper bounds on the share size of a secret-sharing scheme realizing an arbitrary access structure and the best known lower bounds on the size of these shares. For an arbitrary n-party access structure, the best known upper bound on the share size is 2^{O(n)}. On the other hand, the best known lower bound on the total share size is much smaller, i.e., Ω(n²/log(n)) [Csirmaz, Studia Sci. Math. Hungar.]. This lower bound was proved more than 25 years ago and no major progress has been made since. In this paper, we study secret-sharing schemes for k-hypergraphs, i.e., for access structures where all minimal authorized sets are of size exactly k (however, unauthorized sets can be larger). We consider the case where k is small, i.e., constant or at most log(n). The trivial upper bound for these access structures is O(n⋅ binom(n-1,k-1)) and this can be slightly improved. If there were efficient secret-sharing schemes for such k-hypergraphs (e.g., 2-hypergraphs or 3-hypergraphs), then we would be able to construct secret-sharing schemes for arbitrary access structures that are better than the best known schemes. Thus, understanding the share size required for k-hypergraphs is important. Prior to our work, the best known lower bound for these access structures was Ω(n log(n)), which holds already for graphs (i.e., 2-hypergraphs). We improve this lower bound, proving a lower bound of Ω(n^{2-1/(k-1)}/k) on the total share size for some explicit k-hypergraphs, where 3 ≤ k ≤ log(n). For example, for 3-hypergraphs we prove a lower bound of Ω(n^{3/2}). For log(n)-hypergraphs, we prove a lower bound of Ω(n²/log(n)), i.e., we show that the lower bound of Csirmaz holds already when all minimal authorized sets are of size log(n). Our proof is simple and shows that the lower bound of Csirmaz holds for a simple variant of the access structure considered by Csirmaz. Using our results, we prove a near quadratic separation between the required share size for realizing an explicit access structure and the monotone circuit size describing the access structure, i.e., the share size in Ω(n²/log(n)) and the monotone circuit size is O(nlog(n)) (where the circuit has depth 3).

Cite as

Amos Beimel. Lower Bounds for Secret-Sharing Schemes for k-Hypergraphs. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{beimel:LIPIcs.ITC.2023.16,
  author =	{Beimel, Amos},
  title =	{{Lower Bounds for Secret-Sharing Schemes for k-Hypergraphs}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.16},
  URN =		{urn:nbn:de:0030-drops-183440},
  doi =		{10.4230/LIPIcs.ITC.2023.16},
  annote =	{Keywords: Secret Sharing, Share Size, Lower Bounds, Monotone Circuits}
}
Document
A Generalization of Self-Improving Algorithms

Authors: Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances x₁,⋯,x_n follow some unknown product distribution. That is, x_i comes from a fixed unknown distribution 𝒟_i, and the x_i’s are drawn independently. After spending O(n^{1+ε}) time in a learning phase, the subsequent expected running time is O((n+ H)/ε), where H ∈ {H_S,H_DT}, and H_S and H_DT are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the x_i’s under the group product distribution. There is a hidden partition of [1,n] into groups; the x_i’s in the k-th group are fixed unknown functions of the same hidden variable u_k; and the u_k’s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map u_k to x_i’s are well-behaved. After an O(poly(n))-time training phase, we achieve O(n + H_S) and O(nα(n) + H_DT) expected running times for sorting and DT, respectively, where α(⋅) is the inverse Ackermann function.

Cite as

Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong. A Generalization of Self-Improving Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.29,
  author =	{Cheng, Siu-Wing and Chiu, Man-Kwun and Jin, Kai and Wong, Man Ting},
  title =	{{A Generalization of Self-Improving Algorithms}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.29},
  URN =		{urn:nbn:de:0030-drops-121873},
  doi =		{10.4230/LIPIcs.SoCG.2020.29},
  annote =	{Keywords: expected running time, entropy, sorting, Delaunay triangulation}
}
Document
Being Van Kampen in Presheaf Topoi is a Uniqueness Property

Authors: Harald König and Uwe Wolter

Published in: LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)


Abstract
Fibred semantics is the foundation of the model-instance pattern of software engineering. Software models can often be formalized as objects of presheaf topoi, e.g. the category of directed graphs. Multimodeling requires to construct colimits of diagrams of single models and their instances, while decomposition of instances of the multimodel is given by pullback. Compositionality requires an exact interplay of these operations, i.e., the diagrams must enjoy the Van Kampen property. However, checking the validity of the Van Kampen property algorithmically based on its definition is often impossible. In this paper we state a necessary and sufficient yet easily checkable condition for the Van Kampen property to hold for diagrams in presheaf topoi. It is based on a uniqueness property of path-like structures within the defining congruence classes that make up the colimiting cocone of the models. We thus add to the statement "Being Van Kampen is a Universal Property" by Heindel and Sobocinski presented at CALCO 2009 the fact that the Van Kampen property reveals a set-based structural uniqueness feature.

Cite as

Harald König and Uwe Wolter. Being Van Kampen in Presheaf Topoi is a Uniqueness Property. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{konig_et_al:LIPIcs.CALCO.2017.16,
  author =	{K\"{o}nig, Harald and Wolter, Uwe},
  title =	{{Being Van Kampen in Presheaf Topoi is a Uniqueness Property}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Bonchi, Filippo and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.16},
  URN =		{urn:nbn:de:0030-drops-80320},
  doi =		{10.4230/LIPIcs.CALCO.2017.16},
  annote =	{Keywords: Van Kampen Cocone, Presheaf Topos, Fibred Semantics, Mapping Path}
}
Document
k-Bounded Petri Net Synthesis from Modal Transition Systems

Authors: Uli Schlachter and Harro Wimmel

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


Abstract
We present a goal-oriented algorithm that can synthesise k-bounded Petri nets (k in N^+) from hyper modal transition systems (hMTS), an extension of labelled transition systems with optional and required behaviour. The algorithm builds a potential reachability graph of a Petri net from scratch, extending it stepwise with required behaviour from the given MTS and over-approximating the result to a new valid reachability graph. Termination occurs if either the MTS yields no additional requirements or the resulting net of the second step shows a conflict with the behaviour allowed by the MTS, making it non-sythesisable.

Cite as

Uli Schlachter and Harro Wimmel. k-Bounded Petri Net Synthesis from Modal Transition Systems. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{schlachter_et_al:LIPIcs.CONCUR.2017.6,
  author =	{Schlachter, Uli and Wimmel, Harro},
  title =	{{k-Bounded Petri Net Synthesis from Modal Transition Systems}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.6},
  URN =		{urn:nbn:de:0030-drops-77802},
  doi =		{10.4230/LIPIcs.CONCUR.2017.6},
  annote =	{Keywords: Modal transition system, bounded Petri net, synthesis}
}
Document
Space-Time Trade-Offs for the Shortest Unique Substring Problem

Authors: Arnab Ganguly, Wing-Kai Hon, Rahul Shah, and Sharma V. Thankachan

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)


Abstract
Given a string X[1, n] and a position k in [1, n], the Shortest Unique Substring of X covering k, denoted by S_k, is a substring X[i, j] of X which satisfies the following conditions: (i) i leq k leq j, (ii) i is the only position where there is an occurrence of X[i, j], and (iii) j - i is minimized. The best-known algorithm [Hon et al., ISAAC 2015] can find S k for all k in [1, n] in time O(n) using the string X and additional 2n words of working space. Let tau be a given parameter. We present the following new results. For any given k in [1, n], we can compute S_k via a deterministic algorithm in O(n tau^2 log n tau) time using X and additional O(n/tau) words of working space. For every k in [1, n], we can compute S_k via a deterministic algorithm in O(n tau^2 log n/tau) time using X and additional O(n/tau) words and 4n + o(n) bits of working space. For both problems above, we present an O(n tau log^{c+1} n)-time randomized algorithm that uses n/ log c n words in addition to that mentioned above, where c geq 0 is an arbitrary constant. In this case, the reported string is unique and covers k, but with probability at most n^{-O(1)} , may not be the shortest. As a consequence of our techniques, we also obtain similar space-and-time tradeoffs for a related problem of finding Maximal Unique Matches of two strings [Delcher et al., Nucleic Acids Res. 1999].

Cite as

Arnab Ganguly, Wing-Kai Hon, Rahul Shah, and Sharma V. Thankachan. Space-Time Trade-Offs for the Shortest Unique Substring Problem. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{ganguly_et_al:LIPIcs.ISAAC.2016.34,
  author =	{Ganguly, Arnab and Hon, Wing-Kai and Shah, Rahul and Thankachan, Sharma V.},
  title =	{{Space-Time Trade-Offs for the Shortest Unique Substring Problem}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.34},
  URN =		{urn:nbn:de:0030-drops-68041},
  doi =		{10.4230/LIPIcs.ISAAC.2016.34},
  annote =	{Keywords: Suffix Tree, Sparsification, Rabin-Karp Fingerprint, Probabilistic z-Fast Trie, Succinct Data-Structures}
}
Document
Parallel Repetition for Entangled k-player Games via Fast Quantum Search

Authors: Kai-Min Chung, Xiaodi Wu, and Henry Yuen

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
We present two parallel repetition theorems for the entangled value of multi-player, one-round free games (games where the inputs come from a product distribution). Our first theorem shows that for a k-player free game G with entangled value val^*(G) = 1 - epsilon, the n-fold repetition of G has entangled value val^*(G^(\otimes n)) at most (1 - epsilon^(3/2))^(Omega(n/sk^4)), where s is the answer length of any player. In contrast, the best known parallel repetition theorem for the classical value of two-player free games is val(G^(\otimes n)) <= (1 - epsilon^2)^(Omega(n/s)), due to Barak, et al. (RANDOM 2009). This suggests the possibility of a separation between the behavior of entangled and classical free games under parallel repetition. Our second theorem handles the broader class of free games G where the players can output (possibly entangled) quantum states. For such games, the repeated entangled value is upper bounded by (1 - epsilon^2)^(Omega(n/sk^2)). We also show that the dependence of the exponent on k is necessary: we exhibit a k-player free game G and n >= 1 such that val^*(G^(\otimes n)) >= val^*(G)^(n/k). Our analysis exploits the novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa (ICALP 2014). We demonstrate that better communication protocols yield better parallel repetition theorems: in particular, our first theorem crucially uses a quantum search protocol by Aaronson and Ambainis, which gives a quadratic Grover speed-up for distributed search problems. Finally, our results apply to a broader class of games than were previously considered before; in particular, we obtain the first parallel repetition theorem for entangled games involving more than two players, and for games involving quantum outputs.

Cite as

Kai-Min Chung, Xiaodi Wu, and Henry Yuen. Parallel Repetition for Entangled k-player Games via Fast Quantum Search. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 512-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.CCC.2015.512,
  author =	{Chung, Kai-Min and Wu, Xiaodi and Yuen, Henry},
  title =	{{Parallel Repetition for Entangled k-player Games via Fast Quantum Search}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{512--536},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.512},
  URN =		{urn:nbn:de:0030-drops-50727},
  doi =		{10.4230/LIPIcs.CCC.2015.512},
  annote =	{Keywords: Parallel repetition, quantum entanglement, communication complexity}
}
Document
Cognitive Approaches for the Semantic Web (Dagstuhl Seminar 12221)

Authors: Dedre Gentner, Frank van Harmelen, Pascal Hitzler, Krzysztof Janowicz, and Kai-Uwe Kühnberger

Published in: Dagstuhl Reports, Volume 2, Issue 5 (2012)


Abstract
A major focus in the design of Semantic Web ontology languages used to be on finding a suitable balance between the expressivity of the language and the tractability of reasoning services defined over this language. This focus mirrors the original vision of a Web composed of machine readable and understandable data. Similarly to the classical Web a few years ago, the attention is recently shifting towards a user-centric vision of the Semantic Web. Essentially, the information stored on the Web is from and for humans. This new focus is not only reflected in the fast growing Linked Data Web but also in the increasing influence of research from cognitive science, human computer interaction, and machine-learning. Cognitive aspects emerge as an essential ingredient for future work on knowledge acquisition, representation, reasoning, and interactions on the Semantic Web. Visual interfaces have to support semantic-based retrieval and at the same time hide the complexity of the underlying reasoning machinery from the user. Analogical and similarity-based reasoning should assist users in browsing and navigating through the rapidly increasing amount of information. Instead of pre-defined conceptualizations of the world, the selection and conceptualization of relevant information has to be tailored to the user's context on-the-fly. This involves work on ontology modularization and context-awareness, but also approaches from ecological psychology such as affordance theory which also plays an increasing role in robotics and AI. During the Dagstuhl Seminar 12221 we discussed the most promising ways to move forward on the vision of bringing findings from cognitive science to the Semantic Web, and to create synergies between the different areas of research. While the seminar focused on the use of cognitive engineering for a user-centric Semantic Web, it also discussed the reverse direction, i.e., how can the Semantic Web work on knowledge representation and reasoning feed back to the cognitive science community.

Cite as

Dedre Gentner, Frank van Harmelen, Pascal Hitzler, Krzysztof Janowicz, and Kai-Uwe Kühnberger. Cognitive Approaches for the Semantic Web (Dagstuhl Seminar 12221). In Dagstuhl Reports, Volume 2, Issue 5, pp. 93-116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Article{gentner_et_al:DagRep.2.5.93,
  author =	{Gentner, Dedre and van Harmelen, Frank and Hitzler, Pascal and Janowicz, Krzysztof and K\"{u}hnberger, Kai-Uwe},
  title =	{{Cognitive Approaches for the Semantic Web (Dagstuhl Seminar 12221)}},
  pages =	{93--116},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{5},
  editor =	{Gentner, Dedre and van Harmelen, Frank and Hitzler, Pascal and Janowicz, Krzysztof and K\"{u}hnberger, Kai-Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.5.93},
  URN =		{urn:nbn:de:0030-drops-37115},
  doi =		{10.4230/DagRep.2.5.93},
  annote =	{Keywords: Cognitive methods, Semantic Web, Analogy and similarity-based reasoning, Semantic heterogeneity and context, Symbol grounding, Emerging semantics, Comonsense reasoning}
}
Document
10381 Summary and Abstracts Collection – Robust Query Processing

Authors: Götz Graefe, Arnd Christian König, Harumi Anne Kuno, Volker Markl, and Kai-Uwe Sattler

Published in: Dagstuhl Seminar Proceedings, Volume 10381, Robust Query Processing (2011)


Abstract
Dagstuhl seminar 10381 on robust query processing (held 19.09.10 - 24.09.10) brought together a diverse set of researchers and practitioners with a broad range of expertise for the purpose of fostering discussion and collaboration regarding causes, opportunities, and solutions for achieving robust query processing. The seminar strove to build a unified view across the loosely-coupled system components responsible for the various stages of database query processing. Participants were chosen for their experience with database query processing and, where possible, their prior work in academic research or in product development towards robustness in database query processing. In order to pave the way to motivate, measure, and protect future advances in robust query processing, seminar 10381 focused on developing tests for measuring the robustness of query processing. In these proceedings, we first review the seminar topics, goals, and results, then present abstracts or notes of some of the seminar break-out sessions. We also include, as an appendix, the robust query processing reading list that was collected and distributed to participants before the seminar began, as well as summaries of a few of those papers that were contributed by some participants.

Cite as

Götz Graefe, Arnd Christian König, Harumi Anne Kuno, Volker Markl, and Kai-Uwe Sattler. 10381 Summary and Abstracts Collection – Robust Query Processing. In Robust Query Processing. Dagstuhl Seminar Proceedings, Volume 10381, pp. 1-64, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{graefe_et_al:DagSemProc.10381.1,
  author =	{Graefe, G\"{o}tz and K\"{o}nig, Arnd Christian and Kuno, Harumi Anne and Markl, Volker and Sattler, Kai-Uwe},
  title =	{{10381 Summary and Abstracts Collection – Robust Query Processing}},
  booktitle =	{Robust Query Processing},
  pages =	{1--64},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10381},
  editor =	{Goetz Graefe and Arnd Christian K\"{o}nig and Harumi Anne Kuno and Volker Markl and Kai-Uwe Sattler},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10381.1},
  URN =		{urn:nbn:de:0030-drops-29846},
  doi =		{10.4230/DagSemProc.10381.1},
  annote =	{Keywords: Robust query processing, adaptive query optimization, query execution, indexing, workload management, reliability, application availability}
}
  • Refine by Author
  • 3 Sattler, Kai-Uwe
  • 2 Chung, Kai-Min
  • 2 König, Harald
  • 2 Kühnberger, Kai-Uwe
  • 2 Ravi, Divya
  • Show More...

  • Refine by Classification
  • 2 Security and privacy → Information-theoretic techniques
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Cryptographic primitives
  • Show More...

  • Refine by Keyword
  • 2 Information-theoretic
  • 2 Lower Bounds
  • 1 Analogy and similarity-based reasoning
  • 1 Bialgebra
  • 1 Bottleneck Complexity
  • Show More...

  • Refine by Type
  • 22 document

  • Refine by Publication Year
  • 8 2023
  • 2 2009
  • 2 2017
  • 1 2003
  • 1 2005
  • 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