Arrow Research search

Author name cluster

Joanna Ochremiak

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers
1 author row

Possible papers

4

Highlights Conference 2018 Conference Abstract

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem

  • Joanna Ochremiak

ABSTRACT. I will discuss several mathematical programming relaxations of the graph isomorphism problem: the Sherali-Adams hierarchy of LP relaxations, its strengthening via the Lasserre hierarchy of SDP relaxations, and its relaxation via Groebner basis computations. I will present a result which completes a full cycle of implications to show that, for the graph isomorphism problem, the relative strength of those relaxations is the same, up to a small loss in the level of the hierarchy. This is joint work with Albert Atserias.

Details

Highlights Conference 2015 Conference Abstract

Algebraic Necessary Condition for Tractability of Valued CSP

  • Joanna Ochremiak

Many natural optimisation problems are expressible as Valued Constraint Satisfaction Problems (VCSPs). Examples include: Max-Cut, Minimum Vertex Cover, Max-3-Sat. We present an algebraic framework for VCSPs, generalising the algebraic framework for its decision version (CSPs) provided by Bulatov et al. We formulate an Algebraic VCSP Dichotomy Conjecture, which says that each valued constraint language gives rise to an optimisation problem solvable in PTime, or to an NP-hard one. It also proposes a criterion to distinguish those two cases. We prove the hardness direction, establishing a necessary algebraic condition for tractability of VCSPs with fixed constraint languages. This is joint work with Marcin Kozik.

Details

Highlights Conference 2014 Conference Abstract

Turing Machines with Atoms and Constraint Satisfaction Problems

  • Joanna Ochremiak

We study deterministic computability over sets with atoms. We characterize those alphabets for which Turing machines with atoms determinize. To this end, the determinization problem is expressed as a Constraint Satisfaction Problem, and a characterization is obtained from deep results in CSP theory. This is joint work with Bartek Klin, Sławomir Lasota and Szymon Toruńczyk.

Details