research
∙
09/19/2021
Making the Most of Parallel Composition in Differential Privacy
We show that the `optimal' use of the parallel composition theorem corre...
share
research
∙
02/17/2020
From Matching with Diversity Constraints to Matching with Regional Quotas
In the past few years, several new matching models have been proposed an...
research
∙
07/01/2019
Enumeration of Preferred Extensions in Almost Oriented Digraphs
In this paper, we present enumeration algorithms to list all preferred e...
research
∙
01/01/2019
On the Parameterized Cluster Editing with Vertex Splitting Problem
In the Cluster Editing problem, a given graph is to be transformed into ...
research
∙
11/09/2018
Minimizing and Computing the Inverse Geodesic Length on Trees
The inverse geodesic length (IGL) of a graph G=(V,E) is the sum of inver...
research
∙
05/21/2018
Colouring Square-Free Graphs without Long Induced Paths
The complexity of Colouring is fully understood for H-free graphs, but ...
research
∙
09/27/2017
Linearly χ-Bounding (P_6,C_4)-Free Graphs
Given two graphs H_1 and H_2, a graph G is (H_1,H_2)-free if it contains...
research
∙
09/18/2015
Backdoors into Heterogeneous Classes of SAT and CSP
In this paper we extend the classical notion of strong and weak backdoor...
research
∙
02/26/2015
Online Fair Division: analysing a Food Bank problem
We study an online model of fair division designed to capture features o...
research
∙
07/11/2014
Computational Aspects of Multi-Winner Approval Voting
We study computational aspects of three prominent voting rules that use ...
research
∙
06/12/2014
Guarantees and Limits of Preprocessing in Constraint Satisfaction and Reasoning
We present a first theoretical analysis of the power of polynomial-time ...
research
∙
12/23/2013
Fair assignment of indivisible objects under ordinal preferences
We consider the discrete assignment problem in which agents express ordi...
research
∙
04/03/2013
Coalitional Manipulation for Schulze's Rule
Schulze's rule is used in the elections of a large number of organizatio...
research
∙
02/07/2013
Possible and Necessary Winner Problem in Social Polls
Social networks are increasingly being used to conduct polls. We introdu...
research
∙
08/08/2012
On Finding Optimal Polytrees
Inferring probabilistic networks from data is a notoriously difficult ta...
research
∙
04/27/2012
Strong Backdoors to Bounded Treewidth SAT
There are various approaches to exploiting "hidden structure" in instanc...
research
∙
02/20/2012
Strong Backdoors to Nested Satisfiability
Knuth (1990) introduced the class of nested formulas and showed that the...
research
∙
10/28/2011
Backdoors to Satisfaction
A backdoor set is a set of variables of a propositional formula such tha...
research
∙
10/28/2011
Backdoors to Acyclic SAT
Backdoor sets, a notion introduced by Williams et al. in 2003, are certa...
research
∙
04/13/2011