BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Phokion G. Kolaitis

Phokion G. Kolaitis appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryDatabasesComputational ComplexityDiscrete MathematicsInformation Theorymath.COmath.ITmath.LO

Catalog footprint

What is connected

7works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2020arXiv

Algorithmic Techniques for Necessary and Possible Winners

We investigate the practical aspects of computing the necessary and possible winners in elections over incomplete voter preferences. In the case of the necessary winners, we show how to implement and accelerate the polynomial-time algorithm of Xia and Conitzer. In the case of the possible winners, where the problem is NP-hard, we give a natural reduction to Integer Linear Programming (ILP) for all positional scoring rules and implement it in a leading commercial optimization solver. Further, we devise optimization techniques to minimize the number of ILP executions and, oftentimes, avoid them altogether. We conduct a thorough experimental study that includes the construction of a rich benchmark of election data based on real and synthetic data. Our findings suggest that, the worst-case intractability of the possible winners notwithstanding, the algorithmic techniques presented here scale well and can be used to compute the possible winners in realistic scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Consistency, Acyclicity, and Positive Semirings

In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work about probability distributions by Vorob'ev (1962) and about database relations by Beeri, Fagin, Maier, Yannakakis (1983) produced characterizations of when local consistency always implies global consistency. Towards a common generalization of these results, we consider K-relations, that is, relations over a set of attributes such that each tuple in the relation is associated with an element from an arbitrary, but fixed, positive semiring K. We introduce the notions of projection of a K-relation, consistency of two K-relations, and global consistency of a collection of K-relations; these notions are natural extensions of the corresponding notions about probability distributions and database relations. We then show that a collection of sets of attributes has the property that every pairwise consistent collection of K-relations over those attributes is globally consistent if and only if the sets of attributes form an acyclic hypergraph. This generalizes the aforementioned results by Vorob'ev and by Beeri et al., and demonstrates that K-relations over positive semirings constitute a natural framework for the study of the interplay between local and global consistency. In the course of the proof, we introduce a notion of join of two K-relations and argue that it is the "right" generalization of the join of two database relations. Furthermore, to show that non-acyclic hypergraphs yield pairwise consistent K-relations that are globally inconsistent, we generalize a construction by Tseitin (1968) in his study of hard-to-prove tautologies in propositional logic.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Decision Problems in Information Theory

Constraints on entropies are considered to be the laws of information theory. Even though the pursuit of their discovery has been a central theme of research in information theory, the algorithmic aspects of constraints on entropies remain largely unexplored. Here, we initiate an investigation of decision problems about constraints on entropies by placing several different such problems into levels of the arithmetical hierarchy. We establish the following results on checking the validity over all almost-entropic functions: first, validity of a Boolean information constraint arising from a monotone Boolean formula is co-recursively enumerable; second, validity of "tight" conditional information constraints is in $Π^0_3$. Furthermore, under some restrictions, validity of conditional information constraints "with slack" is in $Σ^0_2$, and validity of information inequality constraints involving max is Turing equivalent to validity of information inequality constraints (with no max involved). We also prove that the classical implication problem for conditional independence statements is co-recursively enumerable.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Complexity of Possible Winners on Partial Chains

The Possible Winner (PW) problem, a fundamental algorithmic problem in computational social choice, concerns elections where voters express only partial preferences between candidates. Via a sequence of investigations, a complete classification of the complexity of the PW problem was established for all pure positional scoring rules: the PW problem is in P for the plurality and veto rules, and NP-complete for all other such rules. More recently, the PW problem was studied on classes of restricted partial orders that arise in natural settings, such as partitioned partial orders and truncated partial orders; in particular, it was shown that there are rules for which the PW problem drops from NP-complete to P on such restricted partial orders. Here, we investigate the PW problem on partial chains, i.e., partial orders that are a total order on a subset of their domains. Such orders arise naturally in a variety of settings, including rankings of movies or restaurants. We classify the complexity of the PW problem on partial chains by establishing that, perhaps surprisingly, this restriction does not change the complexity of the problem, namely, the PW problem is NP-complete for all pure positional scoring rules other than the plurality and veto rules. As a byproduct, we obtain a new and more principled proof of the complexity of the PW problem on arbitrary partial orders.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Aggregation of Votes with Multiple Positions on Each Issue

