waashk/dblp huggingface dataset:
epsilon-approximations with minimum packing constraint violation (extended abstract) we present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding np-hard discrete optimization problem. without any constraint violation, the &egr;-approximation problem for many problems of this type is itself np-hard. our methods provide polynomial-time &egr;-approximations while attempting to minimize the packing constraint violation. our methods lead to the first known approximation algorithms with provable performance guarantees for the s-median problem, the tree prunning problem, and the generalized assignment problem. these important problems have numerous applications to data compression, vector quantization, memory-based learning, computer graphics, image processing, clustering, regression, network location, scheduling, and communication. we provide evidence via reductions that our approximation algorithms are nearly optimal in terms of the packing constraint violation. we also discuss some recent applications of our techniques to scheduling problems.
bounded-concurrent secure two-party computation without setup assumptions. in this paper we study the feasibility of obtaining protocols for general two-party computation that remain secure under concurrent composition. (a general protocol can be used for obtaining secure computation of any functionality.) we consider a scenario where no trusted setup is assumed (and so, for example, there is no common reference string available to the parties); we call this the "plain model". we present both negative and positive results for this model. specifically, we show that a general two-party protocol that remains secure for m concurrent executions and can be proven via black-box simulation, must have more than m rounds of communication. an important corollary of this result is that there do not exist protocols for black-box secure general two-party computation for the case of unbounded concurrency (where any polynomial number of concurrent executions may be run). on the positive side, we show that under general cryptographic assumptions, there exist secure protocols for general two-party computation in the model of bounded concurrent composition (in this model the number of concurrent executions is fixed and the protocol design may depend on this number). our protocol has o(m) rounds of communication, where m is the bound on the number of concurrent executions, and uses both black-box and non black-box techniques. we note that this protocol constitutes the first feasibility result for general two-party computation without setup assumptions for any model of concurrency.
a logspace algorithm for tree canonization (extended abstract) we present a solution to the problem of assigning to each directed tree t of size n a unique isomorphism invariant name for t, using only work space o(log n). hence, tree isomorphism is computable in logspace. as another consequence, we obtain the corollary that the set of logspace computable queries (lspace) on trees is recursively enumerable. our results extend easily to undirected trees and even forests.
on the composition of authenticated byzantine agreement. a fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. this problem is known as byzantine agreement (or generals) and has been the focus of much research. lamport et al. [1982] showed that in order to achieve byzantine agreement in the plain model, more than two thirds of the participating parties must be honest. they further showed that by augmenting the network with a public-key infrastructure for digital signatures, it is possible to obtain protocols that are secure for any number of corrupted parties. the problem in this augmented model is called &ldquo;authenticated byzantine agreement&rdquo;.in this article, we consider the question of concurrent, parallel and sequential composition of authenticated byzantine agreement protocols with a single common setup. we present surprising impossibility results showing that:(1) authenticated byzantine agreement protocols that remain secure under parallel or concurrent composition (even for just two executions) and tolerate a third or more corrupted parties, do not exist.(2) deterministic authenticated byzantine agreement protocols that run for r rounds and tolerate a third or more corrupted parties, can remain secure for at most 2r &minus; 1 sequential executions.in contrast, we present randomized protocols for authenticated byzantine agreement that remain secure under sequential composition, for any polynomial number of executions. we exhibit two such protocols. in the first protocol, an honest majority is required. in the second protocol, any number of parties may be corrupted; however, the complexity of the protocol is in the order of 2n &middot; n&excl; for n parties. in order to have this polynomial in the security parameter k (used for the signature scheme in the protocol), this requires the overall number of parties to be limited to o(log k/log log k). the above results are achieved due to a new protocol for authenticated byzantine generals for three parties that can tolerate any number of faulty parties and composes sequentially.finally, we show that when the model is further augmented so that in each session, all the participating parties receive a common session identifier that is unique to that session, then any polynomial number of authenticated byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.
developmental systems and languages developmental systems were introduced (lindenmayer, 1968, 1971) in order to model morphogenetic (pattern-generating) processes in growing, multicellular, filamentous organisms. these systems were originally conceived as linear arrays of interconnected finite automata, each automaton corresponding to a living cell, with the possibility that new automata can be added to the array (cells divide) or be deleted from the array (cells die). each cell in the array is supposed to have the same state-transition and output functions. as required by biological considerations these functions must be applied to all cells in the array simultaneously at each time step. thus one obtains infinite sequences of arrays once the functions and the initial arrays are specified. simplified constructs are defined (and used in this paper) by considering the states and outputs to be identical and thus omitting the output functions. such filamentous developmental systems have been called &ldquo;lindenmayer models&rdquo; herman, 1969, 1970) or &ldquo;l-systems&rdquo; (van dalen, 1971).
the design of parsers for incremental language processors an incremental language processor is one that accepts as input a sequence of substrings of the source language and maps them independently onto fragments in some object code. the ordered sequence of these object code fragments are then either compiled, in which case we have an incremental compiler, or interpreted. in the first case the advantage resulting is that subsequent changes in the source program entail only reprocessing the source fragments affected and recompiling the updated collection of object code fragments. in an environment where small changes are made frequently to large programs, e.g. debugging, the curtailment of reprocessing is attractive. in the second case the object code fragments are the actual run-time program representation, and hence inter-fragment relations are transiently evaluated as needed in the process of execution, with no long-term preservation of these relationships beyond the scope of their immediate need in execution time. this permits the possibility of program recomposition in the midst of execution, one of the principal characteristics of conversational computing. many conversational language processors execute a program representation functionally analogous to parse trees, i.e. the syntax analysis of a fragment, insofar as it is possible, is done at fragment load time. this representation choice is popular because many of the expensive aspects of interpretation, including character string scanning, symbol table lookup, and parsing, are performed once only and do not contribute to the execution overhead. this paper is devoted to examining the question of the construction of such a parser in a general manner for an arbitrary source language.
girth and euclidean distortion. (math) in this paper we partially prove a conjecture that was raised by linial, london and rabinovich in \cite{llr}. let $g$ be a $k$-regular graph, $k \ge 3$, with girth $g$. we show that every embedding $f : g \to \ell_2$ has distortion $\omega (\sqrt{g})$. the original conjecture which remains open is that the euclidean distortion is bounded below by $\omega(g)$. two proofs are given, one based on semi-definite programming, and the other on markov type, a concept that considers random walks on metrics.
limitations of synchronization primitives with conditional branching and global variables a formal model of the process concept is presented. this model can represent sets of processes that use the synchronization primitive pv or one of the many generalizations of pv. the study of synchronization problems is then reduced to the study of relations between sets of processes. for one relation&mdash; &ldquo;simulate&rdquo;&mdash;it is possible to show that there are differences between several synchronization primitives. these differences show that the relative &ldquo;power&rdquo; of these synchronization primitives is not the same.
complexity measures and hierarchies for the evaluation of integers, polynomials, and n-linear forms the difficulty of evaluating integers and polynomials has been studied in various frameworks ranging from the addition-chain approach [5] to integer evaluation to recent efforts aimed at generating polynomials that are hard to evaluate [2,8,10]. here we consider the classes of integers and polynomials that can be evaluated within given complexity bounds and prove the existence of proper hierarchies of complexity classes. the framework in which our problems are cast is general enough to allow any finite set of binary operations rather than just addition, subtraction, multiplication, and division. the motivation for studying complexity classes rather than specific integers or polynomials is analogous to why complexity classes are studied in automata-based complexity: (i) the immense difficulty associated with computing the complexity of a specific integer or polynomial; (ii) the important insight obtained from discovering the structure of the complexity classes.
the complexity of control structures and data structures the running time or computational complexity of a sequential process is usually determined by summing weights attached to the basic operations from which the process is derived. in practice, however, the complexity is often limited by how efficiently it can access its data structures and how efficiently it can control program flow. furthermore, it has been extensively argued [4] that certain limitations on the process sequencing mechanisms available to the programmer result in more &ldquo;efficient&rdquo; representations for the underlying processes. in this paper we will examine these issues in an attempt to assess the &ldquo;power&rdquo; of various data and control structures.
evaluation of polynomials with super-preconditioning in an effort to understand the complexity of arithmetic computation, a number of researchers [1,5,7,8,9,11] have studied the following question: given a polynomial f(x), find a minimal cost straightline program that computes f(x).@@@@ in this paper this question is generalized to the following question: given a polynomial f(x) and an operator &dgr; that maps polynomials to sets of polynomials, find a minimal cost straightline program that computes some h(x) &egr; &dgr;(f(x)).
lower bounds for vlsi increased use of very large scale integration (vlsi) for the fabrication of digital circuits has led to increased interest in complexity results on the inherent vlsi difficulty of various problems. lower bounds have been obtained for problems such as integer multiplication [1,2], matrix multiplication [7], sorting [8], and discrete fourier transform [9], all within vlsi models similar to one originally developed by thompson [8,9]. the lower bound results all pertain to a space-time trade-off measure that arises naturally within this model. in this paper, we extend the model and the class of functions for which non-trivial bounds can be proved. in section 2, we give a more general model than has been proposed previously. in section 3 we show how to reduce the derivation of lower bounds within the model to a problem in distributed computing in section 4, we consider lower bounds for a number of predicates: n-input, l-output functions (as contrasted with the n-input, n-output functions which have been studied previously). in section 5, we show that previous lower bound results (for n-input, n-output functions) also apply even when the model is extended to allow nondeterminism, randomness, and multiple arrivials. finally, the full details of the results presented here will appear in the final version of this paper.
on-line learning of linear functions we present an algorithm for the on-line learning of linear functions which is optimal to within a constant factor with respect to bounds on the sum of squared errors for a worst case sequence of trials. the bounds are logarithmic in the number of variables. furthermore, the algorithm is shown to be optimally robust with respect to noise in the data (again to within a constant factor). we also discuss an application of our methods to the iterative solution of sparse systems of linear equations.
critical path scheduling of task systems with resource and processor constraints (extended abstract) minimum execution time scheduling of unit execution time (uet) task systems with resources has been the subject of several papers over the past few years. because such scheduling problems are, in general, np-hard, a variety of heuristic methods for producing schedules have been studied, among them, critical path scheduling. the strongest results to date have been for systems where there is no processor constraint. these results may be utilized for systems with a processor constraint by treating the processors as an additional resource. unfortunately, in those cases where the number of processors is close to the number of resources, this results in an upper bound which is somewhat misleading. in this paper we investigate the performance of critical path scheduling for uet task systems with resources and a fixed number of processors. an upper bound for the worst case performance of critical path scheduling is given. this bound depends both on the number of processors and on the number of different resources. moreover, we show that this is the best possible (asymptotic) upper bound.
on gamma-reducibility versus polynomial time many-one reducibility (extended abstract) we prove that a class of functions (denoted by npcpt), whose graphs can be accepted in non-deterministic polynomial time, can be evaluated in deterministic polynomial time if and only if &ggr;-reducibility is equivalent to polynomial time many-one reducibility. we also modify the proof technique used to obtain part of this result to obtain the stronger result that if every &ggr;-reduction can be replaced by a polynomial time turing reduction then every function in npcpt can be evaluated in deterministic polynomial time.
how discreet is the discrete log? blum and micali [4] showed how to hide one bit using the discrete logarithm function. in this paper we show how to hide c&bull;loglog p bits for any constant c, where p is the modulus.
hit-and-run from a corner. we show that the hit-and-run random walk mixes rapidly starting from any interior point of a convex body. this is the first random walk known to have this property. in contrast, the ball walk can take exponentially many steps from some starting points. the proof extends to sampling an exponential density over a convex body.
on minimal-program complexity measures brief consideration is given to some properties of three measures of complexity based on the length of minimal descriptive programs. although the measures explicitly deal with finite sequences, the complexity of an infinite sequence can be regarded as a function mapping each positive integer n to the complexity of the initial segment of length n. some properties of a complexity hierarchy of infinite sequences with respect to one of the measures is considered.
extractors: optimal up to constant factors. this paper provides the first explicit construction of extractors which are simultaneously optimal up to constant factors in both seed length and output length. more precisely, for every n,k, our extractor uses a random seed of length o(log n) to transform any random source on n bits with (min-)entropy k, into a distribution on (1-α)k bits that is ε-close to uniform. here α and ε can be taken to be any positive constants. (in fact, ε can be almost polynomially small.our improvements are obtained via three new techniques, each of which may be of independent interest. the first is a general construction of mergers [22] from locally decodable error-correcting codes. the second introduces new condensers that have constant seed length (and retain a constant fraction of the min-entropy in the random source). the third is a way to augment the "win-win repeated condensing" paradigm of [17] with error reduction techniques like [15] so that the our constant seed-length condensers can be used without error accumulation.
doubly lexical orderings of matrices a doubly lexical ordering of the rows and columns of any real-valued matrix is defined. this notion extends to graphs. these orderings are used to prove and unify results on several classes of matrices and graphs, including totally balanced matrices and chordal graphs. an almost-linear time doubly lexical ordering algorithm is given.
a simple parallel algorithm for the maximal independent set problem simple parallel algorithms for the maximal independent set (mis) problem are presented. the first algorithm is a monte carlo algorithm with a very local property. the local property of this algorithm may make it a useful protocol design tool in distributed computing environments and artificial intelligence. one of the main contributions of this paper is the development of powerful and general techniques for converting monte carlo algorithms into deterministic algorithms. these techniques are used to convert the monte carlo algorithm for the mis problem into a simple deterministic algorithm with the same parallel running time.
maximization problems on graphs with edge weights chosen from a normal distribution (extended abstract) we consider optimization problems on complete graphs with edge weights chosen from identical but independent normal distributions. we show some very general techniques for obtaining upper and lower bounds on the asymptotic behavior of these problems. often, but not always, these bounds are equal, enabling us to state the asymptotic behavior of the maximum. problems in which the bounds are tight include finding the optimum traveling salesman tour, finding a minimum cost spanning tree, and finding a heaviest clique on k vertices. we then discuss some greedy heuristic algorithms for these problems.
more analysis of double hashing in [gs78] a deep and elegant analysis showed that double hashing was equivalent to the ideal uniform hashing up to a load factor of about 0.319. in this paper we give an analysis which extends this to load factors arbitrarily close to 1. we understand from [ko86, gu87] that ajtai, guibas, koml&oacute;s, and szemer&eacute;di obtained this result in the first part of 1986; the analysis in this paper is of interest nonetheless because we demonstrate how a resampling technique can be used to obtain a remarkably simple proof.
straight-line program length as a parameter for complexity measures this paper represents a continuation of work in [lbi] and [lb2] directed toward the development of a unified, relative model for complexity theory. the earlier papers establish a simple, natural and fairly general model, and demonstrated its attractiveness by using it to state and prove a variety of technical results. the present paper uses the same model but deals more specifically with the problems involved in stating complexity bounds in a usable closed form for arbitrary operations on arbitrary data types. work currently in progress is directed toward similar unified treatment of complexity of data structures.
fast allocation of nearby resources in a distributed system dijkstra's informally-stated dining philosophers problem [d] involves a number n of philosophers sitting in a circle, a single fork between each pair of adjacent philosophers. the problem is to program the philosophers in ways which guarantee certain conditions of fairness and absence of deadlock. in this paper, the problem is generalized to a distributed system resource allocation problem which is local in two senses. first, although the system and number of users can be very large, there is a limit to the overlap in resource demands of different users. the second condition can be thought of as a property of the geography of the network - the resources are (or can be) located in the network in such a way that communication between a user and any of its required resources is fast.
efficient reducibility between programming systems: preliminary report much of the research on semantic theories has concentrated on qualitative properties such as definability (of such programming concepts as recursive procedures), equivalence (of different language constructs), and verifiability (of the correctness, or consistency, of one expression relative to another). current qualitative theories are in a tentative state and much remains to be done. however, there is also a quantitative side to semantics. indeed, many of the questions which any semantic theory must answer are at once qualitative and quantitative. we would like to draw upon complexity-theoretic techniques to answer such questions. we are currently working on the development of new algebraic constructs to provide a mathematical framework for both qualitative and quantitative analysis of semantic problems.
sets that don't help this paper contains several results yielding pairs of problems which don't help each other's solution, and therefore which may be said to be complex for &ldquo;different reasons.&rdquo; statements are formalized and results proved within blum complexity theory, generalized to relative algorithms. the approach is fairly intuitive; all details appear in [1] and [2].
bounds for the computational power and learning complexity of analog neural nets. it is shown that high-order feedforward neural nets of constant depth with piecewise-polynomial activation functions and arbitrary real weights can be simulated for boolean inputs and outputs by neural nets of a somewhat larger size and depth with heaviside gates and weights from {-1, 0, 1}. this provides the first known upper bound for the computational power of the former type of neural nets. it is also shown that in the case of first-order nets with piecewise-linear activation functions one can replace arbitrary real weights by rational numbers with polynomially many bits without changing the boolean function that is computed by the neural net. in order to prove these results, we introduce two new methods for reducing nonlinear problems about weights in multilayer neural nets to linear problems for a transformed set of parameters. these transformed parameters can be interpreted as weights in a somewhat larger neural net.as another application of our new proof technique we show that neural nets with piecewise-polynomial activation functions and a constant number of analog inputs are probably approximately correct (pac) learnable (in valiant's model for pac learning [comm. assoc. comput. mach., 27 (1984), pp. 1134--1142]).