On the complexity of trial and error for constraint satisfaction problems

Ivanyos, G; Kulkarni, R; Qiao, Y; Santha, M; Sundaram, A

On the complexity of trial and error for constraint satisfaction problems

Ivanyos, G Kulkarni, R Qiao, Y

Santha, M Sundaram, A

Permalink

Publisher:: Springer
Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8572 LNCS, (PART 1), pp. 663-675
Issue Date:: 2014-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (339.17 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ivanyos, G
dc.contributor.author	Kulkarni, R
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449
dc.contributor.author	Santha, M
dc.contributor.author	Sundaram, A
dc.date.accessioned	2022-08-05T13:21:58Z
dc.date.available	2022-08-05T13:21:58Z
dc.date.issued	2014-01-01
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8572 LNCS, (PART 1), pp. 663-675
dc.identifier.isbn	9783662439470
dc.identifier.issn	0302-9743
dc.identifier.issn	1611-3349
dc.identifier.uri	http://hdl.handle.net/10453/159686
dc.description.abstract	In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if the assignment is not satisfying. In this paper we initiate a systematic study of constraint satisfaction problems in the trial and error model. To achieve this, we first adopt a formal framework for CSPs, and based on this framework we define several types of revealing oracles. Our main contribution is to develop a transfer theorem for each type of the revealing oracle, under a broad class of parameters. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another, potentially harder CSP in the normal setting, such that their complexities are polynomial time equivalent. This in principle transfers the study of a large class of hidden CSPs, possibly with a promise on the instances, to the study of CSPs in the normal setting. We then apply the transfer theorems to get polynomial-time algorithms or hardness results for hidden CSPs, including satisfaction problems, monotone graph properties, isomorphism problems, and the exact version of the Unique Games problem. © 2014 Springer-Verlag.
dc.language	en
dc.publisher	Springer
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.relation.ispartof	International Colloquium on Automata Languages and Programming
dc.relation.isbasedon	10.1007/978-3-662-43948-7_55
dc.rights	info:eu-repo/semantics/openAccess
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	On the complexity of trial and error for constraint satisfaction problems
dc.type	Conference Proceeding
utslib.citation.volume	8572 LNCS
utslib.location.activity	Copenhagen, Denmark
utslib.for	0802 Computation Theory and Mathematics
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
pubs.consider-herdc	false
dc.date.updated	2022-08-05T13:21:57Z
pubs.issue	PART 1
pubs.publication-status	Published
pubs.volume	8572 LNCS
utslib.citation.issue	PART 1

Abstract:

In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if the assignment is not satisfying. In this paper we initiate a systematic study of constraint satisfaction problems in the trial and error model. To achieve this, we first adopt a formal framework for CSPs, and based on this framework we define several types of revealing oracles. Our main contribution is to develop a transfer theorem for each type of the revealing oracle, under a broad class of parameters. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another, potentially harder CSP in the normal setting, such that their complexities are polynomial time equivalent. This in principle transfers the study of a large class of hidden CSPs, possibly with a promise on the instances, to the study of CSPs in the normal setting. We then apply the transfer theorems to get polynomial-time algorithms or hardness results for hidden CSPs, including satisfaction problems, monotone graph properties, isomorphism problems, and the exact version of the Unique Games problem. © 2014 Springer-Verlag.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/159686