We consider the problem of aggregating votes cast by a society on a fixed set of issues, where each member of the society may vote for one of several positions on each issue, but the combination of votes on the various issues is restricted to a set of feasible voting patterns. We require the aggregation to be supportive, i.e. for every issue $j$ the corresponding component $f_j$ of every aggregator on every issue should satisfy $f_j(x_1, ,\ldots, x_n) \in \{x_1, ,\ldots, x_n\}$. We prove that, in such a set-up, non-dictatorial aggregation of votes in a society of some size is possible if and only if either non-dictatorial aggregation is possible in a society of only two members or a ternary aggregator exists that either on every issue $j$ is a majority operation, i.e. the corresponding component satisfies $f_j(x,x,y) = f_j(x,y,x) = f_j(y,x,x) =x, \forall x,y$, or on every issue is a minority operation, i.e. the corresponding component satisfies $f_j(x,x,y) = f_j(x,y,x) = f_j(y,x,x) =y, \forall x,y.$ We then introduce a notion of uniformly non-dictatorial aggregator, which is defined to be an aggregator that on every issue, and when restricted to an arbitrary two-element subset of the votes for that issue, differs from all projection functions. We first give a characterization of sets of feasible voting patterns that admit a uniformly non-dictatorial aggregator. Then making use of Bulatov's dichotomy theorem for conservative constraint satisfaction problems, we connect social choice theory with combinatorial complexity by proving that if a set of feasible voting patterns $X$ has a uniformly non-dictatorial aggregator of some arity then the multi-sorted conservative constraint satisfaction problem on $X$, in the sense introduced by Bulatov and Jeavons, with each issue representing a sort, is tractable; otherwise it is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Consistent Answers of Conjunctive Queries on Graphs

During the past decade, there has been an extensive investigation of the computational complexity of the consistent answers of Boolean conjunctive queries under primary key constraints. Much of this investigation has focused on self-join-free Boolean conjunctive queries. In this paper, we study the consistent answers of Boolean conjunctive queries involving a single binary relation, i.e., we consider arbitrary Boolean conjunctive queries on directed graphs. In the presence of a single key constraint, we show that for each such Boolean conjunctive query, either the problem of computing its consistent answers is expressible in first-order logic, or it is polynomial-time solvable, but not expressible in first-order logic.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Exchange-Repairs: Managing Inconsistency in Data Exchange

In a data exchange setting with target constraints, it is often the case that a given source instance has no solutions. In such cases, the semantics of target queries trivialize. The aim of this paper is to introduce and explore a new framework that gives meaningful semantics in such cases by using the notion of exchange-repairs. Informally, an exchange-repair of a source instance is another source instance that differs minimally from the first, but has a solution. Exchange-repairs give rise to a natural notion of exchange-repair certain answers (XR-certain answers) for target queries. We show that for schema mappings specified by source-to-target GAV dependencies and target equality-generating dependencies (egds), the XR-certain answers of a target conjunctive query can be rewritten as the consistent answers (in the sense of standard database repairs) of a union of conjunctive queries over the source schema with respect to a set of egds over the source schema, making it possible to use a consistent query-answering system to compute XR-certain answers in data exchange. We then examine the general case of schema mappings specified by source-to-target GLAV constraints, a weakly acyclic set of target tgds and a set of target egds. The main result asserts that, for such settings, the XR-certain answers of conjunctive queries can be rewritten as the certain answers of a union of conjunctive queries with respect to the stable models of a disjunctive logic program over a suitable expansion of the source schema.

0 citations0 reviewsNo code linkedOpen access