Reviewing bounds on the circuit size of the hardest functions

In this paper we review the known bounds for L(n), the circuit size complexity of the hardest Boolean function on n input bits. The best known bounds appear to be

     

The size and depth of layered Boolean circuits

We consider the relationship between size and depth for layered Boolean circuits and synchronous circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth . For synchronous circuits of size s, we obtain simulations of depth . The best known result so far was by Paterson and Valiant (1976) [17], and Dymond and Tompa (1985) [6], which holds for general Boolean circuits and states that , where C(f) and D(f) are the minimum size and depth, respectively, of Boolean circuits computing f. The proof of our main result uses an adaptive strategy based on the two-person pebble game introduced by Dymond and Tompa (1985) [6]. Improving any of our results by polylog factors would immediately improve the bounds for general circuits.     

A tighter upper bound for random MAX 2-SAT

Given a conjunctive normal form F with n variables and m=cn 2-clauses, it is interesting to study the maximum number of clauses satisfied by all the assignments of the variables (MAX 2-SAT). When c is sufficiently large, the upper bound of of random MAX 2-SAT had been derived by the first-moment argument. In this paper, we provide a tighter upper bound (3/4)cn+g(c)cn also using the first-moment argument but correcting the error items for f(n,cn), and when considering the ε³ error item. Furthermore, we extrapolate the region of the validity of the first-moment method is c>2.4094 by analyzing the higher order error items.     

Testing juntas

We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the approximation parameter ε. We present several tests that require a number of queries that is polynomial in J and linear in ε⁻¹. We show a non-adaptive test that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over n boolean variables, and has a more compact analysis.We then provide a lower bound of on the number of queries required for the non-adaptive testing of the above property; a lower bound of for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group Z^q₂ that may be interesting in its own right. We show that for some , the distributions of the random walk at times t and t+2 are close to each other, independently of the step distribution of the walk.We also discuss related questions. In particular, when given in advance a known J-junta function , we show how to test a function for the property of being identical to up to a permutation of the variables, in a number of queries that is polynomial in J and ε⁻¹.     

Eigen-distribution on random assignments for game trees

In this Letter, we investigate a special distribution, called eigen-distribution, on random assignments for a class of game trees . There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In the ID case, we prove that the distributional probability ? belongs to , and ? is a strictly increasing function on rounds k∈[1,∞). In the CD case, we propose a reverse assigning technique (RAT) to form two particular sets of assignments, 1-set and 0-set, then show that the E¹-distribution (namely, a particular distribution on the assignments of 1-set such that all the deterministic algorithms have the same complexity) is the unique eigen-distribution for in the global distribution.     

Upper bound for algebraic immunity on a subclass of Maiorana McFarland class of bent functions

Studying algebraic immunity of Boolean functions is recently a very important research topic in cryptography. It is recently proved by Courtois and Meier that for any Boolean function of n-variable the maximum algebraic immunity is . We found a large subclass of Maiorana McFarland bent functions on n-variable with a proven low level of algebraic immunity . To the best of our knowledge we provide for the first time a new upper bound for algebraic immunity for a nontrivial class of Boolean functions. We also discuss that this result has some fascinating implications.     

A nondeterministic space-time tradeoff for linear codes

We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k²². We prove an exponential lower bound ²Ω(n/ck) for an explicit function over substantially smaller domain D of size about k². Our function is a universal function of linear codes.     

On the lower bounds of the second order nonlinearities of some Boolean functions

The rth order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code R(r,n). In this paper we deduce the lower bounds of the second order nonlinearities of the following two types of Boolean functions:

1.

with d=2^2r+2^r+1 and , where n=6r.

2.

, where x,y∈F_2^t,n=2t,n?6 and i is an integer such that 1?i<t,gcd(2^t-1,2ⁱ+1)=1.

For some λ, the functions of the first type are bent functions, whereas Boolean functions of the second type are all bent functions, i.e., they possess the maximum first order nonlinearity. It is demonstrated that in some cases our bounds are better than the previously obtained bounds.     

On the minimum number of negations leading to super-polynomial savings

We show that an explicit sequence of monotone functions can be computed by Boolean circuits with polynomial (in n) number of And, Or and Not gates, but every such circuit must use at least logn−O(loglogn) Not gates. This is almost optimal because results of Markov [J. ACM 5 (1958) 331] and Fisher [Lecture Notes in Comput. Sci., Vol. 33, Springer, 1974, p. 71] imply that, with only small increase of the total number of gates, any circuit in n variables can be simulated by a circuit with at most ⌈log(n+1)⌉ Not gates.     

Nonadaptive quantum query complexity

We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes a total boolean function depending on n variables must make Ω(n) queries to the input in total. Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using queries to solve the same problem. Thus, in the nonadaptive setting, quantum algorithms for these tasks can achieve at most a very limited speed-up over classical query algorithms.     

Topological formulation of termination properties of iterates of functions

We consider a number of decision problems, that appear in the dynamical systems and database literature, concerning the termination of iterates of real functions. These decision problems take a function as input and ask, for example, whether this function is mortal, nilpotent, terminating, or reaches a fixed point on a given point in . We associate topologies to functions and study some basic properties of these topologies. The contribution of this paper is a translation of the above mentioned decision problems into decision problems concerning well-known properties of topologies, e.g., connectivity. We also show that connectivity of topologies on is undecidable for n>1.     

An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution

We show that halfspaces in n dimensions can be PAC-learned with respect to the uniform distribution with accuracy ε and confidence δ using examples.     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).