Anindya De
ABSTRACT
The Chow parameters of a Boolean function f: {-1,1}n -> {-1,1} are its n+1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Cho61, Tan61] that the (exact values of the) Chow parameters of any linear threshold function f uniquely specify f within the space of all Boolean functions, but until recently [OS11] nothing was known about efficient algorithms for reconstructing f (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem. Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function f, runs in time ~O(n2)• (1/ε)O(log2(1/ε)) and with high probability outputs a representation of an LTF f' that is ε-close to f. The only previous algorithm [OS11] had running time poly(n) • 22~O(1/ε2).
As a byproduct of our approach, we show that for any linear threshold function f over {-1,1}n, there is a linear threshold function f' which is ε-close to f and has all weights that are integers at most √n • (1/ε)O(log2(1/ε)). This significantly improves the best previous result of [Serv09] which gave a poly(n) • 2O(1/ε2/3) weight bound, and is close to the known lower bound of max{√n, (1/ε)Ω(log log (1/ε)) [Gol06,Serv07]. Our techniques also yield improved algorithms for related problems in learning theory.
In addition to being significantly stronger than previous work, our results are obtained using conceptually simpler proofs. The two main ingredients underlying our results are (1) a new structural result showing that for f any linear threshold function and g any bounded function, if the Chow parameters of f are close to the Chow parameters of g then f is close to g; (2) a new boosting-like algorithm that given approximations to the Chow parameters of a linear threshold function outputs a bounded function whose Chow parameters are close to those of f.
Supplemental Material
- H. Aziz, M. Paterson, and D. Leech. Efficient algorithm for designing weighted voting games. In IEEE Intl. Multitopic Conf., pages 1--6, 2007.Google Scholar
Cross Ref
- C. R. Baugh. Chow parameters in pseudothreshold logic. In SWAT (FOCS), pages 49--55, 1973. Google ScholarDigital Library
- S. Ben-David and E. Dichterman. Learning with restricted focus of attention. Journal of Computer and System Sciences, 56(3):277--298, 1998. Google ScholarDigital Library
- A. Birkendorf, E. Dichterman, J. Jackson, N. Klasner, and H.U. Simon. On restricted-focus-of-attention learnability of Boolean functions. Machine Learning, 30:89--123, 1998. Google ScholarDigital Library
- J. Bruck. Harmonic analysis of polynomial threshold functions. SIAM Journal on Discrete Mathematics, 3(2):168--177, 1990.Google ScholarCross Ref
- F. Carreras. On the design of voting games. Mathematical Methods of Operations Research, 59(3):503--515, 2004.Google ScholarCross Ref
- M. Cheraghchi, J. Håstad, M. Isaksson, and O. Svensson. Approximating Linear Threshold Predicates. In 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems -- APPROX 2010, pages 110--123, 2010. Google ScholarDigital Library
- C.K. Chow. On the characterization of threshold functions. In Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS), pages 34--38, 1961. Google ScholarDigital Library
- M. Dertouzos. Threshold Logic: A Synthesis Approach. MIT Press, Cambridge, MA, 1965.Google Scholar
- I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, and E. Viola. Bounded independence fools halfspaces. SIAM J. on Comput., 39(8):3441--3462, 2010. Google ScholarDigital Library
- P. Dubey and L.S. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4:99--131, 1979.Google ScholarDigital Library
- I. Diakonikolas and R. Servedio. Improved approximation of linear threshold functions. In Proc. 24th Annual IEEE Conference on Computational Complexity (CCC), pages 161--172, 2009. Google ScholarDigital Library
- E. Einy and E. Lehrer. Regular simple games. International Journal of Game Theory, 18:195--207, 1989. Google ScholarDigital Library
- W. Feller. An introduction to probability theory and its applications. John Wiley & Sons, 1968.Google Scholar
- V. Feldman. Distribution-specific agnostic boosting. In Proceedings of Innovations in Computer Science, pages 241--250, 2010.Google Scholar
- V. Feldman. Learning DNF expressions from Fourier spectrum. CoRR, abs/1203.0594, 2012.Google Scholar
- Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. Agnostic learning of monomials by halfspaces is hard. In FOCS, pages 385--394, 2009. Google ScholarDigital Library
- D. Felsenthal and M. Machover. A priori voting power: what is it all about? Political Studies Review, 2(1):1--23, 2004.Google ScholarCross Ref
- J. Freixas. Different ways to represent weighted majority games. Top (Journal of the Spanish Society of Statistics and Operations Research), 5(2):201--212, 1997.Google Scholar
- P. Goldberg. A Bound on the Precision Required to Estimate a Boolean Perceptron from its Average Satisfying Assignment. SIAM Journal on Discrete Mathematics, 20:328--343, 2006. Google ScholarDigital Library
- G. Halász. Estimates for the concentration function of combinatorial number theory and probability. Period. Math. Hungar., 8(3):197--211, 1977.Google ScholarCross Ref
- J. Håstad. On the size of weights for threshold gates. SIAM Journal on Discrete Mathematics, 7(3):484--492, 1994. Google ScholarDigital Library
- S.L. Hurst. The application of Chow Parameters and Rademacher-Walsh matrices in the synthesis of binary functions. The Computer Journal, 16:165--173, 1973.Google ScholarCross Ref
- Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS), pages 538--545. IEEE Computer Society Press, 1995. Google ScholarDigital Library
- P. Kaszerman. A geometric test-synthesis procedure for a threshold device. Information and Control, 6(4):381--398, 1963.Google ScholarCross Ref
- A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), pages 11--20, 2005. Google ScholarDigital Library
- M. Kearns, R. Schapire, and L. Sellie. Toward Efficient Agnostic Learning. Machine Learning, 17(2/3):115--141, 1994. Google ScholarDigital Library
- K.R. Kaplan and R.O. Winder. Chebyshev approximation and threshold functions. IEEE Trans. Electronic Computers, EC-14:315--325, 1965.Google ScholarCross Ref
- E. Lapidot. The counting vector of a simple game. Proceedings of the AMS, 31:228--231, 1972.Google ScholarCross Ref
- D. Leech. Power indices as an aid to institutional design: the generalised apportionment problem. In M. Holler, H.Kliemt, D. Schmidtchen, and M. Streit, editors, Yearbook on New Political Economy, 2003.Google Scholar
- K. Matulef, R. O'Donnell, R. Rubinfeld, and R. Servedio. Testing halfspaces. SIAM J. on Comput., 39(5):2004--2047, 2010. Google ScholarDigital Library
- A. M. Odlyzko. On subspaces spanned by random selections of $\pm 1$ vectors. J. Comb. Theory, Ser. A, 47(1):124--133, 1988. Google ScholarDigital Library
- R. O'Donnell and R. Servedio. The Chow Parameters Problem. SIAM J. on Comput., 40(1):165--199, 2011. Google ScholarDigital Library
- V.P. Roychowdhury, K.-Y. Siu, A. Orlitsky, and T. Kailath. Vector analysis of threshold functions. Information and Computation, 120(1):22--31, 1995. Google ScholarDigital Library
- R. Servedio. Every linear threshold function has a low-weight approximator. Comput. Complexity, 16(2):180--209, 2007. Google ScholarDigital Library
- M. Tannenbaum. The establishment of a unique representation for a linearly separable function. Technical report, Lockheed Missiles and Space Co., 1961. Threshold Switching Techniques Note 20, pp. 1--5.Google Scholar
- K. Takamiya and A. Tanaka. Computational complexity in the design of voting games. Technical Report 653, The Institute of Social and Economic Research, Osaka University, 2006.Google Scholar
- Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In IEEE Conference on Computational Complexity, pages 126--136, 2009. Google ScholarDigital Library
- T.Tao and V. H. Vu. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. Annals of Mathematics, 169:595--632, 2009.Google ScholarCross Ref
- A. Taylor and W. Zwicker. A Characterization of Weighted Voting. Proceedings of the AMS, 115(4):1089--1094, 1992.Google Scholar
- R.O. Winder. Threshold logic in artificial intelligence. Artificial Intelligence, IEEE Publication S-142:107--128, 1963.Google Scholar
- R.O. Winder. Threshold gate approximations based on chow parameters. IEEE Transactions on Computers, pages 372--375, 1969. Google ScholarDigital Library
- R.O. Winder. Chow parameters in threshold logic. Journal of the ACM, 18(2):265--289, 1971. Google ScholarDigital Library
Index Terms
- Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces
Recommendations
Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
The Chow parameters of a Boolean function f:{−1, 1}n → {−1, 1} are its n+1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Chow 1961; Tannenbaum 1961] that the (exact values of the) Chow parameters of any linear threshold ...
The chow parameters problem
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the 2nd Annual FOCS (1961), C. K. Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters. Providing an algorithmic version of Chow'...
The Chow Parameters Problem
In [Proceedings of the Second Symposium on Switching Circuit Theory and Logical Design (FOCS), 1961, pp. 34-38], Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers ...
Comments