waashk/dblp huggingface dataset:
a new approach to the maximum flow problem all previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original ford and fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of dinic). an alternative method based on the preflow concept of karzanov is introduced. a preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. the method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. the algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving an o(n3) time bound on an n-vertex graph. by incorporating the dynamic tree data structure of sleator and tarjan, we obtain a version of the algorithm running in o(nm log(n2/m)) time on an n-vertex, m-edge graph. this is as fast as any known method for any graph density and faster on graphs of moderate density. the algorithm also admits efficient distributed and parallel implementations. a parallel implementation running in o(n2log n) time using n processors and o(m) space is obtained. this time bound matches that of the shiloach-vishkin algorithm, which also uses n processors but requires o(n2) space.
solving minimum-cost flow problems by successive approximation we introduce a framework for solving minimum-cost flow problems. our approach measures the quality of a solution by the amount that the complementary slackness conditions are violated. we show how to extend techniques developed for the maximum flow problem to improve the quality of a solution. this framework allows us to achieve &ogr;(min(n3, n5/3 m2/3, nm log n) log (nc)) running time.
finding minimum-cost circulations by canceling negative cycles a classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. we show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. this gives a very simple strongly polynomial algorithm that uses no scaling. a variant of the algorithm that uses dynamic trees runs in o(nm(log n) min{log(nc), mlog n}) time on a network of n vertices, m arcs, and arc costs of maximum absolute value c. this bound is comparable to those of the fastest previously known algorithms.
simulating threshold circuits by majority circuits. we prove that a single threshold gate with arbitrary weights can be simulated by an explicit polynomial-size, depth-2 majority circuit. in general we show that a polynomial-size, depth-d threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth d + 1. goldmann, håstad, and razborov showed in [comput. complexity, 2 (1992), pp. 277--300] that a nonuniform simulation exists. our construction answers two open questions posed by them: we give an explicit construction, whereas they use a randomized existence argument, and we show that such a simulation is possible even if the depth d grows with the number of variables n (their simulation gives polynomial-size circuits only when d is constant).
concurrent zero-knowledge with timing, revisited. following dwork, naor, and sahai (30th stoc, 1998), we consider concurrent execution of protocols in a semi-synchronized network. specifically, we assume that each party holds a local clock such that a constant bound on the relative rates of these clocks is a-priori known, and consider protocols that employ time-driven operations (i.e., time-out in-coming messages and delay out-going messages).we show that the constant-round zero-knowledge proof for np of goldreich and kahan (jour. of crypto., 1996) preserves its security when polynomially-many independent copies are executed concurrently under the above timing model.we stress that our main result establishes zero-knowledge of interactive proofs, whereas the results of dwork et al are either for zero-knowledge arguments or for a weak notion of zero-knowledge (called &egr;-knowledge) proofs.our analysis identifies two extreme schedulings of concurrent executions under the above timing model: the first is the case of parallel execution of polynomially-many copies, and the second is of concurrent execution of polynomially-many copies such the number of copies that are simultaneously active at any time is bounded by a constant (i.e., bounded simultaneity). dealing with each of these extreme cases is of independent interest, and the general result (regarding concurrent executions under the timing model) is obtained by combining the two treatments.
towards a theory of software protection and simulation by oblivious rams software protection is one of the most important issues concerning computer practice. there exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. in this paper, we make the first steps towards a theoretic treatment of software protection: first, we distill and formulate the key problem of learning about a program from its execution. second, assuming the existence of one-way permutations, we present an efficient way of executing programs such that it is infeasible to learn anything about the program by monitoring its executions. how can one efficiently execute programs without allowing an adversary, monitoring the execution, to learn anything about the program? traditional cryptographic techniques can be applied to keep the contents of the memory unknown throughout the execution, but are not applicable to the problem of hiding the access pattern. the problem of hiding the access pattern efficiently corresponds to efficient simulation of random access machines (ram) on an oblivious ram. we define an oblivious ram to be a (probabilistic) ram for which (the distribution of) the memory access pattern is independent of the input. we present an (on-line) simulation of t steps of an arbitrary ram with m memory cells, by less than t&middot;m&egr; steps of an oblivious ram with 2m memory cells, where &egr;>0 is an arbitrary constant.
a hard-core predicate for all one-way functions a central tool in constructing pseudorandom generators, secure encryption functions, and in other areas are &ldquo;hard-core&rdquo; predicates b of functions (permutations) &fnof;, discovered in [blum micali 82]. such b(x) cannot be efficiently guessed (substantially better than 50-50) given only &fnof;(x). both b, &fnof; are computable in polynomial time. [yao 82] transforms any one-way function &fnof; into a more complicated one, &fnof;*, which has a hard-core predicate. the construction applies the original &fnof; to many small pieces of the input to &fnof;* just to get one &ldquo;hard-core&rdquo; bit. the security of this bit may be smaller than any constant positive power of the security of &fnof;. in fact, for inputs (to &fnof;*) of practical size, the pieces effected by &fnof; are so small that &fnof; can be inverted (and the &ldquo;hard-core&rdquo; bit computed) by exhaustive search. in this paper we show that every one-way function, padded to the form &fnof;(p, x) = (p, g(x)), &verbar;&verbar;p&verbar;&verbar; = &verbar;x&verbar;, has by itself a hard-core predicate of the same (within a polynomial) security. namely, we prove a conjecture of [levin 87, sec. 5.6.2] that the scalar product of boolean vectors p, x is a hard-core of every one-way function &fnof;(p, x) = (p, g(x)). the result extends to multiple (up to the logarithm of security) such bits and to any distribution on the x's for which &fnof; is hard to invert.
a unified approach to models of synchronous parallel machines a number of different models of synchronous, unbounded parallel computers have appeared in recent literature. without exception, running time on these models has been shown to be polynomially related to the classical space complexity measure. the general applicability of this relationship is called &ldquo;the parallel computation thesis&rdquo; and strong evidence of its truth is given in this paper by introducing the notion of &ldquo;conglomerates&rdquo; - a very large class of parallel machines, including all those which could feasibly be built. basic parallel machine models are also investigated, in an attempt to pin down the notion of parallel time to within a constant factor. to this end, a universal conglomerate structure is developed with can simulate any other basic model within linear time. this approach also leads to fair estimates of instruction execution times for various parallel models.
strong signature schemes the notion of digital signature based on trapdoor functions has been introduced by diffie and hellman[3]. rivest, shamir and adleman[8] gave the first number theoretic implementation of a signature scheme based on a trapdoor function. if f is a trapdoor function and m a message, f&minus;1(m) is the signature of m. the signature can be verified by computing f(f&minus;1(m)) &equil; m. this approach presents the following problems even when f is hard to invert: 1) there may be special message spaces (or subsets of them) that are easy to sign without knowing the trapdoor information 2) it is possible to forge the signature of random numbers; this violates the requirements of many protocols 3) given a polynomial number of signed messages, it may be possible to sign a new one without knowing the trapdoor information. we solve the above problems by exhibiting two signature schemes for which any strategy of an adversary, who has seen all previously signed messages, that has a moderate success in forging even a single additional signature, is transformable to a fast algorithm for factoring or inverting the rsa function. this provably holds for all message spaces with all possible probability distributions. thus, in particular, given the signature of m, forging the signature of m+1 or 2m or 2sm is as hard as factoring. the two signature schemes
huffman coding with unequal letter costs. (math) in the standard huffman coding problem, one is given a set of words and for each word a positive frequency. the goal is to encode each word w as a codeword c(w) over a given alphabet. the encoding must be prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size &sgr;w freq w, &124;c(w)&124;. the problem has a well-known polynomial-time algorithm due to huffman [15].here we consider the generalization in which the letters of the encoding alphabet may have non-uniform lengths. the goal is to minimize the weighted average codeword length &sgr;w freq (w) cost(c(w)), where cost s is the sum of the (possibly non-uniform) lengths of the letters in s. despite much previous work, the problem is not known to be np-hard, nor was it previously known to have a polynomial-time approximation algorithm. here we describe a polynomial-time approximation scheme (ptas) for the problem.
edge partition of planar sraphs into two outerplanar graphs. an outerplanar graph is a planar graph that can be embedded in the plane without crossing edges, in such a way that all the vertices are on the outer boundary. in this paper, we prove a conjecture of chartrand, geller, and hedetniemi that any planar graph g=(v,e) has a bipartition of its edge set e = a ∪ b such that the graphs induced by these subsets, g[a] and g[b], are outerplanar.
a linear probing sort and its analysis (preliminary draft) we present a variant of the distribution sort approach which makes use of extra storage to sort a list of n elements in an average of about (2+@@@@2)n &equil; 3.412...n probes into a table. an accurate analysis of this technique is made by introducing a transform from a poisson approximation to the exact (finite) distribution. this analysis also leads to the solution of an interesting parking problem.
on the stability of the ethernet we consider the stochastic behavior of binary exponential backoff, a probabilistic algorithm for regulating transmissions on a multiple access channel. ethernet, a local area network, is built upon this algorithm. the fundamental theoretical issue is stability: does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough? we present a realistic model of n &ge; 2 stations communicating over the channel. our main result is to establish that the algorithm is stable if the sum of the arrival rates is sufficiently small. we report detailed results on which rates lead to stability when n = 2 stations share the channel. in passing we derive several other results bearing on the efficiency of the conflict resolution process. lastly, we report results from a simulation study, which, in particular, indicate alternative retransmission strategies can significantly improve performance.
coordinate representation of order types requires exponential storage we give doubly exponential upper and lower bounds on the size of the smallest grid on which we can embed every planar configuration of n points in general position up to order type. the lower bound is achieved by the construction of a widely dispersed &ldquo;rigid&rdquo; configuration which is then modified to one in general position by recent techniques of sturmfels and white, while the upper bound uses recent results of grigor'ev and vorobjou on the solution of simultaneous inequalities. this provides a sharp answer to a question first posed by chazelle.
on line context free language recognition in less than cubic time (extended abstract) a new on-line context free language recognition algorithm is presented which is derived from earley's algorithm and has several advantages over the original. first, the new algorithm not only is conceptually simpler than earley's, but also allows significant speed improvements. second, our algorithm serves to explain the connections between earley's algorithm and the cocke-kasami-younger algorithm. third, our algorithm allows an implementation which uses only 0(n2/log n) operations on bit vectors of length n, or 0(n3/log n) operations on a ram. this makes it the fastest known on-line context free language recognition algorithm.
on the time complexity of broadcast communication schemes (preliminary version) in this paper, we investigate the power of such broadcast in solving a paradigmatic problem in distributed computing. imagine a network in which each node machine ni (1-&-le;i-&-le;n) keeps a boolean value vi in local memory. the vi 's determine a set s-&-equil;{i: vi-&-equil;1}. the non-emptiness problem on n nodes is to find some i in s, or else find that s is empty. in practice, a problem of this type arises in two ways: 1. consensus testing: has any node voted -&-ldquo;no-&-rdquo;, where vi-&-equil;1 means node i votes -&-ldquo;no-&-rdquo;, and vi-&-equil;o means node i votes -&-ldquo;yes-&-rdquo;? 2. establishing a distinguished node: s specifies a set of candidates, and solving non-emptiness selects one. for example, the nodes may be bidding for a job or a resource. in section 2, we introduce an idealistic broadcast communication scheme which abstracts certain features of the csma technology.
some restrictions on w-grammars the effect of some restrictions on w-grammars (the formalization of the syntax of algol 68) are explored. two incomparable families examined at length are wrb (languages generated by normal regular-based w-grammars) and ws (languages generated by simple w-grammars). both properly contain the context-free languages and are properly contained in the family of quasirealtime languages. in addition, wrb is closed under nested iterated substitution (but is not an afl) and is properly contained in the family of indexed languages.
quantum mechanical algorithms for the nonabelian hidden subgroup problem. we provide positive and negative results concerning the &ldquo;standard method&rdquo; of identifying a hidden subgroup of a nonabelian group using a quantum computer.
a lower bound for randomized algebraic decision trees. we extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the intersections of halfspaces. as an application, among other things, we derive, for the first time, $\omega(n^2)$ randomized lower bound for the {\em knapsack problem} (which was previously only known for deterministic algebraic decision trees).
computing crossing numbers in quadratic time. we show that for every fixed k ≥ 0 there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, computes a drawing of the graph into the plane with at most k crossings.
when is the evaluation of conjunctive queries tractable? the evaluation of conjunctive queries is hard both with respect to its combined complexity (np-complete) and its parameterized complexity (w[1]-complete). it becomes tractable (ptime for combined complexity, fpt for parameterized complexity), when the underlying graphs of the conjunctive queries have bounded tree-width [2]. we show that, in some sense, this is optimal both with respect to combined and parameterized complexity: for every class c of graphs, the evaluation of all conjunctive queries whose underlying graph is in c is tractable if, and only if, c has bounded tree-width.a technical result of independent interest is that the colored grid homomorphism problem is np-complete and, if parameterized by the grid size, w[1]-complete.
asymptotic conditional probabilities for first-order logic motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order formulas. that is, given first-order formulas &fgr; and &thgr;, we consider the number of structures with domain {1,&hellip;,n} that satisfy &thgr;, and compute the fraction of them in which &fgr; is true. we then consider what happens to this probability of first-order formulas, except that now we are considering asymptotic conditional probabilities. although work has been done on special cases of asymptotic conditional probabilities, no general theory has been developed. this is probably due in part to the fact that it has been known that, if there is a binary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. we show that in this general case, almost all the questions one might want to ask (such as deciding whether the asymptotic probability exists) are highly undecidable. on the other hand, we show that the situation with unary predicates only is much better. if the vocabulary consists only of unary predicate and constant symbols, it is decidable whether the limit exists, and if it does, there is an effective algorithm for computing it. the complexity depends on two parameters: whether there is a fixed finite vocabulary or an infinite one, and whether there is a bound on the depth of quantifier nesting.
data-streams and histograms. histograms have been used widely to capture data distribution, to represent the data by a small number of step functions. dynamic programming algorithms which provide optimal construction of these histograms exist, albeit running in quadratic time and linear space. in this paper we provide linear time construction of 1 + &egr; approximation of optimal histograms, running in polylogarithmic space.our results extend to the context of data-streams, and in fact generalize to give 1 + &egr; approximation of several problems in data-streams which require partitioning the index set into intervals. the only assumptions required are that the cost of an interval is monotonic under inclusion (larger interval has larger cost) and that the cost can be computed or approximated in small space. this exhibits a nice class of problems for which we can have near optimal data-stream algorithms.
a constant factor approximation for the single sink edge installation problems. we present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. the distances in the underlying network form a metric. this result improves the previous bound of $o(\log|r|)$, where $r$ is the set of sources. we also present a better constant approximation to the related access network design problem. our algorithms are randomized and combinatorial. as a subroutine in our algorithm, we use an interesting variant of facility location with lower bounds on the amount of demand an open facility needs to serve. we call this variant load balanced facility location and present a constant factor approximation for it, while relaxing the lower bounds by a constant factor.
a new representation for linear lists we present a new data structure for maintaining a set of records in a linear list according to their key values. this data structure has the property that we can keep a number of fingers at points of interest in the key space (e.g., the beginning or the end of the list), so that access and modification in the neighborhood of a finger is very efficient. in the section 2 we discuss the general structure of our b-tree. since we propose to search the tree from a leaf upwards, additional links need to be introduced. in section 3 we show how to obtain our result for the case of one finger. a key idea is the construction of a number representation behaving as described above, which we can use to model the propagation of modifications in the b-tree along the finger path. in section 4 we generalize the structure so that several fingers in the key space can be maintained, with the advantage that access is cheap in the neighborhood of each finger. finally in section 5 we present some implementation notes and applications, mostly to sorting.
the analysis of double hashing (extended abstract) in this paper we analyze the performance of a well known algorithm known as double hashing [knuth]. in this method we probe the hash table along arithmetic progressions, where both the initial element and the increment of the progression are chosen randomly and independently depending only on the key k of the search. we prove that double hashing is asymptotically equivalent to uniform probing, an idealized hashing technique that exhibits no clustering and is known to be optimal in a certain sense. between steps of the extension process we can show that the effect of clustering is negligible, and that we therefore never depart too far from the truly random situation.
primitives for the manipulation of general subdivisions and the computation of voronoi diagrams we discuss the following problem: given n points in the plane (the &ldquo;sites&rdquo;), and an arbitrary query point q, find the site that is closest to q. this problem can be solved by constructing the voronoi diagram of the given sites, and then locating the query point in one of its regions. we give two algorithms, one that constructs the voronoi diagram in o(n lg n) time, and another that inserts a new site in o(n) time. both are based on the use of the voronoi dual, the delaunay triangulation, and are simple enough to be of practical value. the simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem, and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. the topology is represented by a new data structure for generalized diagrams, that is embeddings of graphs in two-dimensional manifolds. this structure represents simultaneously an embedding, its dual, and its mirror-image. furthermore, just two operators are sufficient for building and modifying arbitrary diagrams.