waashk/dblp huggingface dataset:
using nondeterminism to amplify hardness. we revisit the problem of hardness amplification in $\mathcal{np}$, as recently studied by o'donnell [j. comput. system sci., 69 (2004), pp. 68-94]. we prove that if $\mathcal{np}$ has a balanced function $f$ such that any circuit of size $s(n)$ fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then $\mathcal{np}$ has a function $f'$ such that any circuit of size $s'(n)=s(\sqrt{n})^{\omega(1)}$ fails to compute $f'$ on a $1/2 - 1/s'(n)$ fraction of inputs. in particular, \begin{enumerate} \item if $s(n)=n^{\omega(1)}$, we amplify to hardness $1/2-1/n^{\omega(1)}$; \item if $s(n)=2^{n^{\omega(1)}}$, we amplify to hardness $1/2-1/2^{n^{\omega(1)}}$; \item if $s(n)=2^{\omega(n)}$, we amplify to hardness $1/2-1/2^{\omega(\sqrt{n})}$. \end{enumerate}our results improve those of of o'donnell, which amplify to $1/2-1/\sqrt{n}$. o'donnell also proved that no construction of a certain general form could amplify beyond $1/2-1/n$. we bypass this barrier by using both derandomization and nondeterminism in the construction of $f'$.we also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that $f$ is balanced are necessary for "black-box" hardness amplification procedures (such as ours).
the pagenumber of genus g graphs is o(g) in 1979, bernhart and kainen conjectured that graphs of fixed genus g &ge; 1 have unbounded pagenumber. in this paper, it is proven that genus g graphs can be embedded in o(g) pages, thus disproving the conjecture. an &ohgr;(g1/2) lower bound is also derived. the first algorithm in the literature for embedding an arbitrary graph in a book with a non-trivial upper bound on the number of pages is presented. first, the algorithm computes the genus g of a graph using the algorithm of filotti, miller, reif (1979), which is polynomial-time for fixed genus. second, it applies an optimal-time algorithm for obtaining an o(g)-page book embedding. separate book embedding algorithms are given for the cases of graphs embedded in orientable and nonorientable surfaces. an important aspect of the construction is a new decomposition theorem, of independent interest, for a graph embedded on a surface. book embedding has application in several areas, two of which are directly related to the results obtained: fault-tolerant vlsi and complexity theory.
flow graph reducibility the structure of programs can often be described by a technique called &ldquo;interval analysis&rdquo; on their flow graphs. here, we characterize the set of flow graphs that can be analyzed in this way in terms of two very simple transformation on graphs. we then give a necessary and sufficient condition for analyzability and apply it to &ldquo;goto-less programs,&rdquo; showing that they all meet the criterion.
a polynomial linear search algorithm for the n-dimensional knapsack problem we present a linear search algorithm which decides the n-dimensional knapsack problem in n4log(n) + 0.(n3) steps. this algorithm works for inputs consisting of n numbers for some arbitrary but fixed integer n. this result solves an open problem posed for example in [6] and [7] by dobkin / lipton and a.c.c. yao, resp.. it destroys the hope of proving large lower bounds for this np-complete problem in the model of linear search algorithms.
fast algorithms for n-dimensional restrictions of hard problems let m be a parallel ram with p processors and arithmetic operations addition and subtraction recognizing l &sub; nn in t steps. (inputs for m are given integer by integer, not bit by bit.) then l can be recognized by a (sequential) linear search algorithm (lsa) in o(n4(log(n) + t + log(p))) steps. thus many n-dimensional restrictions of np-complete problems (binary programming, traveling salesman problem, etc.) and even that of the uniquely optimum traveling salesman problem, which is &dgr;p2-complete, can be solved in polynomial time by an lsa. this result generalizes the construction of a polynomial lsa for the n-dimensional restriction of the knapsack problem previously shown by the author, and destroys the hope of proving nonpolynomial lower bounds on lsas for any problem that can be recognized by a pram as above with 2poly(n) processors in poly(n) time.
testing polynomials which are easy to compute (extended abstract) we exploit the fact that the set of all polynomials p&egr;@@@@[x1,..,xn] of degree &le;d which can be evaluated with &le;v nonscalar steps can be embedded into a zariski-closed affine set w(d,n,v),dim w(d,n,v)&le;(v+1 +n)2 and deg w(d,n,v)&le;(2vd)(v+1+n)2. as a consequence we prove that for u:&equil; 2v(d+1)2 and s:&equil; 6(v+1+n)2 there exist &abarbelow;1,..,&abarbelow;s&egr; [u]n &equil; {1,2,..,u}n such that for all polynomials p&egr;w(d,n,v):p(&abarbelow;1) &equil; p(&abarbelow;2) &equil;...&equil; p(&abarbelow;s) &equil; o implies p&xgr;o. this means that &abarbelow;1,...,&abarbelow;s is a correct test sequence for a zero test on all polynomials in w(d,n,v). moreover, &ldquo;almost every&rdquo; sequence &abarbelow;1,..,&abarbelow;s&egr;[u]n is such a correct test sequence for w(d,n,v). the existence of correct test sequences &abarbelow;1,..,&abarbelow;s&egr; [u]n is established by a counting argument without constructing a correct test sequence. we even show that it is beyond the known methods to establish (i.e. to construct and to prove correctness) of such a short correct test sequence for w(d,n,v). we prove that given such a short, correct test sequence for w(d,n,v) we can efficiently construct a multivariate polynomial p&egr;@@@@[x1,..,xn] with deg(p) &equil; d and small integer coefficients such that p@@@@ w(d,n,v). for v>n log d lower bounds of this type are beyond our present methods in algebraic complexity theory.
how many queries are needed to learn? we investigate the query complexity of exact learning in the membership and (proper) equivalence query model. we give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. we give applications of this characterization, including results on learning a natural subclass of dnf formulas, and on learning with membership queries alone. query complexity has previously been used to prove lower bounds on the time complexity of exact learning. we show a new relationship between query complexity and time complexity in exact learning: if any &ldquo;honest&rdquo; class is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then p = np. in particular, we show that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for &ggr;p4.
exact learning of dnf formulas using dnf hypotheses. we show the following: (a) for any @e>0, log^(^3^+^@e^)n-term dnf cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) for sufficiently large t, t-term dnf formulas cannot be polynomial-query learned with membership and equivalence queries that use t^1^+^@e-term dnf formulas as hypotheses, for some @e
the strong exponential hierarchy collapses the polynomial hierarchy, composed of the levels p, np, pnp, npnp, etc., plays a central role in classifying the complexity of feasible computations. it is not known whether the polynomial hierarchy collapses. we resolve the question of collapse for an exponential-time analogue of the polynomial-time hierarchy. composed of the levels e (i.e., &cup;c dtime[2cn]), ne, pne, npne, etc., the strong exponential hierarchy collapses to its &dgr;2 level. e &ne; pne = npne &cup; npnpne &cup; &middot;&middot;&middot; our proof stresses the use of partial census information and the exploitation of nondeterminism. extending our techniques, we also derive new quantitative relativization results. we show that if the (weak) exponential hierarchy's &dgr;j+1 and &sgr;j+1 levels, respectively e&sgr;pj and ne&sgr;pj, do separate, this is due to the large number of queries ne makes to its &sgr;pj database.1 our technique provide a successful method of proving the collapse of certain complexity classes.
parameter-passing mechanisms and nondeterminism the problem of defining an adequate semantics for recursive definitions which allow various types of parameter-passing mechanisms has generated a considerable amount of interest in the literature. (see [b1], [m4], [r3], [v2]) consider for example the well-known recursive definition f <x, y> <&equil; if x&equil;0 then 0 else f<x&minus;1,f<x, y>>. interpreted as a fixpoint equation over the flat cpo of non-negative integers it has as its least solution f(x, y) = 0 if x&equil;m for any non-negative integer m &equil; @@@@ otherwise (&ldquo;@@@@&rdquo; means undefined) this also happens to coincide with the computed function if a call-by-name (or outside-in) evaluation mechanism is used. however if a call-by-value (or inside-out) evaluation mechanism is used the computed function is fv (x, y) &equil; 0 if x&equil;0 &equil; @@@@ otherwise in [vl] the conclusion is drawn that the call-by-value evaluation mechanism is incorrect and should not be considered.
what's decidable about hybrid automata? hybrid automata model systems with both digital and analog components, such as embedded control programs. many verification tasks for such programs can be expressed as reachability problems for hybrid automata. by improving on previous decidability and undecidability results, we identify the precise boundary between decidability and undecidability of the reachability problem for hybrid automata. on the positive side, we give an (optimal) pspace reachability algorithm for the case of initialized rectangular automata, where all analog variables follow trajectories within piecewise-linear envelopes and are reinitialized whenever the envelope changes. our algorithm is based on the construction of a timed automaton that contains all reachability information about a given initialized rectangular automaton. the translation has practical significance for verification, because it guarantees the termination of symbolic procedures for the reachability analysis of initialized rectangular automata. the translation also preserves the $\omega$-languages of initialized rectangular automata with bounded nondeterminism. on the negative side, we show that several slight generalizations of initialized rectangular automata lead to an undecidable reachability problem. in particular, we prove that the reachability problem is undecidable for timed automata augmented with a single stopwatch.
computability over arbitrary fields in most attempts to make precise the concept of a computable function, or decidable predicate, over a field f, it is considered necessary that the elements of f should be in some sense effectively describable, and hence that f itself should be countable. this is the attitude taken in the study of computable fields (see rabin1). our proposed definition of computability over arbitrary fields is based on the shepherdson - sturgis2 concept of an unlimited register machine.
matrix searching with the shortest path metric. we present an o(n) time algorithm for computing row-wise maxima or minima of an implicit, totally monotone $n \times n$ matrix whose entries represent shortest-path distances between pairs of vertices in a simple polygon. we apply this result to derive improved algorithms for several well-known problems in computational geometry. most prominently, we obtain linear-time algorithms for computing the geodesic diameter, all farthest neighbors, and external farthest neighbors of a simple polygon, improving the previous best result by a factor of o(log n) in each case.
parallel algorithms for the transitive closure and the connected component problems parallel programs are presented that determine the transitive closure of a matrix using n3 processors and connected components of an undirected graph using n2 processors. in both cases, the desired results are obtained in time 0(log2n). it is assumed that the processors have access to common memory. simultaneous access to the same location is permitted for fetch, but not store, instructions. the problem of determining the connected components of a graph using a parallel computer has recently appeared in the literature [1,2]. the result in [1] is based on finding the transitive closure of a matrix in time 0(log2n) which can be done using 0(n3) processors. we show that n2 processors are sufficient to solve the connected component problem in time 0(log2n). we present algorithm closure that will find the transitive closure of boolean matrix m [n by n] using n3 processors [numbered p(0,0,0) through p(n&minus;1 ,n&minus;1, n&minus;1)] each of which has local memory and each of which can access common array a [n by n].
powers of graphs: a powerful approximation technique for bottleneck problems in this paper we investigate a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of np-complete problems in routing, location, and communication network design. each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. in addition, for several of these problems we can show that unless p&eqil;np, there does not exist a polynomial-time algorithm that has a better performance guarantee.
the logical complexity of geometric properties in the plane this paper studies the logical complexity of geometric properties in the plane. these properties are characterized according to the length of formulas necessary to express them. in this study a portion of the plane x will be considered as a collection of squares {x1, ..., xn} arranged into a fine grid. a pattern p is a subset of x and the grid is assumed to be fine enough so that approximations to geometrical figures can be obtained. p can be defined by mapping m: x &ran;{0,1} where for x &egr; x, m(x) &equil; 1 iff x &egr; p. a set of patterns or a geometrical property &rgr; can be expressed as a boolean function f on the n variables x1, ..., xn such that the value of f is 1 under the assignment m iff p &egr; &rgr.
testing isomorphism on cone graphs (extended abstract) we give algorithms to decide graph isomorphism in a subclass of graphs which we call cone graphs. a cone graph is an undirected graph for which there exists a vertex r which uniquely determines a breadth-first search (bfs) tree. equivalently, all shortest paths from r to any other graph vertex are unique. our algorithms may be used either nondeterministically or probabilistically. used as probabilistic algorithms, they return always a correct answer, but with an expected running time only.
key agreement from weak bit agreement. assume that alice and bob, given an authentic channel, have a protocol where they end up with a bit sa and sb, respectively, such that with probability 1+ε/2 these bits are equal. further assume that conditioned on the event sa =n sb no polynomial time bounded algorithm can predict the bit better than with probability 1-δ/2. is it possible to obtain key agreement from such a primitive? we show that for constant δ and ε the answer is yes if and only if δ > 1-ε/1+ε, both for uniform and non-uniform adversaries.the main computational technique used in this paper is a strengthening of impagliazzo's hard-core lemma to the uniform case and to a set size parameter which is tight (i.e., twice the original size). this may be of independent interest.
poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. assuming that we start with no edges in a graph with n vertices, the amortized operation costs are o(log2 n) for connectivity, o(log4 n) for minimum spanning forest, 2-edge connectivity, and o(log5 n) biconnectivity.
a new pcp outer verifier with applications to homogeneous linear equations and max-bisection. we show an optimal hardness result for the following problem: given a system of homogeneous linear equations over gf(2) with 3 variables per equation, find a balanced assignment that satisfies maximum number of equations. for arbitrarily small constant ζ > 0, we show that it is hard to determine (in polynomial time) whether such a system has a balanced assignment that satisfies 1-ζ fraction of equations or there is no balanced assignment that satisfies more than ½+ζ fraction of equations. as a corollary, we show that it is hard to approximate (in polynomial time) the max-bisection problem within factor 16⁄15-ζ. these hardness results hold under the assumption np ⊈ ∩ε > 0 dtime(2nε).our results are obtained via a construction of a new pcp outer verifier that has a mixing property and a smoothness property. these properties are crucial in the analysis of the inner verifier. no previous outer verifier can achieve both these properties simultaneously. an outer verifier is essentially a 2-query pcp over a large alphabet. loosely speaking, the mixing property says that the locations of the two queries read by the verifier are uncorrelated. the smoothness property says that the verifier's acceptance predicate is close to being a bijective predicate. our construction relies on the algebraic techniques used to prove the pcp theorem. this is in contrast with all earlier constructions that use the pcp theorem as a black-box. the progress in inapproximability theory seems to require new ideas for building outer verifiers and our construction takes a first step in that direction.
notes on merging networks (preliminary version) several new results which contribute to the understanding of parallel merging networks are presented. first, a simple new explanation of the operation of batcher's merging networks is offered. this view leads to the derivation of a modified version of batcher's odd-even (m, n) network which has delay time [log(m+n)]. this is the same delay time as batcher's bitonic (m, n) network, but it is achieved with substantially fewer comparators. second, a correspondence is demonstrated between the number of comparators (and the delay time) for such networks and certain properties of binary number systems which have recently been extensively studied. third, the [log(m + n)] delay time is shown to be optimal for a non-degenerate range of values of m and n.
duality applied to the complexity of matrix multiplications and other bilinear forms the paper considers the complexity of bilinear forms in a noncommutative ring. the dual of a computation is defined and applied to matrix multiplication and other bilinear forms. it is shown that the dual of an optimal computation gives an optimal computation for a dual problem. an nxm by mxp matrix product is shown to be the dual of an nxp by pxm or an mxn by nxp matrix product implying that each of the matrix products requires the same number of multiplications to compute. finally an algorithm for computing a single bilinear form over a noncommutative ring with a minimum number of multiplications is derived by considering a dual problem.
linear time algorithm for isomorphism of planar graphs (preliminary report) the isomorphism problem for graphs g1 and g2 is to determine if there exists a one-to-one mapping of the vertices of g1 onto the vertices of g2 such that two vertices of g1 are adjacent if and only if their images in g2 are adjacent. in addition to determining the existence of such an isomorphism, it is useful to be able to produce an isomorphism-inducing mapping in the case where one exists. the isomorphism problem for triconnected planar graphs is particularly simple since a triconnected planar graph has a unique embedding on a sphere [6]. weinberg [5] exploited this fact in developing an algorithm for testing isomorphism of triconnected planar graphs in o(|v|2) time where v is the set consisting of the vertices of both graphs. the result has been extended to arbitrary planar graphs and improved to o(|v|log|v|) steps by hopcroft and tarjan [2,3]. in this paper, the time bound for planar graph isomorphism is improved to o(|v|). in addition to determining the isomorphism of two planar graphs, the algorithm can be easily extended to partition a set of planar graphs into equivalence classes of isomorphic graphs in time linear in the total number of vertices in all graphs in the set. a random access model of computation (see cook [1]) is assumed. although the proposed algorithm has a linear asymptotic growth rate, at the present stage of development it appears to be inefficient on account of a rather large constant. this paper is intended only to establish the existence of a linear algorithm which subsequent work might make truly efficient.
algorithms for rational function arithmetic operations despite recent advances in speeding up many arithmetic and algebraic algorithms plus a general increase in algorithm analyses, no computing time study has ever been done for algorithms which perform the rational function arithmetic operations. mathematical symbol manipulation systems which provide for operations on rational functions use algorithms which were initially given by p. henrici in 1956. in this paper, these algorithms are precisely specified and their computing times analyzed. then, new algorithms based on the use of modular arithmetic are developed and analyzed. it is shown that the computing time for adding and taking the derivative of rational functions is 2 orders of magnitude faster using the modular algorithms. also, the computing time for rational function multiplication will be one order of magnitude faster using the modular algorithm.
efficient stable sorting with minimal extra space in his chapter on sorting, knuth [1]@@@@ describes the open problem of stable sorting with no more than 0(log2n) bits of extra space and less than 0(n2) computation time. in this paper we define the concept of a contiguent and show that a contiguent forming algorithm may be used as the basis for a stable sort. a class of such contiguent forming algorithm may be used as the basis for a stable sort. a class of such contiguent forming algorithms is described, the most naive of which requires 0(log n) bits of extra space and 0(n log2n) computation time. we also describe a stable merging algorithm which requires 0(n) time and 0(log n) bits of extra space, but which is not applicable to all cases. it is shown, however, that this merge may be combined with a contiguent compilation algorithm to yield a generally applicable stable sorting algorithm. one such combination provides the basis for a stable sorting algorithm which requires 0(n.logn.g(n)) time and 0(log n) bits of extra space. another such combination provides the basis for a stable sorting algorithm which requires 0(n log n) time and 0(log2n) bits of extra space.