CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt146",{id:"formSmash:upper:j_idt146",widgetVar:"widget_formSmash_upper_j_idt146",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt147_j_idt149",{id:"formSmash:upper:j_idt147:j_idt149",widgetVar:"widget_formSmash_upper_j_idt147_j_idt149",target:"formSmash:upper:j_idt147:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Label Cover Reductions for Unconditional Approximation Hardness of Constraint SatisfactionPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2014 (English)Doctoral thesis, comprehensive summary (Other academic)Alternative title
##### Abstract [en]

##### Place, publisher, year, edition, pages

Stockholm: Numerical Analysis and Computer Science (NADA), Stockholm University , 2014. , xii, 52 p.
##### Keyword [en]

Optimization, NP, Approximation, Approximability, Inapproximability, Constraint Satisfaction, CSP, Boolean Analysis, Satisfiability, SAT, Acyclic Subgraph, Betweenness, Unique Games
##### National Category

Computer Science
##### Research subject

Computer Science
##### Identifiers

URN: urn:nbn:se:kth:diva-151402OAI: oai:DiVA.org:kth-151402DiVA: diva2:748501
##### Public defence

2014-10-21, F3, Sing Sing, Lindstedtsvägen 26, KTH, Stockholm, 13:15 (English)
##### Opponent

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt434",{id:"formSmash:j_idt434",widgetVar:"widget_formSmash_j_idt434",multiple:true});
##### Supervisors

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt440",{id:"formSmash:j_idt440",widgetVar:"widget_formSmash_j_idt440",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt446",{id:"formSmash:j_idt446",widgetVar:"widget_formSmash_j_idt446",multiple:true});
##### Projects

Approximation of NP-hard optimization problems
##### Funder

EU, European Research Council, 226203
##### Note

##### List of papers

Etikettäckningsreduktioner för Obetingad Approximationssvårighet av Vilkorssatisfiering (Swedish)

Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). In these, one is given a collection of constraints on variables with the task of finding an assignment satisfying the greatest number of constraints. In particular, parity constraints dictate that an odd (alt. even) number of variables are assigned a certain value.Satisfiable collections of parity constraints are easy in the sense that they can be efficiently solved via Gaussian elimination. We prove the threshold phenomenon that when constraints accept even one more assignment besides parities, then it is hard to find approximate solutions which are essentially better than random assignments.We also investigate the uselessness of predicates. Uselessness is a stronger hardness property in the sense that even if one was permitted to choose the acceptance criteria for given constraints, it is NP-hard to find solutions beating random assignments. We provide the first examples of predicates which are useless even when all variables appear unnegated.Finally, in an Ordering CSP (OCSP), one receives a set of items to order and constraints specifying how the items should be ordered relative to one another. For example, in the problem Maximum Betweenness, we have constraints of the form "order x between y and z". Our contribution is to significantly improve the approximation hardness of various OCSPs and provide the first unconditional direct Probabilistically Checkable Proofs for OCSPs.Notably, all results were previously known assuming the Unique Games Conjecture and the d-to-1 Conjecture. Our unconditional analogues of the same theorems involve developments for dealing with various obstacles faced by conventional techniques.

QC 20140929

Available from: 2014-09-29 Created: 2014-09-19 Last updated: 2014-09-30Bibliographically approved1. On the NP-hardness of approximating ordering constraint satisfaction problems$(function(){PrimeFaces.cw("OverlayPanel","overlay675596",{id:"formSmash:j_idt482:0:j_idt486",widgetVar:"overlay675596",target:"formSmash:j_idt482:0:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

2. Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width four (extended abstract)$(function(){PrimeFaces.cw("OverlayPanel","overlay567834",{id:"formSmash:j_idt482:1:j_idt486",widgetVar:"overlay567834",target:"formSmash:j_idt482:1:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

3. Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four$(function(){PrimeFaces.cw("OverlayPanel","overlay587576",{id:"formSmash:j_idt482:2:j_idt486",widgetVar:"overlay587576",target:"formSmash:j_idt482:2:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

4. Parity is Positively Useless$(function(){PrimeFaces.cw("OverlayPanel","overlay748473",{id:"formSmash:j_idt482:3:j_idt486",widgetVar:"overlay748473",target:"formSmash:j_idt482:3:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1144",{id:"formSmash:j_idt1144",widgetVar:"widget_formSmash_j_idt1144",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1197",{id:"formSmash:lower:j_idt1197",widgetVar:"widget_formSmash_lower_j_idt1197",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1198_j_idt1200",{id:"formSmash:lower:j_idt1198:j_idt1200",widgetVar:"widget_formSmash_lower_j_idt1198_j_idt1200",target:"formSmash:lower:j_idt1198:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});