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 [Chow 1961; Tannenbaum 1961] 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 [O'Donnell and Servedio 2011] 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 Õ(n2) ⋅ (1/ϵ)O(log2(1/ϵ)) and with high probability outputs a representation of an LTF f′ that is ϵ-close to f in Hamming distance. The only previous algorithm [O'Donnell and Servedio 2011] had running time poly(n) ⋅ 22Õ(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 of magnitude at most √n ⋅ (1/ϵ)O(log2(1/ϵ)). This significantly improves the previous best result of Diakonikolas and Servedio [2009] which gave a poly(n) ⋅ 2Õ(1/ϵ2/3) weight bound, and is close to the known lower bound of max{√n, (1/ϵ)Ω(log log (1/ϵ))} [Goldberg 2006; Servedio 2007]. 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.
- H. Aziz, M. Paterson, and D. Leech. 2007. Efficient algorithm for designing weighted voting games. In Proceedings of the IEEE International Multitopic Conference. 1--6.Google Scholar
- J. Banzhaf. 1965. Weighted voting doesn't work: A mathematical analysis. Rutgers Law Rev. 19, 317--343.Google Scholar
- C. R. Baugh. 1973. Chow parameters in pseudothreshold logic. In Proceedings of SWAT (FOCS). 49--55. Google ScholarDigital Library
- S. Ben-David and E. Dichterman. 1998. Learning with restricted focus of attention. J. Comput. System Sci. 56, 3, 277--298. Google ScholarDigital Library
- A. Birkendorf, E. Dichterman, J. Jackson, N. Klasner, and H. U. Simon. 1998. On restricted-focus-of-attention learnability of Boolean functions. Mach. Learn. 30, 89--123. Google ScholarDigital Library
- J. Bruck. 1990. Harmonic analysis of polynomial threshold functions. SIAM J. Disc. Math. 3, 2, 168--177.Google ScholarCross Ref
- F. Carreras. 2004. On the design of voting games. Math. Meth. Oper. Res. 59, 3, 503--515.Google ScholarCross Ref
- M. Cheraghchi, J. Håstad, M. Isaksson, and O. Svensson. 2010. Approximating linear threshold predicates. In Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'10). 110--123. Google ScholarDigital Library
- C. K. Chow. 1961. On the characterization of threshold functions. In Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS). 34--38. Google ScholarDigital Library
- A. De, I. Diakonikolas, and R.A. Servedio. 2012. The inverse Shapley value problem. In Proceedings of ICALP. 266--277. Google ScholarDigital Library
- B. de Keijzer, T. Klos, and Y. Zhang. 2010. Enumeration and exact design of weighted voting games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. (AAMAS'10). Vol. 1, 391--398. Google ScholarDigital Library
- M. Dertouzos. 1965. Threshold Logic: A Synthesis Approach. MIT Press, Cambridge, MA.Google Scholar
- I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, and E. Viola. 2010. Bounded independence fools halfspaces. SIAM J. Comput. 39, 8, 3441--3462. Google ScholarDigital Library
- I. Diakonikolas and R. Servedio. 2009. Improved approximation of linear threshold functions. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC). 161--172. Google ScholarDigital Library
- P. Dubey and L. S. Shapley. 1979. Mathematical properties of the Banzhaf power index. Math. Oper. Res. 4, 99--131. Google ScholarDigital Library
- E. Einy and E. Lehrer. 1989. Regular simple games. Int. J. Game Theory 18, 195--207. Google ScholarDigital Library
- C. C. Elgot. 1960. Truth functions realizable by single threshold organs. In Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS). 225--245. Google ScholarDigital Library
- V. Feldman. 2010. Distribution-specific agnostic boosting. In Proceedings of the Conference on Innovations in Computer Science. 241--250.Google Scholar
- V. Feldman. 2012. Learning DNF expressions from Fourier spectrum. In Proceedings of Conference on Learning Theory. 17.1--17.19.Google Scholar
- V. Feldman, V. Guruswami, P. Raghavendra, and Y. Wu. 2009. Agnostic learning of monomials by halfspaces is hard. In Proceedings of FOCS. 385--394. Google ScholarDigital Library
- W. Feller. 1968. An Introduction to Probability Theory and Its Applications. Wiley.Google Scholar
- D. Felsenthal and M. Machover. 2004. A priori voting power: What is it all about? Polit. Stud. Rev. 2, 1, 1--23.Google Scholar
- J. Freixas. 1997. Different ways to represent weighted majority games. J. Span. Soc. Stat. Oper. Res. 5, 2, 201--212.Google Scholar
- P. Goldberg. 2006. A bound on the precision required to estimate a Boolean perceptron from its average satisfying assignment. SIAM J. Disc. Math. 20, 328--343. Google ScholarDigital Library
- G. Halász. 1977. Estimates for the concentration function of combinatorial number theory and probability. Period. Math. Hungar. 8, 3, 197--211.Google ScholarCross Ref
- J. Håstad. 1994. On the size of weights for threshold gates. SIAM J. Disc. Math. 7, 3, 484--492. Google ScholarDigital Library
- S. L. Hurst. 1973. The application of Chow parameters and Rademacher-Walsh matrices in the synthesis of binary functions. Comput. J. 16, 165--173. Issue 2.Google ScholarCross Ref
- R. Impagliazzo. 1995. Hard-core distributions for somewhat hard problems. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, 538--545. Google ScholarDigital Library
- A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. 2005. Agnostically learning halfspaces. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS). 11--20. Google ScholarDigital Library
- K. R. Kaplan and R. O. Winder. 1965. Chebyshev approximation and threshold functions. IEEE Trans. Electronic Comput. EC-14, 315--325.Google ScholarCross Ref
- P. Kaszerman. 1963. A geometric test-synthesis procedure for a threshold device. Inf. Cont. 6, 4, 381--398.Google ScholarCross Ref
- M. Kearns, R. Schapire, and L. Sellie. 1994. Toward efficient agnostic learning. Mach. Learn. 17, 2/3, 115--141. Google ScholarDigital Library
- S. Kurz. 2012. On the inverse power index problem. Optimization 61, 8, 989--1011.Google ScholarCross Ref
- S. Kurz and S. Napel. 2012. Heuristic and exact solutions to the inverse power index problem for small voting bodies. arxiv report http://arxiv.org/abs/1202.6245.Google Scholar
- E. Lapidot. 1972. The counting vector of a simple game. Proc. AMS 31, 228--231.Google ScholarCross Ref
- A. Laruelle and M. Widgren. 1998. Is the allocation of voting power among EU states fair? Public Choice 94, 317--339.Google Scholar
- D. Leech. 2002a. Designing the voting system for the EU Council of Ministers. Public Choice 113, 437--464.Google ScholarCross Ref
- D. Leech. 2002b. Voting power in the governance of the International Monetary Fund. Ann. Oper. Res. 109, 375--397.Google ScholarCross Ref
- D. Leech. 2003. Power indices as an aid to institutional design: The generalised apportionment problem. In Yearbook on New Political Economy, M. Holler, H. Kliemt, D. Schmidtchen, and M. Streit (Eds.).Google Scholar
- K. Matulef, R. O'Donnell, R. Rubinfeld, and R. Servedio. 2010. Testing halfspaces. SIAM J. Comput. 39, 5, 2004--2047. Google ScholarDigital Library
- S. Muroga, I. Toda, and M. Kondo. 1962. Majority decision functions of up to six variables. Math. Comput. 16, 459--472.Google ScholarCross Ref
- S. Muroga, T. Tsuboi, and C. R. Baugh. 1967. Enumeration of threshold functions of eight variables. Tech. Rep. 245. Univ. Illinois, Urbana.Google Scholar
- A. M. Odlyzko. 1988. On subspaces spanned by random selections of ± 1 vectors. J. Comb. Theory, Ser. A 47, 1, 124--133. Google ScholarDigital Library
- R. O'Donnell and R. Servedio. 2011. The Chow parameters problem. SIAM J. Comput. 40, 1, 165--199. Google ScholarDigital Library
- L. S. Penrose. 1946. The elementary statistics of majority voting. J. Roy. Stat. Soc. 109, 1, 53--57.Google ScholarCross Ref
- V. P. Roychowdhury, K.-Y. Siu, A. Orlitsky, and T. Kailath. 1995. Vector analysis of threshold functions. Inf. Computat. 120, 1, 22--31. Google ScholarDigital Library
- R. Servedio. 2007. Every linear threshold function has a low-weight approximator. Comput. Complex. 16, 2, 180--209. Google ScholarDigital Library
- I. S. Shiganov. 1986. Refinement of the upper bound of the constant in the central limit theorem. J. Sov. Math. 2545--2550.Google Scholar
- K. Takamiya and A. Tanaka. 2006. Computational complexity in the design of voting games. Tech. Rep. 653. The Institute of Social and Economic Research, Osaka University.Google Scholar
- M. Tannenbaum. 1961. The establishment of a unique representation for a linearly separable function. Tech. Rep. Lockheed Missiles and Space Co. Threshold Switching Techniques Note 20, 1--5.Google Scholar
- T. Tao and V. H. Vu. 2009. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. Ann. Math. 169, 595--632.Google ScholarCross Ref
- A. Taylor and W. Zwicker. 1992. A characterization of weighted voting. Proc. AMS 115, 4, 1089--1094.Google ScholarCross Ref
- L. Trevisan, M. Tulsiani, and S. P. Vadhan. 2009. Regularity, boosting, and efficiently simulating every high-entropy distribution. In Proceedings of the IEEE Conference on Computational Complexity. 126--136. Google ScholarDigital Library
- R. O. Winder. 1963. Threshold logic in artificial intelligence. In Artificial Intelligence, IEEE Publication S-142, 107--128.Google Scholar
- R. O. Winder. 1964. Threshold functions through n = 7. Tech. Rep. 7. Air Force Cambridge Research Laboratories.Google Scholar
- R. O. Winder. 1969. Threshold gate approximations based on Chow parameters. IEEE Trans. Comput. 372--375. Google ScholarDigital Library
- R. O. Winder. 1971. Chow parameters in threshold logic. J. ACM 18, 2, 265--289. Google ScholarDigital Library
Index Terms
- Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
Recommendations
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'...
Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of ComputingThe degree-d Chow parameters of a Boolean function are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded ...
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingThe 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 ...
Comments