waashk/dblp huggingface dataset:
shallow multiplication circuits and wise financial investments paterson, pippenger and zwick have recently obtained a general theory that describes the optimal way in which given carry-save adders can be combined into carry-save networks. their work produces, in particular, multiplication circuits of depth 3.71 log* n (these circuits put out two numbers whose sum is the result of the multiplication). in this work an extension of the above general theory is obtained. we now consider carry-save adders that may receive inputs and produce outputs using several different representation methods. we describe the optimal way of utilising any such collection of carry-save adders. the optimality proof uses the min-max theorem of game theory. by using several different representation standards, the depth of multiplication circuits can be surprisingly reduced to 3.48 log* n (again two output numbers are produced). we introduce bit level redundancy by using a novel coding scheme in which each bit is distributed over four wires. interestingly, the information on these four wires is usually not transmitted simultaneously. finally, an analogy is made between the optimisation problem faced by the circuit designer and the optimisation problem faced by an investor, offered a collection of financial investment plans, each involving perhaps several different currencies. this analogy is used to obtain intuitive explanations of the results obtained.
the joy of theory. this talk is meant to be a celebration of theoreticians, thier achievements, and thier unique style, drawing to a large extent on examples from this volume.theoretical computer science has largely succeeded in its core mission, that is, improving a rigorous and productive foundational understanding of the power and limitations of the von neumann computer and its software. and in the past few years it has strived to extend its reach to the internet and the worldwide web, the central computational artifact of our times.but theoreticians have achieved much more than this. our community has identified p vs. np, arguably the deepest and most important mathematical question of our time -- and it is leading the assault on it. in addition we are developing "algorithmic mirrors" through which other sciences (notably physics and biology, with economics and other social sciences soon to join) rediscover, fruitfully, themselves. and we have furthered and influenced crucially combinatorics and logic, the important mathematical fields from which we have drawn methodologically. the newfound respectability and prestige of our parent field, computer science, owes much to these achievements.theoreticians comprise a microcosm with wonderful characteristics: great scientific, social, and intellectual openness; responsibility and mutual respect, but also healthy doses of irreverence, mistrust of the establishment, willingness to experiment, and self-critical spirit; and a strong sense of an international community that is remarkably cohesive and tightly knit while celebrating the diversity of its people, of their backgrounds, and of their scientific interests and approaches.we have also developed a fascinating, complex esthetic of our work based on mathematical elegance and depth, relevance and fashion, timeliness and competition -- but also on playfulness and humor. our esthetic has served us well: some of our most important results were derived by long chains of contributions, each seemingly guided to a large extent by such esthetic considerations. in fact, this esthetic extends delightfully to the exposition of our work, as evidenced by the unique genre of scientific prose known as "focs/stoc abstract".
computing correlated equilibria in multi-player games. we develop a polynomial-time algorithm for finding correlated equilibria (a well-studied notion of rationality due to aumann that generalizes the nash equilibrium) in a broad class of succinctly representable multiplayer games, encompassing essentially all known kinds, including all graphical games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. our algorithm is based on a variant of the existence proof due to hart and schmeidler [11], and employs linear programming duality, the ellipsoid algorithm, markov chain steady state computations, as well as application-specific methods for computing multivariate expectations.
on the faithful regular extensions of iterative algebras in ([6]), tiuryn proved the existence of extensions of algebras with the unique fixed point property (iterative algebras) to ordered algebras with the least fixed point property (regular algebras), extensions preserving the fixed point solutions. the aim of this paper is to prove that whenever the extension is &ldquo;faithful&rdquo;, i.e. obtained without collapsing elements of the carrier, the new regular algebra is again iterative. in section 1 we fix some notations and definitions and state tiuryn's result. section 2 contains the formulation of the problem and a sketch of the proof. section 3 deals with the main construction.
some complexity results for the traveling salesman problem it is shown that, unless p&equil;np, local search algorithms for the traveling salesman problem having polynomial time complexity per iteration will generate solutions arbitrarily far from the optimal. the traveling salesman problem is also shown to be np-complete even if its instances are restricted to be realizable by a set of points on the euclidean plane.
communication complexity in this paper we prove several results concerning this complexity measure. first we establish (in a non-constructive manner) that there exist languages which cannot be recognized with less than n communication (obviously, communication n is always enough for recognizing any language). in fact, we show that for any functionf(n)-&-lt; n, there are languages recognizable with communicationf(n) but not with communicationf (n)-&-minus;1. in other words, this complexity measure possesses a very dense hierarchy or complexity classes, as miniscule increments in communication add to the languages that can be recognized.
on the complexity of matrix product. our main result is a lower bound of $\omega(m^2 \log m)$ for the size of any arithmetic circuit for the product of two matrices, over the real or complex numbers, as long as the circuit does not use products with field elements of absolute value larger than 1 (where m &times; m is the size of each matrix). that is, our lower bound is superlinear in the number of inputs and is applied for circuits that use addition gates, product gates, and products with field elements of absolute value up to 1. we also prove size-depth tradeoffs for such circuits: we show that if a circuit, as above, is of depth d, then its size is $\omega(m^{2+ 1/o(d)})$.
testing metric properties. finite metric spaces, and in particular tree metrics play an important role in various disciplines such as evolutionary biology and statistics. a natural family of problems concerning metrics is deciding, given a matrix m, whether or not it is a distance metric of a certain predetermined type. here we consider the following relaxed version of such decision problems: for any given matrix m and parameter ε, we are interested in determining, by probing m, whether m has a particular metric property p, or whether it is ε-far from having the property. in ε-far we mean that at least an ε-fraction of the entries of m must be modified so that it obtains the property. the algorithm may query the matrix on entries m[i,j] of its choice, and is allowed a constant probability of error.we describe algorithms for testing euclidean metrics, tree metrics and ultrametrics. furthermore, we present an algorithm that tests whether a matrix m is an approximate ultrametric. in all cases the query complexity and running time are polynomial in 1/ε and independent of the size of the matrix. finally, our algorithms can be used to solve relaxed versions of the corresponding search problems in time that is sub-linear in the size of the matrix.
multi-linear formulas for permanent and determinant are of super-polynomial size. an arithmetic formula is multilinear if the polynomial computed by each of its subformulas is multilinear. we prove that any multilinear arithmetic formula for the permanent or the determinant of an n &times; n matrix is of size super-polynomial in n. previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multilinear formulas of constant depth.
bounded-concurrent secure multi-party computation with a dishonest majority. we show how to securely realize any multi-party functionality in a way that preserves security under an a-priori bounded number of concurrent executions, regardless of the number of corrupted parties. previous protocols for the above task either rely on set-up assumptions such as a common reference string, or require an honest majority. our constructions are in the plain model and rely on standard intractability assumptions (enhanced trapdoor permutations and collision resistant hash functions). even though our main focus is on feasibility of concurrent multi-party computation we actually obtain a protocol using only a constant number of communication rounds. as a consequence our protocol yields the first construction of constant-round phstand-alone secure multi-party computation with a dishonest majority, proven secure under standard (polynomial-time) hardness assumptions; previous solutions to this task either require logarithmic round-complexity, or subexponential hardness assumptions. the core of our protocol is a novel construction of (concurrently) simulation-sound zero-knowledge protocols, which might be of independent interest. finally, we extend the framework constructed to give a protocol for secure multi-party (and thus two-party) computation for any number of corrupted parties, which remains secure even when arbitrary subsets of parties concurrently execute the protocol, possibly with interchangeable roles. as far as we know, for the case of two-party or multi-party protocols with a dishonest majority, this is the first positive result for any non-trivial functionality which achieves this property in the plain model.
extractors with weak random seeds. we show how to extract random bits from two or more independent weak random sources in cases where only one source is of linear min-entropy and all other sources are of logarithmic min-entropy. our main results are as follows: a long line of research, starting by nisan and zuckerman[14], gives explicit constructions of seeded-extractors, that is, extractors that use a short seed of truly random bits to extract randomness from a weak random source. for every such extractor e, with seed of length d, we construct an extractor e′, with seed of length d′=o(d), that achieves the same parameters as e but only requires the seed to be of min-entropy larger than (1⁄2+δ) •d′ (rather than fully random), where δ is an arbitrary small constant. fundamental results of chor and goldreich and vazirani [6,21] show how to extract ω(n) random bits from two (independent) sources of length n and min-entropy larger than (1⁄2δ) • n, where δ is an arbitrary small constant. we show how to extract ω(n) random bits (with optimal probability of error) when only one source is of min-entropy (1⁄2+δ) •n and the other source is of logarithmic min entropy.3 a recent breakthrough of barak, impagliazzo and wigderson[4] shows how to extract ω(n) random bits from a constant number of (independent) sources of length n and min-entropy larger than δ n, where δ is an arbitrary small constant. we show how to extract ω (n) random bits (with optimal probability of error) when only one source is of min-entropy δ n and all other (constant number of) sources are of logarithmic min-entropy.a very recent result of barak, kindler, shaltiel, sudakov and wigderson[5] shows how to extract a constant number of random bits from three (independent) sources of length n and min-entropy larger than δn, where δ is an arbitrary small constant. we show how to extract ω(n)/ random bits, with sub-constant probability of error, from one source of min-entropy δ n and two sources of logarithmic min-entropy.in the same paper, barak, kindler, shaltiel, sudakov and wigderson[5] give an explicit coloring of the complete bipartite graph of size 2n x 2n with two colors, such that there is no monochromatic subgraph of size larger than 2δn x 2 2δn, where δ is an arbitrary small constant. we give an explicit coloring of the complete bipartite graph of size 2n x 2n with a constant number of colors, such that there is no monochromatic subgraph of size larger than 2δn x n5.we also give improved constructions of mergers and condensers. in particular, we show that using a constant number of truly random bits, one can condense a source of length n and min-entropy rate δ into a source of length ω (n) and min-entropy rate 1-δ, where δ is an arbitrary small constant.we show that using a constant number of truly random bits, one can merge a constant number of sources of length n, such that at least one of them is of min-entropy rate 1-δ, into one source of length ω(n) and min-entropy rate slightly less than 1-δ, where δ is any small constant.
the complexity of facets (and some facets of complexity) many important combinatorial optimization problems, including the traveling salesman problem (tsp), the clique problem and many others, call for the optimization of a linear functional over some discrete set of vectors.
extractors for a constant number of polynomially small min-entropy independent sources. we consider the problem of randomness extraction from independent sources. we construct an extractor that can extract from a constant number of independent sources of length $n$, each of which have min-entropy $n^\gamma$, for an arbitrarily small constant $\gamma>0$. our extractor is obtained by composing seeded extractors in simple ways. we introduce a new technique to condense independent somewhere-random sources which looks like a useful way to manipulate independent sources. our techniques are different from those used in recent work [b. barak, r. impagliazzo, and a. wigderson, siam j. comput., 36 (2006), pp. 1095-1118; b. barak, g. kindler, r. shaltiel, b. sudakov, and a. wigderson, simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, in proceedings of the 37th annual acm symposium on theory of computing, acm, new york, 2005, pp. 1-10; r. raz, extractors with weak random seeds, in proceedings of the 37th annual acm symposium on theory of computing, acm, new york, 2005, pp. 11-20; j. bourgain, int. j. number theory, 1 (2005), pp. 1-32] for this problem in the sense that they do not rely on any results from arithmetic combinatorics. using an extractor of bourgain's [int. j. number theory, 1 (2005), pp. 1-32] as a black box, we obtain a new extractor for two independent block sources with few blocks, even when the min-entropy is as small as $\operatorname{polylog}(n)$. we also show how to modify the 2 source disperser for linear min-entropy of barak et al. [simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, in proceedings of the 37th annual acm symposium on theory of computing, acm, new york, 2005, pp. 1-10] and the three source extractor of raz [extractors with weak random seeds, in proceedings of the 37th annual acm symposium on theory of computing, acm, new york, 2005, pp. 11-20] to get dispersers/extractors with exponentially small error and linear output length where previously both were constant.
lower bounds for dynamic connectivity. we prove an ω(lg erik n) cell-probe lower bound on maintaining connectivity in dynamic graphs, as well as a more general trade-off between updates and queries. our bound holds even if the graph is formed by disjoint paths, and thus also applies to trees and plane graphs. the bound is known to be tight for these restricted cases, proving optimality of these data structures (e. g., sleator and tarjan's dynamic trees). our trade-off is known to be tight for trees, and the best two data structures for dynamic connectivity in general graphs are points on our trade-off curve. in this sense these two data structures are optimal, and this tightness serves as strong evidence that our lower bounds are the best possible. from a more theoretical perspective, our result is the first logarithmic cell-probe lower bound for any problem in the natural class of dynamic language membership problems, breaking the long standing record of ω(lg n / lg lg n). in this sense, our result is the first data-structure lower bound that is "truly" logarithmic, i. e., logarithmic in the problem size counted in bits. obtaining such a bound is listed as one of three major challenges for future research by miltersen [13] (the other two challenges remain unsolved). our techniques form a general framework for proving cell-probe lower bounds on dynamic data structures. we show how our framework also applies to the partial-sums problem to obtain a nearly complete understanding of the problem in cell-probe and algebraic models, solving several previously posed open problems.
time-space trade-offs for predecessor search. we develop a new technique for proving cell-probe lower bounds for static data structures. previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. we give the first lower bound for an explicit problem which breaks this communication complexity barrier. in addition, our bounds give the first separation between polynomial and near linear space. such a separation is inherently impossible by communication complexity.using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. given a set y of n integers of l bits each, the goal is to efficiently find predecessor (x) = max (y ∈ y | y ≤ x). for this purpose, we represent y on a ram with word length b using s ≥ nl bits of space. defining a = lg s/n, we show that the optimal search time is, up to constant factors: min(logbn, lgl-lg n / n, lg(l/a) / lg(a/lg n * lg l/a), lg (l/a) / lg (lg (l/a) / lg (lg n / a)).in external memory (b > l), it follows that the optimal strategy is to use either standard b-trees, or a ram algorithm ignoring the larger block size. in the important case of b = l = γ lg n, for γ > 1 (i.e. polynomial universes), and near linear space (such as s = n • lgo(1) n), the optimal search time is θ(lg l). thus, our lower bound implies the surprising conclusion that van emde boas' classic data structure from [focs'75] is optimal in this case. note that for space n1+ε, a running time of o(lg l / lg lg l) was given by beame and fich [stoc'99].
on the degree of polynomials that approximate symmetric boolean functions (preliminary version) in this paper, we provide matching (up to a constant factor) upper and lower bounds on the degree of polynomials that represent symmetric boolean functions with an error 1/3. let &ggr;(f)=min{|2k&ndash;n+1|:fk &ne; fk+ 1 and 0 &le; k &le; n &ndash; 1} where fi is the value of f on inputs with exactly i 1's. we prove that the minimum degree over all the approximating polynomials of f is &thgr;((n(n-&ggr;(f))).5). we apply the techniques and tools from approximation theory to derive this result.
a 2.5 n-lower bound on the combinatorial complexity of boolean functions consider the combinational complexity l(f) of boolean functions over the basis &ohgr; &equil; {f&brvbar; f:{0,1}2 &rarr; {0,1}}. a new method for proving linear lower bounds of size 2n is presented. combining it with methods presented in [12] and [15], we establish for a special sequence of functions fn:{0,1}n &rarr; {0,1}: 2.5n &le; l(f) &le 6n. also a trade-off result between circuit complexity and formula size is derived.
on time hierarchies for fixed k &ge; 2 we tighten the time hierarchy for k-tape turing machines. also for fixed k &ge; 2 we exhibit infinite hierarchies of languages recognizable by k-tape machines with increasing amount of time on the same amount of space.
an information-theoretic approach to time bounds for on-line computation (preliminary version) static, descriptional complexity (program size) [16, 9] can be used to obtain lower bounds on dynamic, computational complexity (such as running time). we describe and discuss this &ldquo;information-theoretic approach&rdquo; in the following section. paul introduced it in [13], to obtain restricted lower bounds on the time complexity of sorting. we use the approach here to obtain lower time bounds for on-line simulation of one abstract storage unit by another. a major goal of our work is to promote the approach.
space bounds for a game of graphs we study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. in [3] it was shown that for each graph with n vertices and maximum in-degree d , there is a pebbling strategy which requires at most c(d) n/log n pebbles. here we show that this bound is tight to within a constant factor. we also analyze a variety of pebbling algorithms, including one which achieves the 0(n/log n) bound.
on point location and motion planning among simplices. let $\ss$ be a set of $n$ possibly intersecting $(d-1)$-simplices in $d$-space for $d \geq 2$, and let ${\cal a}(\ss)$ be the arrangement of $\ss$. let $k = |{\cal a}(\ss)|$ be the number of faces of any dimension in the arrangement of $\ss$. a data structure is described that uses storage $o(n^{d-1+\eps} +k)$ and is built {\em deterministically} in time $o(n^{d-1+\eps} +k\log n)$, where $\eps >0$ is an arbitrarily small constant, such that the face of ${\cal a}(\ss)$ containing a query point is located in time $o(\log^3 n)$. if two query points are in the same cell of ${\cal a}(\ss)$, a collision-free path connecting them is produced. this result is obtained by exploiting powerful and so far overlooked properties of sparse nets introduced by chazelle [{\em discrete comput. geom.}, 9 (1993), pp. 145--158]. if the $(d-1)$-simplices in $\ss$ have pairwise-disjoint interiors and $d \geq 3$, improved bounds are obtained. a data structure is described that uses $o(n^{d-1})$ storage and is built deterministically in time $o(n^{d-1})$ such that point-location queries are solved in time $o(\log n)$. also, as a by-product, this method gives the first optimal worst-case algorithm for triangulating a nonsimple polyhedron in 3-space.
intercalation theorems for tree transducer languages we develop intercalation lemmas for the computations of the top-down tree transducers defined by rounds [15] and thatcher [17]. these lemmas are used to prove necessary conditions for languages all of whose strings are of exponential length to be tree transducer languages. the language {ww:w&egr;{a,b}*, &brvbar;w&brvbar;&equil;2n,n&ge;0}, which is generable by the composition of two transducers, is shown not to be generable by one. the proof technique applies to bottom-up transducers as well. the results are related to some subclasses of woods' augmented transition networks [18] characterized elsewhere in terms of tree transducer languages [14].
on the relationship between finite automata, finite monoids, and prefix codes it is the aim of the present study to establish links between the structure of a given (finite) prefixcode and that of its syntactic monoid, using automata theory as a tool.