Ondřej Čepek
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Ondřej Čepek has a total of 43 co-authors. Here are the top co-authors by number of shared publications:
- Petr Kučera
Charles University
16 shared publications - Endre Boros
MSIS & RUTCOR, Business School, Rutgers University, Piscataway, USA
14 shared publications - Roman Barták
Charles University
11 shared publications - Kristóf Bérczi
MTA-ELTE Matroid Optimization Research Group and HUN-REN–ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University, and HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary
4 shared publications Kazuhisa Makino
3 shared publications- Kazuhisa Makino
Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan
3 shared publications
Latest Publications
- 13 November 2026
- Published by Springer Nature
- p. 171-210
Knowledge Representation Languages and Knowledge Compilation
- 13 November 2026
- Published by Springer Nature
- p. 171-210
Knowledge Representation Languages and Knowledge Compilation
- Open Access
- 1 November 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 22 (1) , 240-249
Boolean Nearest Neighbor Language in the Knowledge Compilation Map
The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turan. A BNN representation of function f is a pair (P,N) of sets of Boolean vectors (called positive and negative prototypes) where f(x) = 1 for every positive prototype x ∈ P, f(x) = 0 for every negative prototype x ∈ N, and the value f(x) for x not in (P ∪ N) is determined by the type of the closest prototype. The main aim of this paper is to determine the position of the BNN language in the Knowledge Compilation Map (KCM). To this end, we settle the complexity status of most standard queries and transformations (those listed in KCM) for BNN inputs. We also compare the succinctness of the BNN language with several languages considered in KCM.
- 1 November 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 22 (1) , 240-249
Open AccessBoolean Nearest Neighbor Language in the Knowledge Compilation Map
The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turan. A BNN representation of function f is a pair (P,N) of sets of Boolean vectors (called positive and negative prototypes) where f(x) = 1 for every positive prototype x ∈ P, f(x) = 0 for every negative prototype x ∈ N, and the value f(x) for x not in (P ∪ N) is determined by the type of the closest prototype. The main aim of this paper is to determine the position of the BNN language in the Knowledge Compilation Map (KCM). To this end, we settle the complexity status of most standard queries and transformations (those listed in KCM) for BNN inputs. We also compare the succinctness of the BNN language with several languages considered in KCM.
- 16 December 2023
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 92 (5) , 1097-1112
A faster implementation of EQ and SE queries for switch-list representations
- 16 December 2023
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 92 (5) , 1097-1112
A faster implementation of EQ and SE queries for switch-list representations
- 15 June 2023
- Published by Springer Nature in Annals of Operations Research
- Vol. 336 (3) , 2091-2110
Recognizing distributed approval voting forms and correspondences
- 15 June 2023
- Published by Springer Nature in Annals of Operations Research
- Vol. 336 (3) , 2091-2110
Recognizing distributed approval voting forms and correspondences
- Open Access
- 4 May 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 922, 170-178
Unique key Horn functions
- 4 May 2022
- Published by Elsevier in Theoretical Computer Science
- Vol. 922, 170-178
Open AccessUnique key Horn functions
- Open Access
Recognizing distributed approval voting forms and correspondences
Each voter $i \in I$ has $\alpha_i$ cards that (s)he distributes among the candidates $a \in A$ as a measure of approval. One (or several) candidate(s) who received the maximum number of cards is (are) elected. We provide polynomial algorithms to recognize voting forms and voting correspondences generated by such voting schemes in cases when either the number of candidates or the number of voters is equal to $2$. We prove that for two voters, if $\alpha_2 \geq \alpha_1-2\geq 0$ then the unique voting correspondence has distinct rows. We also characterize voting forms with distinct rows.Open AccessRecognizing distributed approval voting forms and correspondences
Each voter $i \in I$ has $\alpha_i$ cards that (s)he distributes among the candidates $a \in A$ as a measure of approval. One (or several) candidate(s) who received the maximum number of cards is (are) elected. We provide polynomial algorithms to recognize voting forms and voting correspondences generated by such voting schemes in cases when either the number of candidates or the number of voters is equal to $2$. We prove that for two voters, if $\alpha_2 \geq \alpha_1-2\geq 0$ then the unique voting correspondence has distinct rows. We also characterize voting forms with distinct rows. - Open Access
- 18 October 2020
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 69, 501–529
Properties of Switch-List Representations of Boolean Functions
In this paper, we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists, which are closely related to interval representations. Given a truth table representation of a Boolean function f the switch-list representation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. The main aim of this paper is to include this type of representation in the Knowledge Compilation Map by Darwiche and Marquis and to argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard representations (such as CNF, DNF, and OBDD) with respect to their relative succinctness. As a by-product of this analysis, we also give a short proof of a longstanding open question proposed by Darwiche and Marquis, namely the incomparability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between switch-lists and OBDDs, we develop a polynomial time compilation algorithm from switch-lists to OBDDs. Finally, we analyze which standard transformations and queries (those considered by Darwiche and Marquis) can be performed in polynomial time with respect to the size of the input if the input knowledge is represented by a switch-list. We show that this collection is very broad and the combination of polynomial time transformations and queries is quite unique. Some of the queries can be answered directly using the switch-list input, others require a compilation of the input to OBDD representations which are then used to answer the queries.
- 18 October 2020
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 69, 501–529
Open AccessProperties of Switch-List Representations of Boolean Functions
In this paper, we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists, which are closely related to interval representations. Given a truth table representation of a Boolean function f the switch-list representation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. The main aim of this paper is to include this type of representation in the Knowledge Compilation Map by Darwiche and Marquis and to argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard representations (such as CNF, DNF, and OBDD) with respect to their relative succinctness. As a by-product of this analysis, we also give a short proof of a longstanding open question proposed by Darwiche and Marquis, namely the incomparability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between switch-lists and OBDDs, we develop a polynomial time compilation algorithm from switch-lists to OBDDs. Finally, we analyze which standard transformations and queries (those considered by Darwiche and Marquis) can be performed in polynomial time with respect to the size of the input if the input knowledge is represented by a switch-list. We show that this collection is very broad and the combination of polynomial time transformations and queries is quite unique. Some of the queries can be answered directly using the switch-list input, others require a compilation of the input to OBDD representations which are then used to answer the queries.
- Open Access
Unique key Horn functions
Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely defines a pure Horn function $h$, representing the functional dependencies. If the knowledge of the attribute values in set $A$ determines the value for attribute $v$, then $A\rightarrow v$ is an implicate of $h$. If $K$ is a key of the database, then $K\rightarrow v$ is an implicate of $h$ for all attributes $v$. Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co-NP-complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the Minimum Key problem is at least as hard as the Minimum Target Set Selection problem with bounded thresholds.Open AccessUnique key Horn functions
Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely defines a pure Horn function $h$, representing the functional dependencies. If the knowledge of the attribute values in set $A$ determines the value for attribute $v$, then $A\rightarrow v$ is an implicate of $h$. If $K$ is a key of the database, then $K\rightarrow v$ is an implicate of $h$ for all attributes $v$. Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co-NP-complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the Minimum Key problem is at least as hard as the Minimum Target Set Selection problem with bounded thresholds. - Open Access
Generating clause sequences of a CNF formula
Given a CNF formula $\Phi$ with clauses $C_1,\ldots,C_m$ and variables $V=\{x_1,\ldots,x_n\}$, a truth assignment $a:V\rightarrow\{0,1\}$ of $\Phi$ leads to a clause sequence $\sigma_\Phi(a)=(C_1(a),\ldots,C_m(a))\in\{0,1\}^m$ where $C_i(a) = 1$ if clause $C_i$ evaluates to $1$ under assignment $a$, otherwise $C_i(a) = 0$. The set of all possible clause sequences carries a lot of information on the formula, e.g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties. We consider a problem posed at Dagstuhl Seminar 19211 "Enumeration in Data Management" (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay.Open AccessGenerating clause sequences of a CNF formula
Given a CNF formula $\Phi$ with clauses $C_1,\ldots,C_m$ and variables $V=\{x_1,\ldots,x_n\}$, a truth assignment $a:V\rightarrow\{0,1\}$ of $\Phi$ leads to a clause sequence $\sigma_\Phi(a)=(C_1(a),\ldots,C_m(a))\in\{0,1\}^m$ where $C_i(a) = 1$ if clause $C_i$ evaluates to $1$ under assignment $a$, otherwise $C_i(a) = 0$. The set of all possible clause sequences carries a lot of information on the formula, e.g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties. We consider a problem posed at Dagstuhl Seminar 19211 "Enumeration in Data Management" (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay. - 1 May 2019
- Published by Elsevier in Discrete Mathematics
- Vol. 342 (5) , 1275-1292
Separable discrete functions: Recognition and sufficient conditions
- 1 May 2019
- Published by Elsevier in Discrete Mathematics
- Vol. 342 (5) , 1275-1292
Separable discrete functions: Recognition and sufficient conditions