We consider a model (BT) for backtracking algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as interval scheduling, knapsack and satisfiability.

We show that neither resolution nor tree-like resolution is automatizable unless the class W[P] from the hierarchy of parameterized problems is fixed-parameter tractable by randomized algorithms with one-sided error.

We show that, unless NP/spl sube/DTIME(2/sup poly log(n)/) the closest vector problem with pre-processing, for /spl lscr//sub p/ norm for any p /spl ges/ 1, is hard to approximate within a factor of (log n)/sup 1/p - /spl epsi//' /P for any /spl epsi/ > 0. This improves the previous best factor of 3/sup 1/p/ - /spl epsi/ due to Regev (2004). Our results also imply that under the same complexity assumption, the nearest codeword problem with pre-processing is hard to approximate within a factor of (log n)/sup 1 - /spl epsi//' for any /spl epsi/ > 0.

We prove exponential lower bounds for the refutation of a random 3-CNF with linear number of clauses by k-DNF Resolution for k ≤ √ 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 1 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(k2)-CNF do not possess short Res(k) refutations.

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for max-cu , max-3sat, and sparsest cut).We prove strong inapproximability results in this model for well-known problems such as max-3sat, hypergraph vertex cover and set cover. We show that the relaxations produced by as many as Ω(n) rounds of the LS+ procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS+ approach gives even slightly subexponential approximation algorithms for these problems.We also point out why our results are somewhat incomparable to known inapproximability results proved using PCPs, and formalize several interesting open questions.

This paper generalizes the classical Knuth-Schoumlnhage algorithm computing the greatest common divisor (gcd) of two polynomials for solving arbitrary linear Diophantine systems over polynomials in time, quasi-linear in the maximal degree. As an application, the following weighted curve fitting problem is considered: given a set of points in the plane, find an algebraic curve (satisfying certain degree conditions) that goes through each point the prescribed number of times. The main motivation for this problem comes from coding theory, namely, it is ultimately related to the list decoding of Reed-Solomon codes. This paper presents a new fast algorithm for the weighted curve fitting problem, based on the explicit construction of a Groebner basis. This gives another fast algorithm for the soft decoding of Reed-Solomon codes different from the procedure proposed by Feng, which works in time (w/r)O(1)nlog2n, where r is the rate of the code, and w is the maximal weight assigned to a vertical line

