Upper and Lower Bounds for Selection on the Mesh

A distance-optimal algorithm for selection on the mesh has proved to be elusive, although distance-optimal algorithms for the related problems of routing and sorting have recently been discovered. In this paper we explain, using the notion of adaptiveness, why techniques used in the currently best selection algorithms cannot lead to a distance-optimal algorithm. For worst-case inputs we apply new techniques to improve the previous best upper bound of 1.22n of Kaklamanis et al. [7] to 1.15n . This improvement is obtained in part by increasing the adaptiveness of previous algorithms. Received May 25, 1995; revised June 1, 1996.     

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/c^d(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator.     

Property Testing Lower Bounds via Communication Complexity

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds. For the problem of testing whether a Boolean function is k-linear (a parity function on k variables), we achieve a lower bound of ??(k) queries, even for adaptive algorithms with two-sided error, thus confirming a conjecture of Goldreich (2010a). The same argument behind this lower bound also implies a new proof of known lower bounds for testing related classes such as k-juntas. For some classes, such as the class of monotone functions and the class of s-sparse GF(2) polynomials, we significantly strengthen the best known bounds.     

Lower and Upper Bounds for Linkage Discovery

For a real-valued function f defined on {0,1}n , the linkage graph of f is a hypergraph that represents the interactions among the input variables with respect to f . In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove that O(n ²logn) function evaluations are enough for bounded functions when the number of hyperedges is O(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients.     

Lower Bounds for Runtime Complexity of Term Rewriting

We present the first approach to deduce lower bounds for (worst-case) runtime complexity of term rewrite systems (TRSs) automatically. Inferring lower runtime bounds is useful to detect bugs and to complement existing methods that compute upper complexity bounds. Our approach is based on two techniques: the induction technique generates suitable families of rewrite sequences and uses induction proofs to find a relation between the length of a rewrite sequence and the size of the first term in the sequence. The loop detection technique searches for “decreasing loops”. Decreasing loops generalize the notion of loops for TRSs, and allow us to detect families of rewrite sequences with linear, exponential, or infinite length. We implemented our approach in the tool AProVE and evaluated it by extensive experiments.     

Lower Bounds for k-DNF Resolution on Random 3-CNFs

We prove exponential lower bounds on refutations of a random 3-CNF with linear number of clauses by k-DNF Resolution for ${k\leq \sqrt{\log n/\log\log n}}$ . For this we design a specially tailored random restrictions that preserve the structure of the input random 3-CNF while mapping every k-DNF with large covering number to one with high probability. Next we make use of the switching lemma for small restrictions by Segerlind, Buss and Impagliazzo to prove the lower bound. This work improves the previously known lower bound for Res(2) system on random 3-CNFs by Atserias, Bonet and Esteban and the result of Segerlind, Buss, Impagliazzo stating that random O(k ²)-CNF do not possess short Res(k) refutations.     

Upper and Lower Bounds on the Learning Curve for Gaussian Processes

In this paper we introduce and illustrate non-trivial upper and lower bounds on the learning curves for one-dimensional Guassian Processes. The analysis is carried out emphasising the effects induced on the bounds by the smoothness of the random process described by the Modified Bessel and the Squared Exponential covariance functions. We present an explanation of the early, linearly-decreasing behavior of the learning curves and the bounds as well as a study of the asymptotic behavior of the curves. The effects of the noise level and the lengthscale on the tightness of the bounds are also discussed.     

Solving Mixed and Conditional Constraint Satisfaction Problems

Constraints are a powerful general paradigm for representing knowledge in intelligent systems. The standard constraint satisfaction paradigm involves variables over a discrete value domain and constraints which restrict the solutions to allowed value combinations. This standard paradigm is inapplicable to problems which are either:(a) mixed, involving both numeric and discrete variables, or(b) conditional,¹ containing variables whose existence depends on the values chosen for other variables, or(c) both, conditional and mixed.We present a general formalism which handles both exceptions in an integral search framework. We solve conditional problems by analyzing dependencies between constraints that enable us to directly compute all possible configurations of the CSP rather than discovering them during search. For mixed problems, we present an enumeration scheme that integrates numeric variables with discrete ones in a single search process. Both techniques take advantage of enhanced propagation rule for numeric variables that results in tighter labelings than the algorithms commonly used. From real world examples in configuration and design, we identify several types of mixed constraints, i.e. constraints defined over numeric and discrete variables, and propose new propagation rules in order to take advantage of these constraints during problem solving.     

约束满足问题的预处理方法研究

搜索控制问题是大多数人工智能问题求解面临的一个根本间题,而约束满足是解决这一问题的常用方法之一它源于机器视觉领域中的情景标识任务,如今在人工智能的众多领域(如规划、调度、时序推理)中获得了广泛的应用,受到了人工智能界的高度重视.在近几期的UCAI和AAAI等国际人工智能会议上这方面的内容均占有一定的比重,《A币ficial In-telligence》杂志曾于1992年出了一期约束满足问题的专辑     

Symmetry Definitions for Constraint Satisfaction Problems

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.     

Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

The determinantal complexity of a polynomial f(x ₁,x ₂,…,x _n ) is the minimum m such that f=det  _m (L(x ₁,x ₂,…,x _n )), where L(x ₁,x ₂,…,x _n ) is a matrix whose entries are affine forms in the x _i s over some field $\mbox {$\mbox {.     

Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

Hardness amplification results show that for every Boolean function f, there exists a Boolean function Amp(f) such that if every size s circuit computes f correctly on at most a 1 ? δ fraction of inputs, then every size s′ circuit computes Amp(f) correctly on at most a ${1/2+\epsilon}$ fraction of inputs. All hardness amplification results in the literature suffer from “size loss” meaning that ${s' \leq \epsilon \cdot s}$ . We show that proofs using “non-uniform reductions” must suffer from such size loss. A reduction is an oracle circuit ${R^{(\cdot)}}$ which given oracle access to any function D that computes Amp(f) correctly on a ${1/2+\epsilon}$ fraction of inputs, computes f correctly on a 1 ? δ fraction of inputs. A non-uniform reduction is allowed to also receive a short advice string that may depend on both f and D. The well-known connection between hardness amplification and list-decodable error-correcting codes implies that reductions showing hardness amplification cannot be uniform for ${\epsilon < 1/4}$ . We show that every non-uniform reduction must make at least ${\Omega(1/\epsilon)}$ queries to its oracle, which implies size loss. Our result is the first lower bound that applies to non-uniform reductions that are adaptive, whereas previous bounds by Shaltiel & Viola (SICOMP 2010) applied only to non-adaptive reductions. We also prove similar bounds for a stronger notion of “function-specific” reductions in which the reduction is only required to work for a specific function f.     

Lower and Upper Bounds on FIFO Buffer Management in QoS Switches

We consider the management of FIFO buffers for network switches providing differentiated services. In each time step, an arbitrary number of packets arrive and only one packet can be sent. The buffer can store a limited number of packets and, due to the FIFO property, the sequence of sent packets has to be a subsequence of the arriving packets. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy can drop packets, and the goal is to maximize the sum of the values of sent packets. For only two different packet values, we introduce the account strategy and prove that this strategy achieves an optimal competitive ratio of if the buffer size tends to infinity and an optimal competitive ratio of for arbitrary buffer sizes. For general packet values, the simple preemptive greedy strategy (PG) is studied. We show that PG achieves a competitive ratio of which is the best known upper bound on the competitive ratio of this problem. In addition, we give a lower bound of on the competitive ratio of PG which improves the previously known lower bound. As a consequence, the competitive ratio of PG cannot be further improved significantly. Supported by the DFG grant WE 2842/1. A preliminary version of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms (ESA), 2006.     

Lower Bounds for Dynamic Algebraic Problems

We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x₁,…, x_n)=(y₁, …, y_m) is an algebraic problem, we consider serving online requests of the form “change input x_i to value v” or “what is the value of output y_i?” We present techniques for showing lower bounds on the worst case time complexity per operation for such problems. The first gives lower bounds in a wide range of rather powerful models (for instance, history dependent algebraic computation trees over any infinite subset of a field, the integer RAM, and the generalized real RAM model of Ben-Amram and Galil). Using this technique, we show optimal Ω(n) bounds for dynamic matrix–vector product, dynamic matrix multiplication, and dynamic discriminant and an Ω( ) lower bound for dynamic polynomial multiplication (convolution), providing a good match with Reif and Tate's O( ) upper bound. We also show linear lower bounds for dynamic determinant, matrix adjoint, and matrix inverse and an Ω( ) lower bound for the elementary symmetric functions. The second technique is the communication complexity technique of Miltersen, Nisan, Safra, and Wigderson which we apply to the setting of dynamic algebraic problems, obtaining similar lower bounds in the word RAM model. The third technique gives lower bounds in the weaker straight line program model. Using this technique, we show an Ω((log n)²/log log n) lower bound for dynamic discrete Fourier transform. Technical ingredients of our techniques are the incompressibility technique of Ben-Amram and Galil and the lower bound for depth-two superconcentrators of Radhakrishnan and Ta-Shma. The incompressibility technique is extended to arithmetic computation in arbitrary fields.     

Non-Asymptotic Lower Bounds for the Data Complexity of Statistical Attacks on Symmetric Cryptosystems

A method is proposed for obtaining the lower bounds of data complexity of statistical attacks on block or stream ciphers. The method is based on the Fano inequality and, unlike the available methods, doesn’t use any asymptotic relations, approximate formulas or heuristic assumptions about the considered cipher. For a lot of known types of attacks, the obtained data complexity bounds have the classical form. For other types of attacks, these bounds allow us to introduce reasonable parameters that characterize the security of symmetric cryptosystems against these attacks.     

Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems

We study the runtime distributions of backtrack procedures for propositional satisfiability and constraint satisfaction. Such procedures often exhibit a large variability in performance. Our study reveals some intriguing properties of such distributions: They are often characterized by very long tails or heavy tails. We will show that these distributions are best characterized by a general class of distributions that can have infinite moments (i.e., an infinite mean, variance, etc.). Such nonstandard distributions have recently been observed in areas as diverse as economics, statistical physics, and geophysics. They are closely related to fractal phenomena, whose study was introduced by Mandelbrot. We also show how random restarts can effectively eliminate heavy-tailed behavior. Furthermore, for harder problem instances, we observe long tails on the left-hand side of the distribution, which is indicative of a non-negligible fraction of relatively short, successful runs. A rapid restart strategy eliminates heavy-tailed behavior and takes advantage of short runs, significantly reducing expected solution time. We demonstrate speedups of up to two orders of magnitude on SAT and CSP encodings of hard problems in planning, scheduling, and circuit synthesis.     

Periodic Constraint Satisfaction Problems: Tractable Subclasses

We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of generating constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints; the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.     

Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution

We work with an extension of Resolution, called Res(2), that allows clauses with conjunctions of two literals. In this system there are rules to introduce and eliminate such conjunctions. We prove that the weak pigeonhole principle PHP^cn_n and random unsatisfiable CNF formulas require exponential-size proofs in this system. This is the strongest system beyond Resolution for which such lower bounds are known. As a consequence to the result about the weak pigeonhole principle, Res(log) is exponentially more powerful than Res(2). Also we prove that Resolution cannot polynomially simulate Res(2) and that Res(2) does not have feasible monotone interpolation solving an open problem posed by Krají ek.