Multi-unit auctions are a paradigmatic model of resource allocation , where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. We design a best possible envy-free and prior-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem , showing that truthfulness requires discarding resources and is thus incompatible with (Pareto) efficiency. • We consider multi-unit auctions with budgets and design a best possible envy-free and prior-free mechanism. • The mechanism approximates the optimal revenue and welfare within constant factors. • For welfare, the approximation converges to 1 as the market becomes fully competitive.

Multi-unit auctions are a paradigmatic model, where a seller brings multiple units of a good, while several buyers bring monetary endowments. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. In this paper we design an optimal envy-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources, and in particular, is incompatible with (Pareto) efficiency.

This issue of SICOMP contains seven specially selected papers from STOC 2013, the Forty-Fifth Annual ACM Symposium on the Theory of Computing, which was held June 1 through 4, 2013, in Palo Alto, California. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough the reviewing process of SICOMP. The program committee for STOC 2013 consisted of an executive committee made up of Boaz Barak, Irit Dinur, Leslie Goldberg, Giuseppe F. Italiano, Sampath Kannan, Neeraj Kayal, Michael Mitzenmacher, and Miklos Santha, supervising a broader program committee made up of Scott Aaronson, Susanne Albers, Benny Applebaum, James Aspnes, Per Austrin, Avrim Blum, Anne Broadbent, Peter Bürgisser, John Byers, Amit Chakrabarti, Shuchi Chawla, Bernard Chazelle, Xi Chen, Julia Chuzhoy, Graham Cormode, Artur Czumaj, Constantinos Daskalakis, Zeev Dvir, Jeff Erickson, Lance Fortnow, Craig Gentry, Anna Gilbert, Sudipto Guha, Mohammed Taghi Hajiaghayi, Moritz Hardt, Avinatan Hassidim, Monika Henzinger, Maurice Herlihy, Nicole Immorlica, Russell Impagliazzo, Piotr Indyk, Yuval Ishai, Mark Jerrum, Yael Kalai, Tali Kaufman, Haim Kaplan, Jonathan Kelner, Valerie King, Samir Khuller, Robert Kleinberg, Elias Koutsoupias, Robert Krauthgamer, Pinyan Lu, Aleksander Madry, Dániel Marx, Peter Bro Miltersen, Moni Naor, Ilan Newman, Rina Panigrahy, Prasad Raghavendra, Andrea Richa, Michael Schapira, Rocco Servedio, Amir Shpilka, Cliff Stein, David Steurer, Mikkel Thorup, Virginia Vassilevska Williams, Eric Vigoda, Ryan Williams, Ronald de Wolf, and David Zuckerman. The program chair was Joan Feigenbaum. Included in this issue are the following papers: ``An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube," by Deeparnab Chakrabarty and C. Seshadhri, provides a randomized tester for near-monotone functions requiring sublinear queries. ``Answering $n^{2+o(1)}$ Counting Queries with Differential Privacy Is Hard," by Jonathan Ullman, gives a nearly tight bound on the number of counting queries that can be answered while preserving privacy. ``Natural Proofs Versus Derandomization," by Ryan Williams, demonstrates surprising connections between natural proofs, derandomization, and weak circuit lower bounds. ``Approximating $k$-median via Pseudo-Approximation," by Shi Li and Ola Svensson, improves the approximation ratio for $k$-median from $3+\epsilon$ to $1 + \sqrt{3} + \epsilon$, the first improvement in a decade. ``Maintaining Shortest Paths under Deletions in Weighted Directed Graphs," by Aaron Bernstein, improves on previous algorithms for maintaining all-pairs approximate shortest paths. ``The Geometry of Differential Privacy: The Sparse and Approximate Cases," by Aleksandar Nikolov, Kunal Talwar, and Li Zhang, characterizes the trade-offs between accuracy and privacy for a rich class of database queries. ``Superlinear Advantage for Exact Quantum Algorithms," by Andris Ambainis, gives the first example of a function that can be computed with a sublinear number of queries compared to the corresponding deterministic algorithm. We thank the authors, the STOC 2013 program committee, the STOC 2013 external reviewers, and the SICOMP referees for all of their hard work.

