Zobrazeno 1 - 10
of 58
pro vyhledávání: '"Capelli, Florent"'
Autor:
Amarilli, Antoine, Capelli, Florent
This work reviews how database theory uses tractable circuit classes from knowledge compilation. We present relevant query evaluation tasks, and notions of tractable circuits. We then show how these tractable circuits can be used to address database
Externí odkaz:
http://arxiv.org/abs/2407.01127
The Binary Polynomial Optimization (BPO) problem is defined as the problem of maximizing a given polynomial function over all binary points. The main contribution of this paper is to draw a novel connection between BPO and the problem of finding the
Externí odkaz:
http://arxiv.org/abs/2311.00149
Autor:
Capelli, Florent, Irwin, Oliver
Given a conjunctive query $Q$ and a database $\mathbf{D}$, a direct access to the answers of $Q$ over $\mathbf{D}$ is the operation of returning, given an index $j$, the $j^{\mathsf{th}}$ answer for some order on its answers. While this problem is $\
Externí odkaz:
http://arxiv.org/abs/2310.15800
We study the problem of enumerating the satisfying assignments for circuit classes from knowledge compilation, where assignments are ranked in a specific order. In particular, we show how this problem can be used to efficiently perform ranked enumera
Externí odkaz:
http://arxiv.org/abs/2310.00731
Publikováno v:
Logical Methods in Computer Science, Volume 20, Issue 1 (January 26, 2024) lmcs:10232
In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying linear programs whose constraints and objective functions depend on the
Externí odkaz:
http://arxiv.org/abs/2210.16694
Autor:
Capelli, Florent, Strozecki, Yann
The quality of enumeration algorithms is often measured by their delay, that is, the maximal time spent between the output of two distinct solutions. If the goal is to enumerate $t$ distinct solutions for any given $t$, then another relevant measure
Externí odkaz:
http://arxiv.org/abs/2108.10208
Autor:
Capelli, Florent
In this paper, we study proof systems in the sense of Cook-Reckhow for problems that are higher in the polynomial hierarchy than coNP, in particular, #SAT and maxSAT. We start by explaining how the notion of Cook-Reckhow proof systems can be apply to
Externí odkaz:
http://arxiv.org/abs/1903.04039
A typical workflow for solving a linear programming problem is to first write a linear program parametrized by the data in a language such as Math GNU Prog or AMPL then call the solver on this program while providing the data. When the data is extrac
Externí odkaz:
http://arxiv.org/abs/1901.03633
The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings su
Externí odkaz:
http://arxiv.org/abs/1811.02944
Autor:
Capelli, Florent, Strozecki, Yann
Publikováno v:
Discrete Applied Mathematics, Volume 303, 2021, Pages 203-215
In this article, we study the problem of enumerating the models of DNF formulas. The aim is to provide enumeration algorithms with a delay that depends polynomially on the size of each model and not on the size of the formula, which can be exponentia
Externí odkaz:
http://arxiv.org/abs/1810.04006