waashk/dblp huggingface dataset:
solvability by radicals is in polynomial time every high school student knows how to express the roots of a quadratic equation in terms of radicals; what is less well-known is that this solution was found by the babylonians a millenia and a half before christ [ne]. three thousand years elapsed before european mathematicians determined how to express the roots of cubic and quartic equations in terms of radicals, and there they stopped, for their techniques did not extend. lagrange published a treatise which discussed why the methods that worked for polynomials of degree less than five did not work for quintic polynomials [lag], they require double exponential time. through the years other mathematicians developed alternate algorithms all of which, however, remained exponential. a major impasse was the problem of factoring polynomials, for until the recent breakthrough of lenstra, lenstra, and lov&aacute;sz [l3], all earlier algorithms had exponential running time. their algorithm, which factors polynomials over the rationals in polynomial time, gave rise to a hope that some of the classical questions of galois theory might have polynomial time solutions. galois transformed the question of solvability by radicals from a problem concerning fields to a problem about groups. what we do is to change the inquiry into several problems concerning the solvability of certain primitive groups.
recursive properties of abstract complexity classes (preliminary version) it is proven that complexity classes of abstract measures of complexity need not be recursively enumerable. however, the complement of each class is r.e. properties of effective enumerations of complexity classes are studied. for any measure there is another measure with 'almost' the same complexity classes such that almost every class admits an effective enumeration in terms of speedy devices. finally complexity classes are shown to not be closed under intersection.
the subgraph homeomorphism problem we investigate the problem of finding a homeomorphic image of a &ldquo;pattern&rdquo; graph h in a larger input graph g. we view this problem as finding specified sets of edge disjoint or node disjoint paths in g. our main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in g; here h is a triangle. no polynomial time algorithm for this problem was previously known. we also discuss a variety of reductions between related versions of this problem and a number of open problems.
location of a point in a planar subdivision and its applications given a subdivision of the plane induced by a planar graph with n vertices, in this paper we consider the problem of identifying which region of the subdivision contains a given test point. we present a search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure. the search runs in time at most 0((log n)2), while the preprocessing task runs in time at most 0(n log n) and requires 0(n) storage. the methods are quite general, since an arbitrary subdivision can be transformed in time at most 0(n log n) into one to which the preprocessing procedure is applicable. this solution of the point-location problem yields interesting and efficient solutions of other geometric problems, such as spatial convex inclusion and inclusion in an arbitrary polygon.
online minimization of transition systems (extended abstract) we are given a transition system implicitly through a compact representation and wish to perform simultaneously reachability analysis and minimization without constructing first the whole system graph. we present an algorithm for this problem that applies to general systems, provided we have appropriate primitive operations for manipulating blocks of states and we can determine termination; the number of operations needed to construct the minimal reachable graph is quadratic in the size of this graph. we specialize the method to obtain efficient algorithms for extended finite state machines that apply separable affine transformations on the variables.
a partial solution to the reachability-problem for vector-addition systems with geometrical techniques we hope to bring new insight into the reachability problem for vector-addition systems, which is pertaining in many areas in computer science theory but unsolved ever since it was proposed by karp and miller. we show that the reachability-problem is decidable in dim. &le; 3 and give a partial solution for the general problem covering a wide instance of it. in both cases a semi-linear characterization is obtained for the complete set of solutions. contrary to common belief the complete solution in dim. 3 does not immediately generalize, and our analysis gives evidence why. a few generalizations and application to long-standing classificational problems in language theory are discussed.
a layout strategy for vlsi which is provably good (extended abstract) in this paper, we introduce a new framework within which to study vlsi layout problems. the framework is based on a straightforward generalization of the lipton-tarjan notion of a planar separator and, unlike previous approaches, leads to universally close upper and lower bounds on the layout area and crossing number of an arbitrary network. in addition, the framework permits simple proofs of results previously thought to be difficult and is suitable for use with good bisection width heurisitcs.
fast approximation algorithms for multicommodity flow problems in this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. our algorithms are significantly faster than the best previously known algorithms, that were based on linear programming. for a k-commodity multicommodity flow problem, the running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. given any multicommodity flow problem as input, our algorithm is guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + epsilon)-factor, or to provide a proof that there is no feasible solution to the original problem. we also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in the "sparsest cut" problems and the uniform concurrent flow problems if k >= the square root of m.
algorithms for routing and testing routability of planar vlsi layouts this paper studies the problem of routing wires in a grid among features on one layer of a vlsi chip, when a sketch of the layer is given. a sketch specifies the positions of features and the topology of the interconnecting wires. we give polynomial-time algorithms that (1) determine the routability of a sketch, and (2) produce a routing of a sketch that optimizes both individual and total wire length. these algorithms subsume most of the polynomial-time algorithms in the literature for planar routing and routability testing in the rectilinear grid model. we also provide an explicit construction of a database, called the rubber-band equivalent, to support computation involving the layout topology.
upper and lower bounds on time-space tradeoffs this paper derives asymptotically tight bounds on the time-space tradeoffs for pebbling three different classes of directed acyclic graphs. let n be the size of the graph, s the number of available pebbles, and t the time necessary for pebbling the graph. (a) a time space tradeoff of the form st &equil; &thgr;(n2) is proved for a special class of permutation graphs which implement the bit reversal permutation. (b) a time-space tradeoff of the form t &equil; s &thgr;(n/s)&thgr;(n/s) is proved for a class of graphs constructed by stacking superconcentrators in series. (c) a time-space tradeoff of the form t &equil; s.22&thgr;(n/s)is proved for pebbling general directed acyclic graphs.
approximating total flow time on parallel machines. we consider the problem of optimizing the total flow time of a stream of jobs that are released over time in a multiprocessor setting. this problem is np-hard even when there are only two machines and preemption is allowed. although the total (or average) flow time is widely accepted as a good measurement of the overall quality of service, no approximation algorithms were known for this basic scheduling problem. this paper contains two main results. we first prove that when preemption is allowed, shortest remaining processing time (srpt) is an o(log(min{nm,p})) approximation algorithm for the total flow time, where n is the number of jobs, m is the number of machines, and p is the ratio between the maximum and the minimum processing time of a job. we also provide an @w(log(nm+p)) lower bound on the (worst case) competitive ratio of any randomized algorithm for the on-line problem in which jobs are known at their release times. thus, we show that up to a constant factor srpt is an optimal on-line algorithm. our second main result addresses the non-preemptive case. we present a general technique that allows to transform any preemptive solution into a non-preemptive solution at the expense of an o(nm) factor in the approximation ratio of the total flow time. combining this technique with our previous result yields an o(nmlognm) approximation algorithm for this case. we also show an @w(n^1^3^-^@e) lower bound on the approximability of this problem (assuming p
new real-time simulations of multihead tape units just as the church-turing thesis has simplified proofs of computability [8], efficient simulations of one computer model by another have simplified proofs of complexity upper bounds. a good example of this is fischer, meyer, and rosenberg's real-time simulation of multihead turing machines by multitape turing machines [5]. without this result, for example, even slisenko [11] may have found it hopeless to show that a multitape turing machine can recognize palindromes in real time. in this paper we give a comparatively simple proof of the fischer-meyer-rosenberg result, dramatically reduce the number of single-head tapes required for the simulation, and generalize the result to multidimensional tapes. in the case of slisenko's palindrome-recognizer, for example, our best simulation brings the number of tapes for a multitape turing machine implementation down from 41 to 20.
collusion-free protocols. secure protocols attempt to minimize the injuries to privacy and correctness inflicted by malicious participants who collude during run-time. they do not, however, prevent malicious parties from colluding and coordinating their actions in the first place!eliminating such collusion of malicious parties during the execution of a protocol is an important and exciting direction for research in cryptography. we contribute the first general result in this direction: (1) we provide a rigorous definition of what a collusion-free protocol is; and (2) we prove that, under standard physical and computational assumptions ---i.e., plain envelopes and trapdoor permutations---collusion-free protocols exist for all finite protocol tasks with publicly observable actions. (note that such tasks are allowed to have secret global state, and thus include poker, bridge, and other such games.our solution is tight in the sense that, for a collusion-free protocol to exist, each of (a) the finiteness of the game of interest, (b) the public observability of its actions, and (c) the use of some type of physically private channel is provably essential.
primal-dual algorithms for deterministic inventory problems. we consider several classical models in deterministic inventory theory: the single-item lot-sizing problem, the joint replenishment problem, and the multistage assembly problem. these inventory models have been studied extensively, and play a fundamental role in broader planning issues, such as the management of supply chains. for each of these problems, we wish to balance the cost of maintaining surplus inventory for future demand against the cost of replenishing inventory more frequently. for example, in the joint replenishment problem, demand for several commodities is specified over a discrete finite planning horizon, the cost of maintaining inventory is linear in the number of units held, but the cost incurred for ordering a commodity is independent of the size of the order; furthermore, there is an additional fixed cost incurred each time a nonempty subset of commodities is ordered. the goal is to find a policy that satisfies all demands on time and minimizes the overall holding and ordering cost. we shall give a novel primal-dual framework for designing algorithms for these models that significantly improve known results in several ways: the performance guarantees for the quality of the solutions improve on or match previously known results; the performance guarantees hold under much more general assumptions about the structure of the costs, and the algorithms and their analysis are significantly simpler than previous known results. finally, our primal-dual framework departs from the structure of previously studied primal-dual approximation algorithms in significant ways, and we believe that our approach may find applications in other settings. more specifically, we provide 2-approximation algorithms for the joint replenishment problem and for the assembly problem, and solve the single-item lot-sizing problem to optimality. the results for the joint replenishment and the lot-sizing problems also hold for their generalizations with back orders allowed. as a byproduct of our work, we prove known and new upper bounds on the integrality gap of some linear-programming (lp) relaxations of the abovementioned problems.
provably near-optimal sampling-based algorithms for stochastic inventory control models. we consider two fundamental stochastic optimization problems that arise in the context of supply-chain models, the single-period newsvendor problem and its multiperiod extension with independent demands. these problems are among the most well-studied stochastic optimization problems in the operations research literature. most commonly, these problems are studied from the perspective that the input probability distributions are given in terms of specific probability distribution functions that are computationally tractable; under this assumption, both problems can be solved efficiently. unfortunately, this information is unlikely to be available in practice, and hence we make the more realistic assumption that the probability distribution is given by a "black box" from which independent samples can be drawn. we give the first fully polynomial randomized approximation schemes for these two problems in this sampling-based model.our work provides new insights into the power of two of the most often-used approaches to solving stochastic optimization problems, the sample average approximation (saa) and stochastic dynamic programming. for the newsvendor problem, we show that by taking a polynomial number of samples and then solving the newsvendor problem with respect to the resulting approximation to the true distribution, we obtain provably near-optimal solution. this significantly extends the class of problems for which the saa is known to yield a scheme. finally, we show how to adapt the framework of stochastic dynamic programming to yield an approximation scheme for the multiperiod newsvendor problem with independent demands. we believe that this is an interesting first step towards the goal of providing a mechanism for deriving efficient approximate stochastic dynamic programming methods for a wide range of multistage stochastic optimization problems.
one-way functions and pseudorandom generators one-way are those functions which are easy to compute, but hard to invert on a non-negligible fraction of instances. the existence of such functions with some additional assumptions was shown to be sufficient for generating perfect pseudorandom strings |blum, micali 82|, |yao 82|, |goldreich, goldwasser, micali 84|. below, among a few other observations, a weaker assumption about one-way functions is suggested, which is not only sufficient, but also necessary for the existence of pseudorandom generators. the main theorem can be understood without reading the sections 3-6.
some results in tree automata in this paper, we will essentially present three results in tree automata. two of these are concerned with certain open problems posed by rounds [1] and martin and vere [3], and the third one is related to the result of peters and ritchie [4]. first we will briefly state the results and then describe them in some detail in sections 2, 3, and 4.
unsolvability considerations in computational complexity the study of computational complexity began with the investigation of turing machine computations with limits on the amounts of tape or time which could be used. latter a set of general axioms for measures of resource limiting was presented and this instigated much study of the properties of these general measures. many interesting results were shown, but the general axioms allowed measures with undesirable properties and many attempts have been made to tighten up the axioms so that only desirable measures will be defined. in this paper several undecidability aspects of complexity classes and several sets associated with them will be examined. these sets will be classified by their degree of unsolvability and restrictions will be placed on measures so that these degrees are identical. this gives rise to a new criterion for the &ldquo;naturalness&rdquo; of measures and to suggestions for strengthening the measures of complexity.
closure of families of languages under substitution operators this paper treats the closure of families of formal languages under operators which may be viewed as substitution into a particular language. a language l over alphabet {a1,...,an} induces an n-place operator on languages by substitution of the n arguments li for the symbols ai. for example, if l is regular, it induces an operator under which any full afl is closed. in section two we find a large class of full afl's which are closed under no other such operators than those induced by regular languages. also, for any full afl @@@@', let @@@@ be the class of languages which @@@@' is closed under substitution into. then @@@@ is itself a full afl and is closed under substitution. finally we show that any substitution-closed full afl @@@@ is obtained in this manner from some non-substitution-closed full afl @@@@ (except when @@@@ is the universal family). the study is based on the concept of a full afl, and in section one considerable effort is devoted to a novel approach to the subject. a full afl is taken to be a family of languages closed under finite-state transducer mappings and substitution into regular sets. by replacing the family of regular sets with more general families we obtain some broad results about canonical forms for derivations of languages from other languages using transducers and substitution. these forms yield several known forms as special cases, and provide tools needed for the study of full afl's in section two.
on the complexity of the maximum subgraph problem for a fixed graph property, the maximum subgraph recognition problem for the property is: given a graph g and integer k, does g have a subgraph induced by k vertices which satisfies the property. this paper studies the complexity of this problem for various properties. the principal result is that if the property is any one of a wide class of monotone properties, the maximum subgraph problem is np-hard. this suggests a promising direction of inquiry into the p &equil; ?np question.
attributed translations attributed translation grammars are introduced as a means of specifying a translation from strings of input symbols to strings of output symbols. each of these symbols can have a finite set of attributes, each of which can take on a value from a possibly infinite set. attributed translation grammars can be applied in depth to practical compiling problems. certain augmented pushdown machines are defined and characterizations are given of the attributed translations they can perform both deterministically and non-deterministically. classes of attributed translation grammars are defined whose translation can be performed deterministically while parsing top down or bottom up.
finding similar regions in many strings. algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems. assume that we are given n dna sequences s1, ...., sn. the consensus patterns problem, which has been widely studied in bioinformatics research, in its simplest form, asks for a region of length l in each si, and a median string s of length l so that the total hamming distance from s to these regions is minimized. we show that the problem is np-hard and give a polynomial time approximation scheme (ptas) for it. we then present an efficient approximation algorithm for the consensus pattern problem under the original relative entropy measure. as an interesting application of our analysis, we further obtain a ptas for a restricted (but still np-hard) version of the important consensus alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence.
isomorphism for graphs embeddable on the projective plane there are no known polynomial time algorithms for graph isomorphism. for certain classes of graphs, however, efficient algorithms have been found. in particular, there is a polynomial time algorithm for isomorphism of planar graphs [4,5]. this paper presents a generalization of the third theorem to the projective plane, allowing a straightforward adaptation of the planar algorithm to the projective plane. gary miller has subsequently generalized my result to surfaces of arbitrary genus, so that there is now a graph isomorphism algorithm which is polynomial for any fixed genus.
imperfect random sources and discrete controlled processes we consider a simple model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. the process produces a string of characters from {0, 1} of length n and is a &ldquo;success&rdquo; or &ldquo;failure&rdquo; depending on whether the string produced belongs to a prespecified set l. in an uninfluenced process each character is chosen by a fair coin toss, and hence the probability of success is |l|/2n. we are interested in the effect on the probability of success in the presence of a player (controller) who can intervene in the process by specifying the value of certain characters in the string. we answer the following questions in both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of |l| what is the expected number of interventions needed to guarantee success? in particular our results imply that if |l|/2n = 1/w(n) where w(n) tends to infinity with n (so the probability of success with no interventions is o(1)) then with &ogr;(&radic;nlogw(n)) interventions the probability of success is 1-o(1). our main results and the proof techniques are related to a well-known theorem of kruskal, katona, and harper in extremal set theory.