NDLI: Approximating Linear Threshold Predicates

Please wait, while we are loading the content...

Approximating Linear Threshold Predicates

Content Provider	ACM Digital Library
Author	Isaksson, Marcus Svensson, Ola Håstad, Johan Cheraghchi, Mahdi
Copyright Year	2012
Abstract	We study constraint satisfaction problems on the domain {™1, 1}, where the given constraints are homogeneous linear threshold predicates, that is, predicates of the form $sgn(w_{1}x_{1}$ + ⋯ + $w_{n}x_{n})$ for some positive integer weights $w_{1},$ ..., $w_{n}.$ Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this article is to identify and study the approximation curve of a class of threshold predicates that allow for nontrivial approximation. Arguably the simplest such predicate is the majority predicate $sgn(x_{1}$ + ⋯ + $x_{n}),$ for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of “majority-like” predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of $\textit{Chow-robustness}$ that might be of independent interest.
Starting Page	1
Ending Page	31
Page Count	31
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2141938.2141940
Volume Number	4
Issue Number	1
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-03-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithms Constraint satisfactory problems Linear threshold predicates
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Complexity of Approximating CSP with Balance / Hard Constraints

On the usefulness of predicates

Approximation Resistant Predicates from Pairwise Independence

Scheduling Problems on Two Sets of Identical Machines

Improved Approximation of Linear Threshold Functions

Approximating elementary functions with symmetric bipartite tables

Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

On the Approximation Resistance of a Random Predicate

Every 2-csp Allows Nontrivial Approximation

Approximating Linear Threshold Predicates

Similar Documents

Complexity of Approximating CSP with Balance / Hard Constraints

On the usefulness of predicates

Approximation Resistant Predicates from Pairwise Independence

Scheduling Problems on Two Sets of Identical Machines

Improved Approximation of Linear Threshold Functions

Approximating elementary functions with symmetric bipartite tables

Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

On the Approximation Resistance of a Random Predicate

Every 2-csp Allows Nontrivial Approximation

Approximating Linear Threshold Predicates