23 papers:
PODS-2015-FaginKK #complexity- Dichotomies in the Complexity of Preferred Repairs (RF, BK, PGK), pp. 3–15.
CSL-2015-DawarW #finite- A Definability Dichotomy for Finite Valued CSPs (AD, PW), pp. 60–77.
LICS-2015-DalmauEHLR #complexity #problem- Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy (VD, LE, PH, BL, AR), pp. 487–498.
- PODS-2014-FinkO #database #probability #query
- A dichotomy for non-repeating queries with negation in probabilistic databases (RF, DO), pp. 144–155.
STOC-2014-GargMV #algorithm #equilibrium- Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions (JG, RM, VVV), pp. 525–534.
- PODS-2013-Wong #calculus #power of #relational #set
- A dichotomy in the intensional expressive power of nested relational calculi augmented with aggregate functions and a powerset operator (LW), pp. 285–296.
- STOC-2013-CaiGW
- A complete dichotomy rises from the capture of vanishing signatures: extended abstract (JYC, HG, TW), pp. 635–644.
LATA-2013-Cai #complexity #problem- Complexity Dichotomy for Counting Problems (JYC), pp. 1–11.
- LICS-2013-Fontaine #consistency #query #question #why
- Why is it Hard to Obtain a Dichotomy for Consistent Query Answering? (GF), pp. 550–559.
- PODS-2012-Kimelfeld #complexity #dependence #functional
- A dichotomy in the complexity of deletion propagation with functional dependencies (BK), pp. 191–202.
- LICS-2011-Barto #constraints #problem #revisited
- The Dichotomy for Conservative Constraint Satisfaction Problems Revisited (LB), pp. 301–310.
ICALP-v1-2010-CaiCL #graph #morphism #theorem- Graph Homomorphisms with Complex Values: A Dichotomy Theorem (JyC, XC, PL), pp. 275–286.
- ICALP-v1-2010-KratschW #preprocessor #problem
- Preprocessing of Min Ones Problems: A Dichotomy (SK, MW), pp. 653–665.
- STOC-2009-KunS
- A new line of attack on the dichotomy conjecture (GK, MS), pp. 725–734.
- ICALP-B-2008-BodirskyG #complexity #constraints
- Non-dichotomies in Constraint Satisfaction Complexity (MB, MG), pp. 184–196.
- PODS-2007-DalviS07a #probability #query
- The dichotomy of conjunctive queries on probabilistic structures (NND, DS), pp. 293–302.
- ICALP-v1-2006-GopalanKMP #satisfiability
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies (PG, PGK, ENM, CHP), pp. 346–357.
SAT-2006-ChenIJSS #constraints #problem #theorem- A Dichotomy Theorem for Typed Constraint Satisfaction Problems (SC, TI, KJ, DS, MS), pp. 226–239.
ICML-2004-FrankK #multi #problem- Ensembles of nested dichotomies for multi-class problems (EF, SK).
- LICS-2001-KirousisK #complexity
- A Dichotomy in the Complexity of Propositional Circumscription (LMK, PGK), pp. 71–80.
DATE-1998-Coudert #encoding #paradigm- A New Paradigm for Dichotomy-based Constrained Encoding (OC), pp. 830–834.
- ICML-1997-MayorazM #composition #on the
- On the Decomposition of Polychotomies into Dichotomies (EM, MM), pp. 219–226.
POPL-1977-Pratt #performance #programming- The Competence/Performance Dichotomy in Programming (VRP), pp. 194–200.