We consider the complexity of properly learning concept classes, i.e. when the learner must output a hypothesis of the same form as the unknown concept. We present the following upper and lower bounds on well-known concept classes: 1) We show that unless NP = RP, there is no polynomial-time PAC learning algorithm for DNF formulae where the hypothesis is an OR-of-thresholds. Note that as special cases, we show that neither DNF nor OR-of-thresholds are properly learnable unless NP = RP. Previous hardness results have required strong restrictions on the size of the output DNF formula. We also prove that it is NP-hard to learn the intersection of /spl lscr/ /spl ges/ 2 halfspaces by the intersection of k halfspaces for any constant k > 0. Previous work held for the case when k = /spl lscr/; 2) Assuming that NP /spl nsube/ DTIME(2/sup n/spl epsi//) for a certain constant /spl epsiv/ < 1 we show that it is not possible to learn size s decision trees by size s/sup k/ decision trees for any k /spl ges/ 0. Previous hardness results for learning decision trees held for k /spl les/ 2; 3) We present the first nontrivial upper bounds on properly learning DNF formulae and decision trees. In particular we show how to learn size s DNF by DNF in time 2/sup O~/(/spl radic/(n log s)), and how to learn size s decision trees by decision trees in time n/sup O(log s)/. The hardness results for DNF formulae and intersections of halfspaces are obtained via specialized graph products for amplifying the hardness of approximating the chromatic number as well as applying work on the hardness of approximate hypergraph coloring. The hardness results for decision trees, as well as the upper bounds, are obtained by developing a connection between automatizability in proof complexity and learnability, which may have other applications.

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ hard for a propositional proof system P if P cannot efficiently prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for any string $b\in\{0,1\}^m$. We consider a variety of "combinatorial" pseudorandom generators inspired by the Nisan--Wigderson generator on the one hand, and by the construction of Tseitin tautologies on the other. We prove that under certain circumstances these generators are hard for such proof systems as resolution, polynomial calculus, and polynomial calculus with resolution (PCR).

We consider the problem to determine the maximal number of satisfiable equations in a linear system chosen at random. We make several plausible conjectures about the average case hardness of this problem for some natural distributions on the instances, and relate them to several interesting questions in the theory of approximation algorithms and in cryptography. Namely we show that our conjectures imply the following facts: (1) Feige's hypothesis about the hardness of refuting a random 3CNF is true, which in turn implies inapproximability within a constant for several combinatorial problems, for which no NP-hardness of approximation is known. (2) It is hard to approximate the nearest codeword within factor n/sup 1 - /spl epsi//. (3) It is hard to estimate the rigidity of a matrix. More exactly, it is hard to distinguish between matrices of low rigidity and random ones. (4) There exists a secure public-key (probabilistic) cryptosystem, based on the intractability of decoding of random binary codes. Our conjectures are strong in that they assume cryptographic hardness: no polynomial algorithm can solve the problem on any non-negligible fraction of inputs. Nevertheless, to the best of our knowledge no efficient algorithms are currently known that refute any of our hardness conjectures.

We analyze the efficiency of the random walk algorithm on random 3‐CNF instances and prove linear upper bounds on the running time of this algorithm for small clause density, less than $1.63$. This is the first subexponential upper bound on the running time of a local improvement algorithm on random instances. Our proof introduces a simple, yet powerful tool for analyzing such algorithms, which may be of further use. This object, called a terminator, is a weighted satisfying assignment. We show that any CNF having a good (small weight) terminator is assured to be solved quickly by the random walk algorithm. This raises the natural question of the terminator threshold which is the maximal clause density for which such assignments exist (with high probability). We use the analysis of the pure literal heuristic presented by Broder, Frieze, and Upfal [Proceedings of the Fourth Annual ACM‐SIAM Symposium on Discrete Algorithms, 1993, pp. 322–330] and Luby, Mitzenmacher, and Shokrollahi [Proceedings of the Ninth Annual ACM‐SIAM Symposium on Discrete Algorithms, 1998, pp. 364–373] and show that for small clause densities good terminators exist. Thus we show that the pure literal threshold ($\approx$1.63) is a lower bound on the terminator threshold. (We conjecture the terminator threshold to be in fact higher.) One nice property of terminators is that they can be found efficiently via linear programming. This makes tractable the future investigation of the terminator threshold and also provides an efficiently computable certificate for short running time of the simple random walk heuristic.

We generalize the classical Knuth-Schonhage algorithm computing GCD of two polynomials for solving arbitrary linear Diophantine systems over polynomials in time, quasi-linear in the maximal degree. As an application, we consider the following weighted curve fitting problem: given a set of points in the plain, find an algebraic curve (satisfying certain degree conditions) that goes through each point the prescribed number of times. The main motivation for this problem comes from coding theory, namely it is ultimately related to the list decoding of Reed-Solomon codes. We present a new fast algorithm for the weighted curve fitting problem, based on the explicit construction of Groebner basis. This gives another fast algorithm for soft-decoding of Reed-Solomon codes different from the procedure proposed by Feng (1999), which works in time (w/r)/sup O(1)/ n log/sup 2/ n loglogn, where r is the rate of the code, and w is the maximal weight assigned to a vertical line.

For a CNF /spl tau/, let w/sub b/(/spl tau/) be the branch-width of its underlying hypergraph. In this paper we design an algorithm for solving SAT in time n/sup O(1)/2/sup O(w(b)(/spl tau/))/. This in particular implies a polynomial algorithm for testing satisfiability on instances with tree-width O(log n). Our algorithm is a modification of the width based automated theorem prover (WBATP) which is a popular (at least on the theoretical level) heuristic for finding resolution refutations of unsatisfiable CNFs. We show that instead of the exhaustive enumeration of all provable clauses, one can do a better search based on the Robertson-Seymour algorithm for approximating the branch-width of a graph. We call the resulting procedure Branch-Width Based Automated Theorem Prover (BWBATP). As opposed to WBATP, it always produces regular refutations. Perhaps more importantly, the running time of our algorithm is bounded in terms of a clean combinatorial characteristic that can be efficiently approximated, and that the algorithm also produces, within the same time, a satisfying assignment if /spl tau/ happens to be satisfiable. In the second part of the paper we investigate the behavior of BWBATP on the Well-studied class of Tseitin tautologies. We argue that in this case BWBATP is better than WBATP. Namely, we show that its running time on any Tseitin tautology /spl tau/ is |/spl tau/|/sup O(1)/. 2/sup O(w(/spl tau//spl boxvr/O))/ as opposed to the obvious bound n/sup O(w(/spl tau//spl boxvr/O))/ provided by WBATP. This in particular implies that Resolution is automatizable on those Tseitin tautologies for which we know the relation w(/spl tau//spl boxvr//spl phi/) /spl les/ O(log S(/spl tau/)). We identify one such subclass and prove partial results toward establishing this relation for larger classes of graphs.

Two distinct proofs of an exponential separation between regular resolution and unrestricted resolution are given. The previous best known separation between these systems was quasi-polynomial.

We study space complexity in the framework of propositional proofs. We consider a natural model analogous to Turing machines with a read-only input tape and such popular propositional proof systems as resolution, polynomial calculus, and Frege systems. We propose two different space measures, corresponding to the maximal number of bits, and clauses/monomials that need to be kept in the memory simultaneously. We prove a number of lower and upper bounds in these models, as well as some structural results concerning the clause space for resolution and Frege systems.

We generalize recent linear lower bounds for Polynomial Calculus based on binomial ideals. We produce a general hardness criterion (that we call immunity) which is satisfied by a random function and prove linear lower bounds on the degree of PC refutations for a wide class of tautologies based on immune functions. As some applications of our techniques, we introduce mod/sub p/ Tseitin tautologies in the Boolean case (e.g. in the presence of axioms x/sub i//sup 2/=x/sub i/), prove that they are hard for PC over fields with characteristic different from p, and generalize them to Flow tautologies which are based on the MAJORITY function and are proved to be hard over any field. We also show the /spl Omega/(n) lower bound for random k-CNFs over fields of characteristic 2.

We show that neither Resolution nor tree-like Resolution is automatizable unless the class W[P] from the hierarchy of parameterized problems is fixed-parameter tractable by randomized algorithms with one-sided error.

Abstract We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within a factor of . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution. Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs.

We call a pseudorandom generator G/sub n/:{0,1}/sup n//spl rarr/{0,1}/sup m/ hard for a propositional proof system P if P can not efficiently prove the (properly encoded) statement G/sub n/(x/sub 1/,...,x/sub n/)/spl ne/b for any string b/spl epsiv/{0,1}/sup m/. We consider a variety of "combinatorial" pseudorandom generators inspired by the Nisan-Wigderson generator on one hand, and by the construction of Tseitin tautologies on the other. We prove that under certain circumstances these generators are hard for such proof systems as resolution, polynomial calculus and polynomial calculus with resolution (PCR).