The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 ( the leader ) first commits to a strategy that is publicly announced, then Player 2 ( the follower ) plays a best response to the leader’s choice. We study Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximate algorithms, and hardness results for finding equilibria for several classes of such two-player games. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We survey recent applications of real algebraic and semi-algebraic geometry in (computational) game theory.

We consider the fundamental mechanism design problem of approximate social welfare maximization under general cardinal preferences on a finite number of alternatives and without money . The well-known range voting scheme can be thought of as a non-truthful mechanism for exact social welfare maximization in this setting. With m being the number of alternatives, we exhibit a randomized truthful-in-expectation ordinal mechanism with approximation ratio Ω( m − 3/4 ). On the other hand, we show that for sufficiently many agents, the approximation ratio of any truthful-in-expectation ordinal mechanism is O ( m − 2/3 ). We supplement our results with an upper bound for any truthful-in-expectation mechanism. We get tighter bounds for the natural special case of m = 3, and in that case furthermore obtain separation results concerning the approximation ratios achievable by natural restricted classes of truthful-in-expectation mechanisms. In particular, we show that the best cardinal truthful mechanism strictly outperforms all ordinal ones. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Ye [2011] showed recently that the simplex method with Dantzig’s pivoting rule, as well as Howard’s policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that both algorithms terminate after at most O ( mn 1− γ log n 1− γ ) iterations, where n is the number of states, m is the total number of actions in the MDP, and 0 < γ < 1 is the discount factor. We improve Ye’s analysis in two respects. First, we improve the bound given by Ye and show that Howard’s policy iteration algorithm actually terminates after at most O ( m 1− γ log n 1− γ ) iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement ) algorithm, a generalization of Howard’s policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games, solving a long standing open problem. Combined with other recent results, this provides a complete characterization of the complexity the standard strategy iteration algorithm for 2-player turn-based stochastic games; it is strongly polynomial for a fixed discount factor, and exponential otherwise.

Emek et al presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) pure signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal mixed signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.

Starting from Zermelo’s classical formal treatment of chess, we trace through history the analysis of two-player win/lose/draw games with perfect information and potentially infinite play. Such chess-like games have appeared in many different research communities, and methods for solving them, such as retrograde analysis, have been rediscovered independently. We then revisit Washburn’s deterministic graphical games (DGGs), a natural generalization of chess-like games to arbitrary zero-sum payoffs. We study the complexity of solving DGGs and obtain an almost-linear time comparison-based algorithm for finding optimal strategies in such games. The existence of a linear time comparison-based algorithm remains an open problem.

Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly solving these games. When the number of positions of the game isbconstant, our algorithms run in polynomial time.

We exhibit a deterministic concurrent reachability game PURGATORY$_n$ with $n$ non-terminal positions and a binary choice for both players in every position so that any positional strategy for Player 1 achieving the value of the game within given $\epsilon

We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: (a) the Blum–Shub–Smale model of computation over the reals; and (b) a problem we call the “generic task of numerical computation,” which captures an aspect of doing numerical computation in floating point, similar to the “long exponent model” that has been studied in the numerical computing community. We show that both of these approaches hinge on the question of understanding the complexity of the following problem, which we call PosSLP: Given a division-free straight-line program producing an integer N, decide whether $N>0$. In the Blum–Shub–Smale model, polynomial-time computation over the reals (on discrete inputs) is polynomial-time equivalent to PosSLP when there are only algebraic constants. We conjecture that using transcendental constants provides no additional power, beyond nonuniform reductions to PosSLP, and we present some preliminary results supporting this conjecture. The generic task of numerical computation is also polynomial-time equivalent to PosSLP. We prove that PosSLP lies in the counting hierarchy. Combining this with work of Tiwari, we obtain that the Euclidean traveling salesman problem lies in the counting hierarchy—the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE. In the course of developing the context for our results on arithmetic circuits, we present some new observations on the complexity of the arithmetic circuit identity testing (ACIT) problem. In particular, we show that if $n!$ is not ultimately easy, then ACIT has subexponential complexity.

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n-bit data with s=n+r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. In this paper, we consider the case of succinct representations, where s=n+r for some redundancy r≪n. For a Boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy–query time tradeoff of the form (r+1)t≥Ω(n/logn). In particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial properties of a coding theoretic flavor, and obtain (r+1)t≥Ω(n) for certain problems. Previously, no ω(m) lower bounds were known on t in the general model for explicit Boolean problems, even for very small redundancies. By restricting our attention to systematic or index structures ϕ satisfying ϕ(x)=x⋅ϕ∗(x) for some map ϕ∗ (where ⋅ denotes concatenation), we show similar lower bounds on the redundancy–query time tradeoff for the natural data structuring problems of Prefix Sum and Substring Search.

