NDLI: Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT

Content Provider	IEEE Xplore Digital Library
Author	Beame, P. Impagliazzo, R. Srinivasan, S.
Copyright Year	2012
Abstract	We show how to approximate any function in AC^0 by decision trees of much smaller height than its number of variables. More precisely, we show that any function in n variables computable by an unbounded fan-in circuit of AND, OR, and NOT gates that has size S and depth d can be approximated by a decision tree of height n - \beta n to within error exp(-\beta n), where \beta = \beta (S, d) = 2^{-O(d log^{4/5}S)}. Our proof is constructive and we use its constructivity to derive a deterministic algorithm for #AC^0SAT with multiplicative factor savings over the naive 2^n.S algorithm of 2^{-\beta n}, when applied to any n-input AC^0 circuit of size S and depth d. Indeed, in the same running time we can deterministically construct a decision tree of size at most 2^{n-\beta n} that exactly computes the function given by such a circuit. Recently, Impagliazzo, Matthews, and Paturi derived an algorithm for #AC^0SAT with greater savings over the naive algorithm but their algorithm is only randomized rather than deterministic. The main technical result we prove to show the above is that for every family F of k-DNF formulas in n variables and every 1
Starting Page	117
Ending Page	125
File Size	283645
Page Count	9
File Format	PDF
ISBN	9781467316637
ISSN	10930159
e-ISBN	9780769547084
DOI	10.1109/CCC.2012.40
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-26
Publisher Place	Portugal
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Decision trees Vegetation Approximation algorithms Correlation Boolean functions Approximation methods Educational institutions Constant-depth circuits Satisfiability algorithms
Content Type	Text
Resource Type	Article

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

Approximating AC0 by small height decision trees and a deterministic algorithm for #AC0sat (2012)

Approximating AC0 by small height decision trees and a deterministic algorithm for #AC0SAT (2012)

Approximating Boolean Functions with Depth-2 Circuits

The Complexity of Satisfiability of Small Depth Circuits

Deterministic approximate counting of depth-2 circuits

Complexity of decision trees for Boolean functions

The Power of Asymmetry in Constant-Depth Circuits

Improved Binary Decision Diagram Constraint Propagation for Satisfiability Problems

Approximating fuzzy membership functions from clustered raw data

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT

Similar Documents

Approximating AC0 by small height decision trees and a deterministic algorithm for #AC0sat (2012)

Approximating AC0 by small height decision trees and a deterministic algorithm for #AC0SAT (2012)

Approximating Boolean Functions with Depth-2 Circuits

The Complexity of Satisfiability of Small Depth Circuits

Deterministic approximate counting of depth-2 circuits

Complexity of decision trees for Boolean functions

The Power of Asymmetry in Constant-Depth Circuits

Improved Binary Decision Diagram Constraint Propagation for Satisfiability Problems

Approximating fuzzy membership functions from clustered raw data

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT