Access Restriction

Author Luby, M. ♦ Velickovic, B. ♦ Wigderson, A.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1993
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Polynomials ♦ Circuit simulation ♦ Approximation algorithms ♦ Boolean functions ♦ Computer science ♦ Mathematics
Abstract The authors describe deterministic algorithms which for a given depth-2 circuit F approximate the probability that on a random input F outputs a specific value alpha . The approach gives an algorithm which for a given GF(2) multivariate polynomial p and given in >0 approximates the number of zeros (or ones) of p within a multiplicative factor 1+ in . The algorithm runs in time exp(exp(O( square root log(n/ in )))), where n is the size of the circuit. They also obtain an algorithm which given a DNF formula F and in >0 approximates the number of satisfying assignments of F within a factor of 1+ in and runs in time exp(O((log(n/ in ))/sup 4/)).
Description Author affiliation: Int. Comput. Sci. Inst., Berkeley, CA, USA (Luby, M.)
ISBN 0818636300
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1993-06-07
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 605.56 kB
Page Count 7
Starting Page 18
Ending Page 24

Source: IEEE Xplore Digital Library