We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the following problem, which we call PosSLP; given a division-free straight-line program producing an integer N, decide whether N > 0. We show that PosSLP lies in the counting hierarchy, and combining our results with work of Tiwari, we show that the Euclidean traveling salesman problem lies in the counting hierarchy - the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some ε > 0, some language in NE ∩ coNE requires nondeterministic circuits of size 2ε n This improves results of Arvind and Köbler and of Klivans and van Melkebeek who proved the same conclusion, but under stronger hardness assumptions. The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim’s hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy proof of the following implication: for some ε > 0, if there is a language in E which requires nondeterministic circuits of size 2ε n , then P = BPP. This differs from Impagliazzo and Wigderson’s theorem “only” by replacing deterministic circuits with nondeterministic ones.

We study how big the blow-up in size can be when one switches between the CNF and DNF representations of Boolean functions. For a function f:{0,1}n→{0,1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0⩽m⩽2n-1, let dnfsize(m,n) be the maximum dnfsize(f) for a function f:{0,1}n→{0,1} with cnfsize(f)⩽m. We show that there are constants c1,c2⩾1 and ε>0, such that for all large n and all m∈[1εn,2εn], we have2n-c1(n/log(m/n))⩽dnfsize(m,n)⩽2n-c2(n/log(m/n)).In particular, when m is the polynomial nc, we get dnfsize(nc,n)=2n-θ(c-1(n/logn)).

In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map f : {0,1}^n * {0,1}^m -> {0,1}, where {0,1}^n is a set of possible data to be stored, {0,1}^m is a set of possible queries (for natural problems, we have m << n) and f(x,y) is the answer to question y about data x. A solution is given by a representation phi : {0,1}^n -> {0,1}^s and a query algorithm q so that q(phi(x), y) = f(x,y). The time t of the query algorithm is the number of bits it reads in phi(x). In this paper, we consider the case of succinct representations where s = n + r for some redundancy r << n. For a boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy-query time trade-off of the form (r + 1) t >= Omega(n/log n). In particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial property of a coding theoretic flavor. Previously, no omega(m) lower bounds were known on t in the general model for explicit functions, even for very small redundancies. By restricting our attention to systematic or index structures phi satisfying phi(x) = x · phi*(x) for some map phi* (where · denotes concatenation) we show similar lower bounds on the redundancy-query time trade-off for the natural data structuring problems of Prefix Sum and Substring Search.

We study the it static membership problem: Given a set S of at most n keys drawn from a universe U of size m, store it so that queries of the form "Is u in S?" can be answered by making few accesses to the memory. We study schemes for this problem that use space close to the information theoretic lower bound of $\Omega(n\log(\frac{m}{n}))$ bits and yet answer queries by reading a small number of bits of the memory. We show that, for $\epsilon > 0$, there is a scheme that stores $O(\frac{n}{\epsilon^2}\log m)$ bits and answers membership queries using a randomized algorithm that reads just one bit of memory and errs with probability at most $\epsilon$. We consider schemes that make no error for queries in S but are allowed to err with probability at most $\epsilon$ for queries not in S. We show that there exist such schemes that store $O((\frac{n}{\epsilon})^2 \log m)$ bits and answer queries using just one bitprobe. If multiple probes are allowed, then the number of bits stored can be reduced to $O(n^{1+\delta}\log m)$ for any $\delta > 0$. The schemes mentioned above are based on probabilistic constructions of set systems with small intersections. We show lower bounds that come close to our upper bounds (for a large range of n and $\epsilon$): Schemes that answer queries with just one bitprobe and error probability $\epsilon$ must use $\Omega(\frac{n}{\epsilon\log(1/\epsilon)} \log m)$ bits of storage; if the error is restricted to queries not in S, then the scheme must use $\Omega(\frac{n^2}{\epsilon^2 \log (n/\epsilon)}\log m)$ bits of storage. We also consider deterministic schemes for the static membership problem and show tradeoffs between space and the number of probes.

The CD complexity of a string x is the length of the shortest polynomial time program which accepts only the string x. The language compression problem consists of giving an upper bound on the CD(A/sup /spl les/n/) complexity of all strings x in some set A. The best known upper bound for this problem is 2log(/spl par/A/sup /spl les/n//spl par/)+O(log(n)), due to Buhrman and Fortnow. We show that the constant factor 2 in this bound is optimal. We also give new bounds for a certain kind of random sets R/spl sube/{0, 1}/sup n/, for which we show an upper bound of log (/spl par/R/sup /spl les/n//spl par/)+O(log(n)).

We study the static membership problem: Given a set S of at most n keys drawn from a universe of size m, store it so that queries of the form "Is x in S?" can be answered quickly.We study schemes for this problem that use space close to the information theoretic lower bound of 12(nlog(~)) bits and yet answer queries by reading a small number of bits of the memory.We show that there is a randomized scheme with error e that stores O(;~-logm) bits and answers queries using a single bitprobe.It is based on a family of sets with small intersections.If the error is required to be restricted to queries not in S, then we have a scheme that stores o((n) 2 logm) bits, answers queries with one bitprobe and works with probability of error less than e.We also show that better schemes with one-sided error can be obtained if more probes are allowed.We show lower bounds that come close to our upper bounds (for a large range of n and e): Schemes that answer queries with just one bitprobe and error probability e must use f~(~ log m) bits of storage; if the error is restricted to r~ 2 queries not in S, then the scheme must use ~(~ log m) bits of storage.We also consider deterministic schemes for the static membership problem and show upper and lower bounds.Ijaikumar, venkat}@tcs.tifr.

In this paper we show several results about monotone planar circuits. We show that monotone planar circuits of bounded width, with access to negated input variables, compute exactly the functions in non-uniform AC/sup 0/. This provides a striking contrast to the non-planar case, where exactly NC/sup 1/ is computed. We show that the circuit value problem for monotone planar circuits, with inputs on the outerface only, can be solved in LOGDCFL/spl sube/SC, improving a LOGCFL upper bound due to Dymond and Cook. We show that for monotone planar circuits, with inputs on the outerface only, excessive depth compared to width is useless; any function computed by a monotone planar circuit of width w with inputs on the outerface can be computed by a monotone planar circuit of width O(w) and depth w/sup O(1)/. Finally, we show that monotone planar read-once circuits, with inputs on the outerface only, can be efficiently learned using membership queries.

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some /spl epsiv/>0, some language in NE/spl cap/ coNE requires nondeterministic circuits of size 2/sup en/. This improves results of Arvind and Kobler (1997) and of Klivans and Van Melkebeek (1999) who have proven the same conclusion, but under stronger hardness assumptions, namely, either the existence of a language in NE/spl cap/ coNE which cannot be approximated by nondeterministic circuits of size less than 2/sup en/ or the existence of a language in NE/spl cap/ coNE which requires oracle circuits of size 2/sup en/ with oracle gates for SAT (satisfiability). The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim's (1996) hitting set approach to derandomization. As a spin-off we show that this approach is strong enough to give an easy (if the existence of explicit dispersers can be assumed known) proof of the following implication: for some /spl epsiv/>0, if there is a language in E which requires nondeterministic circuits of size 2/sup en/, then P=BPP. This differs from Impagliazzo and Wigderson's (1995) theorem "only" by replacing deterministic circuits with nondeterministic ones.

We prove that at least 3k−4/k(2k−3)(n/2) – O(k)equivalence tests and no more than 2/k (n/2) + O(n) equivalence tests are needed in the worst case to identify the equivalence classes with at least k members in set of n elements. The upper bound is an

Consider the set ℋ of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good ℋ is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from ℋ and look at the expected size of the largest hash bucket. ℋ is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently. If the finite field F has n elements, then there is a bad set S ⊂ F 2 of size n with expected maximal bucket size Ω( n 1/3 ). If n is a perfect square, then there is even a bad set with largest bucket size always at least √n. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below √ + 1/2.) If, however, we consider the field of two elements, then we get much better bounds. The best previously known upper bound on the expected size of the largest bucket for this class was O (2 √ log n ). We reduce this upper bound to O (log n log log n ). Note that this is not far from the guarantee for a random function. There, the average largest bucket would be Θ (log n / log log n ). In the course of our proof we develop a tool which may be of independent interest. Suppose we have a subset S of a vector space D over Z 2 , and consider a random linear mapping of D to a smaller vector space R . If the cardinality of S is larger than c ε | R |log| R |, then with probability 1 - ϵ, the image of S will cover all elements in the range.

