NDLI: Counting Predicates, Subset Surjective Functions, and Counting CSPs

Content Provider	IEEE Xplore Digital Library
Author	Bulatov, A.A. Hedayaty, A.
Copyright Year	2012
Abstract	We introduce a new type of closure operator on the set of relations, max-implementation, and its weaker analog max-quantification. Then we show that approximation reductions between counting constraint satisfaction problems (CSPs) are preserved by these two types of closure operators. Together with some previous results this means that the approximation complexity of counting CSPs is determined by partial clones of relations that additionally closed under these new types of closure operators. Galois correspondence of various kind have proved to been quite helpful in the study of the complexity of the CSP. While we were unable to identify a Galois correspondence for partial clones closed under max-implementation and max-quantification, we obtain such results for slightly different type of closure operators, k-existential quantification. This type of quantifiers are known as counting quantifiers in model theory, and often used to enhance first order logic languages. We characterize partial clones of relations closed under k-existential quantification as sets of relations invariant under a set of partial functions that satisfy the condition of k-subset surjectivity.
Starting Page	331
Ending Page	336
File Size	209576
Page Count	6
File Format	PDF
ISBN	9781467309080
ISSN	0195623X
DOI	10.1109/ISMVL.2012.46
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-05-14
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Cloning Approximation methods Complexity theory Polynomials Approximation algorithms Standards Educational institutions approximation clones clones of relations Galois correspondence counting problems
Content Type	Text
Resource Type	Article
Subject	Mathematics 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

Boolean Max-Co-Clones

Counting quantifiers, subset surjective functions, and counting csps.

Log-supermodular functions, functional clones and counting CSPs

Log-supermodular functions, functional clones and counting CSPs

Counting Problems and Clones of Functions

Counting quantifiers , subset surjective functions , and counting CSPs

The proof complexity of linear algebra

Polynomials as Generators of Minimal Clones

Polynomial degree vs. quantum query complexity

Counting Predicates, Subset Surjective Functions, and Counting CSPs

Similar Documents

Boolean Max-Co-Clones

Counting quantifiers, subset surjective functions, and counting csps.

Log-supermodular functions, functional clones and counting CSPs

Log-supermodular functions, functional clones and counting CSPs

Counting Problems and Clones of Functions

Counting quantifiers , subset surjective functions , and counting CSPs

The proof complexity of linear algebra

Polynomials as Generators of Minimal Clones

Polynomial degree vs. quantum query complexity

Counting Predicates, Subset Surjective Functions, and Counting CSPs