31 Search Results for "L�bbecke, Marco"

Document
DOI: 10.4230/LIPIcs.FSCD.2023.18
For the Metatheory of Type Theory, Internal Sconing Is Enough

Authors: Rafaël Bocquet, Ambrus Kaposi, and Christian Sattler

Published in: LIPIcs, Volume 260, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)

Abstract
Metatheorems about type theories are often proven by interpreting the syntax into models constructed using categorical gluing. We propose to use only sconing (gluing along a global section functor) instead of general gluing. The sconing is performed internally to a presheaf category, and we recover the original glued model by externalization. Our method relies on constructions involving two notions of models: first-order models (with explicit contexts) and higher-order models (without explicit contexts). Sconing turns a displayed higher-order model into a displayed first-order model. Using these, we derive specialized induction principles for the syntax of type theory. The input of such an induction principle is a boilerplate-free description of its motives and methods, not mentioning contexts. The output is a section with computation rules specified in the same internal language. We illustrate our framework by proofs of canonicity and normalization for type theory.
Cite as

Rafaël Bocquet, Ambrus Kaposi, and Christian Sattler. For the Metatheory of Type Theory, Internal Sconing Is Enough. In 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 260, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bocquet_et_al:LIPIcs.FSCD.2023.18,
  author =	{Bocquet, Rafa\"{e}l and Kaposi, Ambrus and Sattler, Christian},
  title =	{{For the Metatheory of Type Theory, Internal Sconing Is Enough}},
  booktitle =	{8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-277-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{260},
  editor =	{Gaboardi, Marco and van Raamsdonk, Femke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2023.18},
  URN =		{urn:nbn:de:0030-drops-180029},
  doi =		{10.4230/LIPIcs.FSCD.2023.18},
  annote =	{Keywords: type theory, presheaves, canonicity, normalization, sconing, gluing}
}
Document
DOI: 10.4230/LIPIcs.FORC.2022.1
Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling

Authors: Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan, and Jayshree Sarathy

Published in: LIPIcs, Volume 218, 3rd Symposium on Foundations of Responsible Computing (FORC 2022)

Abstract
Sampling schemes are fundamental tools in statistics, survey design, and algorithm design. A fundamental result in differential privacy is that a differentially private mechanism run on a simple random sample of a population provides stronger privacy guarantees than the same algorithm run on the entire population. However, in practice, sampling designs are often more complex than the simple, data-independent sampling schemes that are addressed in prior work. In this work, we extend the study of privacy amplification results to more complex, data-dependent sampling schemes. We find that not only do these sampling schemes often fail to amplify privacy, they can actually result in privacy degradation. We analyze the privacy implications of the pervasive cluster sampling and stratified sampling paradigms, as well as provide some insight into the study of more general sampling designs.
Cite as

Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan, and Jayshree Sarathy. Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.FORC.2022.1,
  author =	{Bun, Mark and Drechsler, J\"{o}rg and Gaboardi, Marco and McMillan, Audra and Sarathy, Jayshree},
  title =	{{Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling}},
  booktitle =	{3rd Symposium on Foundations of Responsible Computing (FORC 2022)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-226-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{218},
  editor =	{Celis, L. Elisa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2022.1},
  URN =		{urn:nbn:de:0030-drops-165243},
  doi =		{10.4230/LIPIcs.FORC.2022.1},
  annote =	{Keywords: privacy, differential privacy, survey design, survey sampling}
}
Document
DOI: 10.4230/OASIcs.Microservices.2017-2019.4
Introduction to Microservice API Patterns (MAP)

Authors: Olaf Zimmermann, Mirko Stocker, Daniel Lübke, Cesare Pautasso, and Uwe Zdun

Published in: OASIcs, Volume 78, Joint Post-proceedings of the First and Second International Conference on Microservices (Microservices 2017/2019)

Abstract
The Microservice API Patterns (MAP) language and supporting website premiered under this name at Microservices 2019. MAP distills proven, platform- and technology-independent solutions to recurring (micro-)service design and interface specification problems such as finding well-fitting service granularities, rightsizing message representations, and managing the evolution of APIs and their implementations. In this paper, we motivate the need for such a pattern language, outline the language organization and present two exemplary patterns describing alternative options for representing nested data. We also identify future research and development directions.
Cite as

Olaf Zimmermann, Mirko Stocker, Daniel Lübke, Cesare Pautasso, and Uwe Zdun. Introduction to Microservice API Patterns (MAP). In Joint Post-proceedings of the First and Second International Conference on Microservices (Microservices 2017/2019). Open Access Series in Informatics (OASIcs), Volume 78, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zimmermann_et_al:OASIcs.Microservices.2017-2019.4,
  author =	{Zimmermann, Olaf and Stocker, Mirko and L\"{u}bke, Daniel and Pautasso, Cesare and Zdun, Uwe},
  title =	{{Introduction to Microservice API Patterns (MAP)}},
  booktitle =	{Joint Post-proceedings of the First and Second International Conference on Microservices (Microservices 2017/2019)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-137-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{78},
  editor =	{Cruz-Filipe, Lu{\'\i}s and Giallorenzo, Saverio and Montesi, Fabrizio and Peressotti, Marco and Rademacher, Florian and Sachweh, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Microservices.2017-2019.4},
  URN =		{urn:nbn:de:0030-drops-118268},
  doi =		{10.4230/OASIcs.Microservices.2017-2019.4},
  annote =	{Keywords: application programming interfaces, distributed systems, enterprise application integration, service-oriented computing, software architecture}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2019.23
Partial Order Reduction for Reachability Games

Authors: Frederik Meyer Bønneland, Peter Gjøl Jensen, Kim G. Larsen, Marco Muñiz, and Jiří Srba

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)

Abstract
Partial order reductions have been successfully applied to model checking of concurrent systems and practical applications of the technique show nontrivial reduction in the size of the explored state space. We present a theory of partial order reduction based on stubborn sets in the game-theoretical setting of 2-player games with reachability/safety objectives. Our stubborn reduction allows us to prune the interleaving behaviour of both players in the game, and we formally prove its correctness on the class of games played on general labelled transition systems. We then instantiate the framework to the class of weighted Petri net games with inhibitor arcs and provide its efficient implementation in the model checker TAPAAL. Finally, we evaluate our stubborn reduction on several case studies and demonstrate its efficiency.
Cite as

Frederik Meyer Bønneland, Peter Gjøl Jensen, Kim G. Larsen, Marco Muñiz, and Jiří Srba. Partial Order Reduction for Reachability Games. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bnneland_et_al:LIPIcs.CONCUR.2019.23,
  author =	{B{\o}nneland, Frederik Meyer and Jensen, Peter Gj{\o}l and Larsen, Kim G. and Mu\~{n}iz, Marco and Srba, Ji\v{r}{\'\i}},
  title =	{{Partial Order Reduction for Reachability Games}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.23},
  URN =		{urn:nbn:de:0030-drops-109251},
  doi =		{10.4230/LIPIcs.CONCUR.2019.23},
  annote =	{Keywords: Petri nets, games, synthesis, partial order reduction, stubborn sets}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.15
The First Order Truth Behind Undecidability of Regular Path Queries Determinacy

Authors: Grzegorz Głuch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
In our paper [Głuch, Marcinkowski, Ostropolski-Nalewaja, LICS ACM, 2018] we have solved an old problem stated in [Calvanese, De Giacomo, Lenzerini, Vardi, SPDS ACM, 2000] showing that query determinacy is undecidable for Regular Path Queries. Here a strong generalisation of this result is shown, and - we think - a very unexpected one. We prove that no regularity is needed: determinacy remains undecidable even for finite unions of conjunctive path queries.
Cite as

Grzegorz Głuch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja. The First Order Truth Behind Undecidability of Regular Path Queries Determinacy. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gluch_et_al:LIPIcs.ICDT.2019.15,
  author =	{G{\l}uch, Grzegorz and Marcinkowski, Jerzy and Ostropolski-Nalewaja, Piotr},
  title =	{{The First Order Truth Behind Undecidability of Regular Path Queries Determinacy}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.15},
  URN =		{urn:nbn:de:0030-drops-103175},
  doi =		{10.4230/LIPIcs.ICDT.2019.15},
  annote =	{Keywords: database theory, query, view, determinacy, recursive path queries}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.16
Datalog: Bag Semantics via Set Semantics

Authors: Leopoldo Bertossi, Georg Gottlob, and Reinhard Pichler

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
Duplicates in data management are common and problematic. In this work, we present a translation of Datalog under bag semantics into a well-behaved extension of Datalog, the so-called warded Datalog^+/-, under set semantics. From a theoretical point of view, this allows us to reason on bag semantics by making use of the well-established theoretical foundations of set semantics. From a practical point of view, this allows us to handle the bag semantics of Datalog by powerful, existing query engines for the required extension of Datalog. This use of Datalog^+/- is extended to give a set semantics to duplicates in Datalog^+/- itself. We investigate the properties of the resulting Datalog^+/- programs, the problem of deciding multiplicities, and expressibility of some bag operations. Moreover, the proposed translation has the potential for interesting applications such as to Multiset Relational Algebra and the semantic web query language SPARQL with bag semantics.
Cite as

Leopoldo Bertossi, Georg Gottlob, and Reinhard Pichler. Datalog: Bag Semantics via Set Semantics. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bertossi_et_al:LIPIcs.ICDT.2019.16,
  author =	{Bertossi, Leopoldo and Gottlob, Georg and Pichler, Reinhard},
  title =	{{Datalog: Bag Semantics via Set Semantics}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.16},
  URN =		{urn:nbn:de:0030-drops-103188},
  doi =		{10.4230/LIPIcs.ICDT.2019.16},
  annote =	{Keywords: Datalog, duplicates, multisets, query answering, chase, Datalog+/-}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.18
A Single Approach to Decide Chase Termination on Linear Existential Rules

Authors: Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
Existential rules, long known as tuple-generating dependencies in database theory, have been intensively studied in the last decade as a powerful formalism to represent ontological knowledge in the context of ontology-based query answering. A knowledge base is then composed of an instance that contains incomplete data and a set of existential rules, and answers to queries are logically entailed from the knowledge base. This brought again to light the fundamental chase tool, and its different variants that have been proposed in the literature. It is well-known that the problem of determining, given a chase variant and a set of existential rules, whether the chase will halt on any instance, is undecidable. Hence, a crucial issue is whether it becomes decidable for known subclasses of existential rules. In this work, we consider linear existential rules with atomic head, a simple yet important subclass of existential rules that generalizes inclusion dependencies. We show the decidability of the all-instance chase termination problem on these rules for three main chase variants, namely semi-oblivious, restricted and core chase. To obtain these results, we introduce a novel approach based on so-called derivation trees and a single notion of forbidden pattern. Besides the theoretical interest of a unified approach and new proofs for the semi-oblivious and core chase variants, we provide the first positive decidability results concerning the termination of the restricted chase, proving that chase termination on linear existential rules with atomic head is decidable for both versions of the problem: Does every chase sequence terminate? Does some chase sequence terminate?
Cite as

Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana. A Single Approach to Decide Chase Termination on Linear Existential Rules. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{leclere_et_al:LIPIcs.ICDT.2019.18,
  author =	{Lecl\`{e}re, Michel and Mugnier, Marie-Laure and Thomazo, Micha\"{e}l and Ulliana, Federico},
  title =	{{A Single Approach to Decide Chase Termination on Linear Existential Rules}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.18},
  URN =		{urn:nbn:de:0030-drops-103200},
  doi =		{10.4230/LIPIcs.ICDT.2019.18},
  annote =	{Keywords: Chase, Tuple Generating Dependencies, Existential rules, Decidability}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.23
Consistent Query Answering for Primary Keys in Logspace

Authors: Paraschos Koutris and Jef Wijsen

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In [Koutris and Wijsen, ACM TODS, 2017], the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this paper, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog (with some aggregation operator) or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition.
Cite as

Paraschos Koutris and Jef Wijsen. Consistent Query Answering for Primary Keys in Logspace. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{koutris_et_al:LIPIcs.ICDT.2019.23,
  author =	{Koutris, Paraschos and Wijsen, Jef},
  title =	{{Consistent Query Answering for Primary Keys in Logspace}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.23},
  URN =		{urn:nbn:de:0030-drops-103252},
  doi =		{10.4230/LIPIcs.ICDT.2019.23},
  annote =	{Keywords: conjunctive queries, consistent query answering, Datalog, primary keys}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.15
Deterministic Blind Radio Networks

Authors: Artur Czumaj and Peter Davies

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Ad-hoc radio networks and multiple access channels are classical and well-studied models of distributed systems, with a large body of literature on deterministic algorithms for fundamental communications primitives such as broadcasting and wake-up. However, almost all of these algorithms assume knowledge of the number of participating nodes and the range of possible IDs, and often make the further assumption that the latter is linear in the former. These are very strong assumptions for models which were designed to capture networks of weak devices organized in an ad-hoc manner. It was believed that without this knowledge, deterministic algorithms must necessarily be much less efficient. In this paper we address this fundamental question and show that this is not the case. We present deterministic algorithms for blind networks (in which nodes know only their own IDs), which match or nearly match the running times of the fastest algorithms which assume network knowledge (and even surpass the previous fastest algorithms which assume parameter knowledge but not small labels). Specifically, in multiple access channels with k participating nodes and IDs up to L, we give a wake-up algorithm requiring O((k log L log k)/(log log k)) time, improving dramatically over the O(L^3 log^3 L) time algorithm of De Marco et al. (2007), and a broadcasting algorithm requiring O(k log L log log k) time, improving over the O(L) time algorithm of Gasieniec et al. (2001) in most circumstances. Furthermore, we show how these same algorithms apply directly to multi-hop radio networks, achieving even larger running time improvements.
Cite as

Artur Czumaj and Peter Davies. Deterministic Blind Radio Networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:LIPIcs.DISC.2018.15,
  author =	{Czumaj, Artur and Davies, Peter},
  title =	{{Deterministic Blind Radio Networks}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.15},
  URN =		{urn:nbn:de:0030-drops-98047},
  doi =		{10.4230/LIPIcs.DISC.2018.15},
  annote =	{Keywords: Broadcasting, Deterministic Algorithms, Radio Networks}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.27
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

Authors: Marco L. Carmosino, Russell Impagliazzo, and Manuel Sabin

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires n^{epsilon k} time, for some constant epsilon>1/2, to count (note that these conjectures are significantly weaker than the usual ones made on these problems) on randomized machines for all but finitely many input lengths, then we have the following derandomizations: - BPP can be decided in polynomial time using only n^alpha random bits on average over any efficient input distribution, for any constant alpha>0 - BPP can be decided in polynomial time with no randomness on average over the uniform distribution This answers an open question of Ball et al. (STOC '17) in the positive of whether derandomization can be achieved from conjectures from fine-grained complexity theory. More strongly, these derandomizations improve over all previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible. Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions about specific problems like k-CLIQUE imply quantitative and qualitative relationships between randomized and deterministic time. This can be either viewed as a barrier to proving some of the main conjectures of fine-grained complexity theory lest we achieve a major breakthrough in unconditional derandomization or, optimistically, as route to attain such derandomizations by working on very concrete and weak conjectures about specific problems.
Cite as

Marco L. Carmosino, Russell Impagliazzo, and Manuel Sabin. Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{carmosino_et_al:LIPIcs.ICALP.2018.27,
  author =	{Carmosino, Marco L. and Impagliazzo, Russell and Sabin, Manuel},
  title =	{{Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.27},
  URN =		{urn:nbn:de:0030-drops-90316},
  doi =		{10.4230/LIPIcs.ICALP.2018.27},
  annote =	{Keywords: Derandomization, Hardness vs Randomness, Fine-Grained Complexity, Average-Case Complexity, k-Orthogonal Vectors, k-CLIQUE}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.11
A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

Authors: Michael Bastubbe, Marco E. Lübbecke, and Jonas T. Witt

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
In Dantzig-Wolfe reformulation of an integer program one convexifies a subset of the constraints, leading to potentially stronger dual bounds from the respective linear programming relaxation. As the subset can be chosen arbitrarily, this includes the trivial cases of convexifying no and all constraints, resulting in a weakest and strongest reformulation, respectively. Our computational study aims at better understanding of what happens in between these extremes. For a collection of integer programs with few constraints we compute, optimally solve, and evaluate the relaxations of all possible (exponentially many) Dantzig-Wolfe reformulations (with mild extensions to larger models from the MIPLIBs). We observe that only a tiny number of different dual bounds actually occur and that only a few inclusion-wise minimal representatives exist for each. This aligns with considerably different impacts of individual constraints on the strengthening the relaxation, some of which have almost no influence. In contrast, types of constraints that are convexified in textbook reformulations have a larger effect. We relate our experiments to what could be called a hierarchy of Dantzig-Wolfe reformulations.
Cite as

Michael Bastubbe, Marco E. Lübbecke, and Jonas T. Witt. A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bastubbe_et_al:LIPIcs.SEA.2018.11,
  author =	{Bastubbe, Michael and L\"{u}bbecke, Marco E. and Witt, Jonas T.},
  title =	{{A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.11},
  URN =		{urn:nbn:de:0030-drops-89464},
  doi =		{10.4230/LIPIcs.SEA.2018.11},
  annote =	{Keywords: Dantzig-Wolfe reformulation, strength of reformulations, Lagrangean relaxation, partial convexification, column generation, hierarchy of relaxations}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.12
Hardness Amplification for Non-Commutative Arithmetic Circuits

Authors: Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire. This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.
Cite as

Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{carmosino_et_al:LIPIcs.CCC.2018.12,
  author =	{Carmosino, Marco L. and Impagliazzo, Russell and Lovett, Shachar and Mihajlin, Ivan},
  title =	{{Hardness Amplification for Non-Commutative Arithmetic Circuits}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.12},
  URN =		{urn:nbn:de:0030-drops-88772},
  doi =		{10.4230/LIPIcs.CCC.2018.12},
  annote =	{Keywords: arithmetic circuits, hardness amplification, circuit lower bounds, non-commutative computation}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.35
Agnostic Learning from Tolerant Natural Proofs

Authors: Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova

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

Abstract
We generalize the "learning algorithms from natural properties" framework of [CIKK16] to get agnostic learning algorithms from natural properties with extra features. We show that if a natural property (in the sense of Razborov and Rudich [RR97]) is useful also against functions that are close to the class of "easy" functions, rather than just against "easy" functions, then it can be used to get an agnostic learning algorithm over the uniform distribution with membership queries. * For AC0[q], any prime q (constant-depth circuits of polynomial size, with AND, OR, NOT, and MODq gates of unbounded fanin), which happens to have a natural property with the requisite extra feature by [Raz87, Smo87, RR97], we obtain the first agnostic learning algorithm for AC0[q], for every prime q. Our algorithm runs in randomized quasi-polynomial time, uses membership queries, and outputs a circuit for a given Boolean function f that agrees with f on all but at most polylog(n)*opt fraction of inputs, where opt is the relative distance between f and the closest function h in the class AC0[q]. * For the ideal case, a natural proof of strongly exponential correlation circuit lower bounds against a circuit class C containing AC0[2] (i.e., circuits of size exp(Omega(n)) cannot compute some n-variate function even with exp(-Omega(n)) advantage over random guessing) would yield a polynomial-time query agnostic learning algorithm for C with the approximation error O(opt).
Cite as

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Agnostic Learning from Tolerant Natural Proofs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{carmosino_et_al:LIPIcs.APPROX-RANDOM.2017.35,
  author =	{Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina},
  title =	{{Agnostic Learning from Tolerant Natural Proofs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{35:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.35},
  URN =		{urn:nbn:de:0030-drops-75842},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.35},
  annote =	{Keywords: agnostic learning, natural proofs, circuit lower bounds, meta-algorithms, AC0\lbrackq\rbrack, Nisan-Wigderson generator}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.10
Learning Algorithms from Natural Proofs

Authors: Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan (1993) gave a quasipolytime learning algorithm for AC^0 (constant-depth circuits with AND, OR, and NOT gates), in the PAC model over the uniform distribution. It was an open question to get a learning algorithm (of any kind) for the class of AC^0[p] circuits (constant-depth, with AND, OR, NOT, and MOD_p gates for a prime p). Our main result is a quasipolytime learning algorithm for AC^0[p] in the PAC model over the uniform distribution with membership queries. This algorithm is an application of a general connection we show to hold between natural proofs (in the sense of Razborov and Rudich (1997)) and learning algorithms. We argue that a natural proof of a circuit lower bound against any (sufficiently powerful) circuit class yields a learning algorithm for the same circuit class. As the lower bounds against AC^0[p] by Razborov (1987) and Smolensky (1987) are natural, we obtain our learning algorithm for AC^0[p].
Cite as

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{carmosino_et_al:LIPIcs.CCC.2016.10,
  author =	{Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina},
  title =	{{Learning Algorithms from Natural Proofs}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.10},
  URN =		{urn:nbn:de:0030-drops-58557},
  doi =		{10.4230/LIPIcs.CCC.2016.10},
  annote =	{Keywords: natural proofs, circuit complexity, lower bounds, learning, compression}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.645
Tighter Connections between Derandomization and Circuit Lower Bounds

Authors: Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova

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

Abstract
We tighten the connections between circuit lower bounds and derandomization for each of the following three types of derandomization: - general derandomization of promiseBPP (connected to Boolean circuits), - derandomization of Polynomial Identity Testing (PIT) over fixed finite fields (connected to arithmetic circuit lower bounds over the same field), and - derandomization of PIT over the integers (connected to arithmetic circuit lower bounds over the integers). We show how to make these connections uniform equivalences, although at the expense of using somewhat less common versions of complexity classes and for a less studied notion of inclusion. Our main results are as follows: 1. We give the first proof that a non-trivial (nondeterministic subexponential-time) algorithm for PIT over a fixed finite field yields arithmetic circuit lower bounds. 2. We get a similar result for the case of PIT over the integers, strengthening a result of Jansen and Santhanam [JS12] (by removing the need for advice). 3. We derive a Boolean circuit lower bound for NEXP intersect coNEXP from the assumption of sufficiently strong non-deterministic derandomization of promiseBPP (without advice), as well as from the assumed existence of an NP-computable non-empty property of Boolean functions useful for proving superpolynomial circuit lower bounds (in the sense of natural proofs of [RR97]); this strengthens the related results of [IKW02]. 4. Finally, we turn all of these implications into equivalences for appropriately defined promise classes and for a notion of robust inclusion/separation (inspired by [FS11]) that lies between the classical "almost everywhere" and "infinitely often" notions.
Cite as

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Tighter Connections between Derandomization and Circuit Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 645-658, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{carmosino_et_al:LIPIcs.APPROX-RANDOM.2015.645,
  author =	{Carmosino, Marco L. and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina},
  title =	{{Tighter Connections between Derandomization and Circuit Lower Bounds}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{645--658},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.645},
  URN =		{urn:nbn:de:0030-drops-53285},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.645},
  annote =	{Keywords: derandomization, circuit lower bounds, polynomial identity testing, promise BPP, hardness vs. randomness}
}
  • Refine by Author
  • 5 Carmosino, Marco L.
  • 5 Impagliazzo, Russell
  • 3 Kabanets, Valentine
  • 3 Kolokolova, Antonina
  • 3 Schöbel, Anita
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Logic
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Information systems → Graph-based database models
  • 1 Information systems → Incomplete data
  • 1 Information systems → Inconsistent data
  • Show More...

  • Refine by Keyword
  • 3 circuit lower bounds
  • 2 Column Generation
  • 2 Datalog
  • 2 Timetabling
  • 2 algorithm engineering
  • Show More...

  • Refine by Type
  • 31 document

  • Refine by Publication Year
  • 14 2010
  • 5 2019
  • 4 2018
  • 1 2009
  • 1 2012
  • 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