We show that searching a width k maze is complete for Pi_k, i.e., for the k'th level of the AC0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for Pi_k. As an application, we show that there is a data structure solving dynamic st-connectivity for constant width grid graphs with time bound O(log log n) per operation on a random access machine. The dynamic algorithm is derived from the parallel one in an indirect way using algebraic tools.

Let M be a fixed finite monoid.We consider the problem of implementing a data type containing a vector x ϭ ( x 1 , x 2 , . . ., x n ) ʦ M n , initially (1, 1, . . ., 1), with two kinds of operations, for each i ʦ {1, . . ., n} and a ʦ M, an operation change i,a which changes x i to a and a single operation product returning ͟ iϭ1 n x i .This is the dynamic word problem for M. If we in addition for each j ʦ {1, . . ., n} have an operation prefix j returning ͟ iϭ1 j x i , we get the dynamic prefix problem for M. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits.We obtain a partial classification of the complexity based on algebraic properties of M.

In this paper we consider solutions to the static dictionary problem on AC/sup 0/ RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC/sup 0/. Our main result is a tight upper and lower bound of /spl theta/(/spl radic/log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2/sup polylog n/. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth /spl Omega/(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984).

Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x 1 ≤ x 2 ≤ … ≤ x m and n elements y 1 ≤ y 2 ≤ … ≤ y m , where n ≥ m. Batcher's odd-even merge yields the following upper bound: M(m,n) ≤ ½(m + n)log 2 m + O(n); in particular, M(n,n) ≤ n log 2 n + o(n) We prove the following lower bound that matches the upper bound above asymptotically as n ≥ m →∞; M(m,n) ≥ ½(m+n)log 2 m - O(m) in particular, M(n,n) ≥ n log 2 - O(n). Our proof technique extends to give similarily tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.

In this paper we consider two-party communication complexity, the "asymmetric case", when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we study trade-offs between the number of bits the first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model. We derive two generally applicable methods of proving lower bounds and obtain several applications. These applications include new lower bounds for data structures in the cell probe model. Of particular interest is our "round elimination" lemma, which is interesting also for the usual symmetric communication case. This lemma generalizes and abstracts in a very clean form the "round reduction" techniques used in many previous lower bound proofs.

We prove fl(~i) lower bounds on the random access machine complexity of several dynamic, partially dynamic and static data structure prob-

Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x=(x/sub 1/,x/sub 2/,...,x/sub n/)/spl isin/M/sup n/, initially (1,1,...,1) with two kinds of operations, for each i/spl isin/{1,...,n}, a/spl isin/M, an operation change/sub i,a/ which changes x/sub i/ to a and a single operation product returning /spl Pi//sub i=1//sup n/x/sub i/. This is the dynamic word problem. If we in addition for each j/spl isin/{1,...,n} have an operation prefix/sub j/ returning /spl Pi//sub i=1//sup j/x/sub i/, we talk about the dynamic prefix problem. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits. We obtain a classification of the complexity based on algebraic properties of M.>

This paper analyzes the concept of malignness, which is the property of probability ensembles making the average case running time equal to the worst case running time for a class of algorithms. The author derives lower and upper bounds on the complexity of malign ensembles, which are tight for exponential time algorithms, and which show that no polynomial time computable malign ensemble exists for the class of polynomial time algorithms. Furthermore, it is shown that for no class of superlinear algorithms a polynomial time samplable malign ensemble exists, unless every language in P has an expected polynomial time constructor.

Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x/sub 1/or=m. Batcher's odd-even merge yields the following upper bound: M(m,n)or=m to infinity :M(m,n)>or=/sup 1///sub 2/(m+n)log/sub 2/(m+1)-O(m); in particular, M(n,n)>or=nlog/sub 2/n-O(n). The authors' proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.>