Article Free Access Share on A lower bound for randomized algebraic decision trees Authors: Dima Grigoriev Dept. of Computer Science and Mathematics, Penn State University, University Park Dept. of Computer Science and Mathematics, Penn State University, University ParkView Profile , Marek Karpinski Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile , Friedhelm Meyer auf der Heide Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 Paderborn Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 PaderbornView Profile , Roman Smolensky Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 612–619https://doi.org/10.1145/237814.238011Published:01 July 1996Publication History 12citation385DownloadsMetricsTotal Citations12Total Downloads385Last 12 Months13Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In the first part of the paper we show that a subset S of a boolean cube B/sub n/ embedded in the projective space P/sup n/ can be approximated by a subset of B/sub n/ defined by nonzeroes of a low-degree polynomial only if the values of the Hilbert function of S are sufficiently small relative to the size of S. The use of this property provides a simple and direct technique for proving lower bounds on the size of ACC[p/sup r/] circuits. In the second part we look at the problem of computing many-output function by ACC[p/sup r/] circuit and give an example when such a circuit can be correct only at exponentially small fraction of assignments.>

This paper examines the class of polynomial threshold functions using harmonic analysis and applies the results to derive lower bounds related to $AC^0 $ functions. A Boolean function is polynomial threshold if it can be represented as the sign of a sparse polynomial (one that consists of a polynomial number of terms). The main result of this paper is that the class of polynomial threshold functions can be characterized using their spectral representation. In particular, it is proved that an n-variable Boolean function whose $L_1 $ spectral norm is bounded by a polynomial in n is a polynomial threshold function, while Boolean function whose $L_\infty ^{ - 1} $ spectral norm is not bounded by a polynomial in n is not a polynomial threshold function [J. Bruck, SIAM J. Discrete Math., 3 (1990), pp. 168–177]. The motivation is that the characterization of polynomial threshold functions can be applied to obtain upper and lower bounds on the complexity of computing with networks of linear threshold elements. In this paper results related to the complexity of computing $AC^0 $ functions are presented. More applications of the characterization theorem are presented in [J. Bruck, SIAM J. Discrete Math., 3 (1990), pp. 168–177] and [K. Y. Siu and J. Bruck, SIAM J. Discrete Math., 4 (1991), pp. 423–435].

It is shown that there is a set of points p/sub 1/, p/sub 2/,. . .,p/sub n/ such that any algebraic program of depth d for polynomial evaluation (or interpolation) at these points has size Omega (n log n/log d). Moreover, if d is a constant, then a lower bound of Omega (n/sup 1+1/d/) is obtained.>

The class of polynomial-threshold functions is studied using harmonic analysis, and the results are used to derive lower bounds related to AC/sup 0/ functions. A Boolean function is polynomial threshold if it can be represented as a sign function of a sparse polynomial (one that consists of a polynomial number of terms). The main result is that polynomial-threshold functions can be characterized by means of their spectral representation. In particular, it is proved that a Boolean function whose L/sub 1/ spectral norm is bounded by a polynomial in n is a polynomial-threshold function, and that a Boolean function whose L/sub infinity //sup -1/ spectral norm is not bounded by a polynomial in n is not a polynomial-threshold function. Some results for AC/sup 0/ functions are derived.>

The author investigates the question of whether or not a specific Boolean function in n variables can be interpolated by an analytic function in the same variables whose partial derivatives of all orders span a subspace of low dimension in the space of analytic functions. The upper and lower bounds for this dimension yield some weak circuit lower bounds. For a particular function, an Omega (n/log n)-size lower bound is obtained for its computation by a circuit whose gates are symmetric. For the same function an Omega (n) lower bound is obtained for the circuit with mod/sub k/ gates.>

View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.

We use algebraic methods to get lower bounds for complexity of different functions based on constant depth unbounded fan-in circuits with the given set of basic operations. In particular, we prove that depth k circuits with gates NOT, OR and MODp where p is a prime require Exp(Ο(n1/2k)) gates to calculate MODr functions for any r ≠ pm. This statement contains as special cases Yao's PARITY result [ Ya 85 ] and Razborov's new MAJORITY result [Ra 86] (MODm gate is an oracle which outputs zero, if the number of ones is divisible by m).

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f : {0, 1}n → {0, 1}m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in {0, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f : {0,1}n → {0, 1}m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.