The "EIP-1559 algorithm" is used by the Ethereum blockchain to assemble transactions into blocks. While prior work has studied it under the assumption that bidders are "impatient", we analyze it under the assumption that bidders are "patient", which better corresponds to the fact that unscheduled transactions remain in the mempool and can be scheduled at a later time. We show that with "patient" bidders, this algorithm produces schedules of near-optimal welfare, provided it is given a mild resource augmentation (that does not increase with the time horizon). We prove some generalizations of the basic theorem, establish lower bounds that rule out several candidate improvements and extensions, and propose several questions for future work.

We study the problem of designing a two-sided market (double auction) to maximize the gains from trade (social welfare) under the constraints of (dominant-strategy) incentive compatibility and budget-balance. Our goal is to do so for an unknown distribution from which we are given a polynomial number of samples. Our first result is a general impossibility for the case of correlated distributions of values even between just one seller and two buyers, in contrast to the case of one seller and one buyer (bilateral trade) where this is possible. Our second result is an efficient learning algorithm for one seller and two buyers in the case of independent distributions which is based on a novel algorithm for computing optimal mechanisms for finitely supported and explicitly given independent distributions. Both results rely heavily on characterizations of (dominant-strategy) incentive compatible mechanisms that are strongly budget-balanced.

We study Proportional Response Dynamics (PRD) in linear Fisher markets, where participants act asynchronously. We model this scenario as a sequential process in which at each step, an adversary selects a subset of the players to update their bids, subject to liveness constraints. We show that if every bidder individually applies the PRD update rule whenever they are included in the group of bidders selected by the adversary, then, in the generic case, the entire dynamic converges to a competitive equilibrium of the market. Our proof technique reveals additional properties of linear Fisher markets, such as the uniqueness of the market equilibrium for generic parameters and the convergence of associated no swap regret dynamics and best response dynamics under certain conditions.

We consider the query complexity of cake cutting in the standard query model and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing contiguous envy-free allocations among $n=3$ players and for computing perfect and equitable allocations with minimum number of cuts between $n=2$ players. For $\epsilon$-envy-free allocations with contiguous pieces, we also give an upper bound of $O(n/\epsilon)$ and lower bound of $\Omega(\log(1/\epsilon))$ queries for any number $n \geq 3$ of players.We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.

The usage of automated learning agents is becoming increasingly prevalent in many online economic applications such as online auctions and automated trading. Motivated by such applications, this paper is dedicated to fundamental modeling and analysis of the strategic situations that the users of automated learning agents are facing. We consider strategic settings where several users engage in a repeated online interaction, assisted by regret-minimizing learning agents that repeatedly play a "game" on their behalf. We propose to view the outcomes of the agents' dynamics as inducing a "meta-game" between the users. Our main focus is on whether users can benefit in this meta-game from "manipulating" their own agents by misreporting their parameters to them. We define a general framework to model and analyze these strategic interactions between users of learning agents for general games and analyze the equilibria induced between the users in three classes of games. We show that, generally, users have incentives to misreport their parameters to their own agents, and that such strategic user behavior can lead to very different outcomes than those anticipated by standard analysis.

We analyze a scenario in which software agents implemented as regret-minimizing algorithms engage in a repeated auction on behalf of their users. We study first-price and second-price auctions, as well as their generalized versions (e.g., as those used for ad auctions). Using both theoretical analysis and simulations, we show that, surprisingly, in second-price auctions the players have incentives to misreport their true valuations to their own learning agents, while in first-price auctions it is a dominant strategy for all players to truthfully report their valuations to their agents.

We introduce a “concrete complexity” model for studying algorithms for matching in bipartite graphs. The model is based on the “demand query” model used for combinatorial auctions. Most (but not all) known algorithms for bipartite matching seem to be translatable into this model including exact, approximate, sequential, parallel, and online ones. A perfect matching in a bipartite graph can be found in this model with O(n3/2) demand queries (in a bipartite graph with n vertices on each side) and our main open problem is to either improve the upper bound or prove a lower bound. An improved upper bound could yield “normal” algorithms whose running time is better than the fastest ones known, while a lower bound would rule out a faster algorithm for bipartite matching from within a large class of algorithms. Our main result is a lower bound for finding an approximately maximum size matching in parallel: A deterministic algorithm that runs in no(1) rounds, where each round can make at most n1.99 demand queries cannot find a matching whose size is within no(1) factor of the maximum. This is in contrast to randomized algorithms that can find a matching whose size is 99% of the maximum in O(log n) rounds, each making n demand queries.

We obtain a description of the Bipartite Perfect Matching decision problem as a multilinear polynomial over the Reals. We show that it has full degree and (1−on(1))· 2n2 monomials with non-zero coefficients. In contrast, we show that in the dual representation (switching the roles of 0 and 1) the number of monomials is only exponential in Θ(n logn). Our proof relies heavily on the fact that the lattice of graphs which are “matching-covered” is Eulerian.

We study a communication variant of local search. There is some fixed, commonly known graph G. Alice holds fA and Bob holds fB, both are functions that specify a value for each vertex. The goal is to find a local maximum of fA+fB with respect to G, i.e., a vertex v for which (fA+fB)(v)≥ (fA+fB)(u) for each neighbor u of v.

We study a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade their goods at the market and then use the bundles received as inputs for the production in the next round. The decision that players have to make is how to invest their money (i.e. bids) in each round. We show that a simple decentralized dynamic, where players update their bids on the goods in the market proportionally to how useful the investments were, leads to growth of the economy in the long term (whenever growth is possible) but also creates unbounded inequality, i.e. very rich and very poor players emerge. We analyze several other phenomena, such as how the relation of a player with others influences its development and the Gini index of the system.

We study revenue maximization by deterministic mechanisms for the simplest case for which Myerson's characterization does not hold: a single seller selling two items, with independently distributed values, to a single additive buyer. We prove that optimal mechanisms are submodular and hence monotone. Furthermore, we show that in the IID case, optimal mechanisms are symmetric. Our characterizations are surprisingly non-trivial, and we show that they fail to extend in several natural ways, e.g. for correlated distributions or more than two items. In particular, this shows that the optimality of symmetric mechanisms does not follow from the symmetry of the IID distribution.

We consider a price competition between two sellers of perfect-complement goods. Each seller posts a price for the good it sells, but the demand is determined according to the sum of prices. This is a classic model by Cournot (1838), who showed that in this setting a monopoly that sells both goods is better for the society than two competing sellers. We show that non-trivial pure Nash equilibria always exist in this game. We also quantify Cournot's observation with respect to both the optimal welfare and the monopoly revenue. We then prove a series of mostly negative results regarding the convergence of best response dynamics to equilibria in such games.

We suggest a general method for inferring players' values from their actions in repeated games. The method extends and improves upon the recent suggestion of (Nekipelov et al., EC 2015) and is based on the assumption that players are more likely to exhibit sequences of actions that have lower regret. We evaluate this "quantal-regret" method on two different datasets from experiments of repeated games with controlled player values: those of (Selten and Chmura, AER 2008) on a variety of two-player 2x2 games and our own experiment on ad-auctions (Noti et al., WWW 2014). We find that the quantal-regret method is consistently and significantly more precise than either "classic" econometric methods that are based on Nash equilibria, or the "min-regret" method of (Nekipelov et al., EC 2015).

We consider a monopolist that is selling n items to a single additive buyer, where the buyer's values for the items are drawn according to independent distributions F1,F2,…,Fn that possibly have unbounded support. It is well known that - unlike in the single item case - the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. It is also known that simple auctions with a finite bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, the question of the possibility of extracting an arbitrarily high fraction of the optimal revenue via a finite menu size remained open.

We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.

Using data obtained in a controlled ad-auction experiment that we ran, we evaluate the regret-based approach to econometrics that was recently suggested by Nekipelov, Syrgkanis, and Tardos (EC 2015). We found that despite the weak regret-based assumptions, the results were (at least) as accurate as those obtained using classic equilibrium-based assumptions. En route we studied to what extent humans actually minimize regret in our ad auction, and found a significant difference between the ``high types'' (players with a high valuation) who indeed rationally minimized regret and the ``low types'' who significantly overbid. We suggest that correcting for these biases and adjusting the regret-based econometric method may improve the accuracy of estimated values.

Summary form only given. A classical point of view in Economic Theory is that prices in markets serve as a communication mechanism between the participants (buyers and sellers) in the market. I will analyze the communication complexity (in the standard sense used in Theoretical Computer Science) required for obtaining efficiency and equilibrium in several scenarios of markets of indivisible goods.

We consider a network of sellers, each selling a single product, where the graph structure represents pair-wise complementarities between products. We study how the network structure affects revenue and social welfare of equilibria of the pricing game between the sellers. We prove positive and negative results, both of "Price of Anarchy" and of "Price of Stability" type, for special families of graphs (paths, cycles) as well as more general ones (trees, graphs). We describe best-reply dynamics that converge to non-trivial equilibrium in several families of graphs, and we use these dynamics to prove the existence of approximately-efficient equilibria.

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can be computed by a shallow decision tree. While this conjecture implies that smooth functions are easy to compute in the simplest computational model, to date no non-trivial upper bounds were known for such functions in any computational model, including unrestricted Boolean circuits. Even a bound on the description length of such functions better than the trivial 2n does not seem to have been known.

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent's valuations are unknown to the central planner, and therefore communication is required to determine an efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is n, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n1/(r+1)-approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size. We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each agent is nε(r), the approximation ratio of any r-round (randomized) protocol is no better than Ω(n1/5r+1), implying an Ω(log log n) lower bound on the rate of convergence of the market to equilibrium. Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14].

Border's theorem gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment, and it has several applications in economic and algorithmic mechanism design. All known generalizations of Border's theorem either restrict attention to relatively simple settings, or resort to approximation. This paper identifies a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art. We also identify a surprisingly tight connection between Myerson's optimal auction theory, when applied to public project settings, and some fundamental results in the analysis of Boolean functions.

The Gale-Shapley algorithm for the Stable Marriage Problem is known to take Θ(n2) steps to find a stable marriage in the worst case, but only Θ(n log n) steps in the average case (with n women and n men). In 1976, Knuth asked whether the worst-case running time can be improved in a model of computation that does not require sequential access to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that Θ(n2) queries are required in a model that allows certain natural random-access queries to the participants' preferences. A significantly more general — albeit slightly weaker — lower bound follows from Segal's elaborate analysis of communication complexity, namely that Ω(n2) Boolean queries are required in order to find a stable marriage, regardless of the set of allowed Boolean queries. Using a reduction to the communication complexity of the disjointness problem, we give a far simpler, yet significantly more powerful argument showing that Ω(n2) Boolean queries of any type are indeed required. Notably, unlike Segal's lower bound, our lower bound generalizes also to (A) randomized algorithms, (B) finding approximately-stable marriages (C) verifying the stability (or the approximate stability) of a proposed marriage, (D) allowing arbitrary separate preprocessing of the women's preferences profile and of the men's preferences profile, and (E) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage.

Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research in economics, initiated by Hurwicz (1972), is devoted to understanding how such markets perform when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported demands, finding clearing prices in the reported market via an ascending price tatonnement procedure, and returns the resulting allocation. Similar mechanisms are used, for example, in the daily opening of the New York Stock Exchange and the call market for copper and gold in London.

We study the necessity of interaction between individuals for obtaining approximately efficient economic allocations. We view this as a formalization of Hayek's classic point of view that focuses on the information transfer advantages that markets have relative to centralized planning. We study two settings: combinatorial auctions with unit demand bidders (bipartite matching) and combinatorial auctions with subadditive bidders. In both settings we prove that non-interactive protocols require exponentially larger communication costs than interactive ones, even those that only use a modest amount of interaction.

We consider a single buyer with a combinatorial preference that would like to purchase related products and services from different vendors,where each vendor supplies exactly one product. We study the general case where subsets of products can be substitutes as well as complementary and analyze the game that is induced on the vendors, where a vendor's strategy is the price that he asks for his product. This model generalizes both Bertrand competition (where vendors are perfect substitutes) and Nash bargaining (where they are perfect complements), and captures a wide variety of scenarios that can appear in complex crowd sourcing or in automatic pricing of related products.

We performed controlled experiments of human participants in a continuous sequence of ad auctions, similar to those used by Internet companies. The goal of the research was to understand users' strategies in making bids. We studied the behavior under two auction types: (1) the Generalized Second-Price (GSP) auction and (2) the Vickrey--Clarke--Groves (VCG) payment rule, and manipulated also the participants' knowledge conditions: (1) explicitly given valuations and (2) payoff information from which valuations could be deduced. We found several interesting behaviors, among them are: No convergence to equilibrium was detected; moreover the frequency with which participants modified their bids increased with time. We can detect explicit "better-response" behavior rather than just mixed bidding. While bidders in GSP auctions do strategically shade their bids, they tend to bid higher than theoretically predicted by the standard VCG-like equilibrium of GSP. Bidders who are not explicitly given their valuations but can only deduce them from their gains behave a little less "precisely" than those with such explicit knowledge, but mostly during an initial learning phase. VCG and GSP yield approximately the same (high) social welfare, but GSP tends to give higher revenue.

We study scenarios where multiple sellers of a homogeneous good compete on prices, where each seller can only sell to some subset of the buyers. Crucially, sellers cannot price-discriminate between buyers. We model the structure of the competition by a graph (or hyper-graph), with nodes representing the sellers and edges representing populations of buyers. We study equilibria in the game between the sellers, prove that they always exist, and present various structural, quantitative, and computational results about them. We also analyze the equilibria completely for a few cases. Many questions are left open.

We consider the menu size of auctions as a measure of auction complexity and study how it affects revenue. Our setting has a single revenue-maximizing seller selling two or more heterogeneous items to a single buyer whose private values for the items are drawn from a (possibly correlated) known distribution, and whose valuation is additive over the items. We show that the revenue may increase arbitrarily with menu size and that a bounded menu size can not ensure any positive fraction of the optimal revenue. The menu size turns out to "nail down" the revenue properties of deterministic auctions: their menu size may be at most exponential in the number of items and indeed their revenue may be larger than that achievable by the simplest types of auctions by a factor that is exponential in the number of items but no larger. Our model is related to a previously studied "unit-demand" model and our results also answer an open problem in that model.

Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible multi-item setting: two items and a single buyer who has independently distributed values for the items, and an additive valuation. In general, the revenue achievable from selling two independent items may be strictly higher than the sum of the revenues obtainable by selling each of them separately. In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two items even in this simple setting is not understood.

Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes of set functions can be sketched. More formally let f be a function mapping subsets of some ground set [n] to the non-negative real numbers. We say that f′ is an α-sketch of f if for every set S, the value f′(S) lies between f(S)/α and f(S), and f′ can be specified by poly(n) bits. We show that for every subadditive function f there exists an α-sketch where α = n1/2 · O(polylog(n)). Furthermore, we provide an algorithm that finds these sketches with a polynomial number of demand queries. This is essentially the best we can hope for since: 1. We show that there exist subadditive functions (in fact, XOS functions) that do not admit an o(n1/2) sketch. (Balcan and Harvey [3] previously showed that there exist functions belonging to the class of substitutes valuations that do not admit an O(n1/3) sketch.) 2. We prove that every deterministic algorithm that accesses the function via value queries only cannot guarantee a sketching ratio better than n1−ε. We also show that coverage functions, an interesting subclass of submodular functions, admit arbitrarily good sketches. Finally, we show an interesting connection between sketching and learning. We show that for every class of valuations, if the class admits an α-sketch, then it can be α-approximately learned in the PMAC model of Balcan and Harvey. The bounds we prove are only information-theoretic and do not imply the existence of computationally efficient learning algorithms in general.

We present a new framework for the design of computationally-efficient and incentive-compatible mechanisms for combinatorial auctions. The mechanisms obtained via this framework are randomized, and obtain incentive compatibility in the universal sense (in contrast to the substantially weaker notion of incentive compatibility in expectation). We demonstrate the usefulness of our techniques by exhibiting two mechanisms for combinatorial auctions with general bidder preferences. The first mechanism obtains an optimal O(m)-approximation to the optimal social welfare for arbitrary bidder valuations. The second mechanism obtains an O(log2m)-approximation for a class of bidder valuations that contains the important class of submodular bidders. These approximation ratios greatly improve over the best (known) deterministic incentive-compatible mechanisms for these classes.

Under many distributed protocols, the prescribed behavior for participants is to behave greedily, i.e., to repeatedly "best respond" to the others' actions. We present recent work (Proc. ICS'11) where we tackle the following general question: "When is it best for a long-sighted participant to adhere to a distributed greedy protocol?". We take a game-theoretic approach and exhibit a class of games where greedy behavior (i.e., repeated best-response) is incentive compatible for all players. We identify several environments of interest that fall within this class, thus establishing the incentive compatibility of the natural distributed greedy protocol for each. These environments include models of the Border Gateway Protocol (BGP) [4], which handles routing on the Internet, and of the Transmission Control Protocol (TCP) [3], and also stable-roommates assignments [2] and cost-sharing [5], which have been extensively studied in economic theory.

We exhibit incentive compatible multi-unit auctions that are not affine maximizers (i.e., are not of the VCG family) and yet approximate the social welfare to within a factor of 1+ɛ. For the case of two-item two-bidder auctions we show that these auctions, termed Triage auctions, are the only scalable ones that give an approximation factor better than 2. “Scalable ” means that the allocation does not depend on the units in which the valuations are measured. We deduce from this that any scalable computationally-efficient incentive-compatible auction for m items and n ≥ 2 bidders cannot approximate the social welfare to within a factor better than 2. This is in contrast to arbitrarily good approximations that can be reached under computational constraints alone, and in contrast to the existence of incentivecompatible mechanisms that achieve the optimal allocation.

No abstract available.

We present a new framework for auction design and analysis that we term "best-response auctions". We use this framework to show that the simple and myopic best-response dynamics converge to the VCG outcome and are incentive compatible in several well-studied auction environments (Generalized Second Price auctions, and auctions with unit-demand bidders). Thus, we establish that in these environments, given that all other bidders are repeatedly best-responding, the best course of action for a bidder is to also repeatedly best-respond. Our results generalize classical results in economics regarding convergence to equilibrium and incentive compatibility of ascending-price English auctions. In addition, our findings provide new game-theoretic justifications for some well-studied auction rules. Best-response auctions provide a way to bridge the gap between the full-information equilibrium concept and the usual private-information auction theory.

The Gibbard–Satterthwaite theorem states that every nondictatorial election rule among at least three alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard–Satterthwaite theorem: a random manipulation by a single random voter will succeed with a nonnegligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range.

In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic ''combinatorial agency'' model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principal's gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.

We present an incentive-compatible polynomial-time approximation scheme for multi-unit auctions with general k-minded player valuations. The mechanism fully optimizes over an appropriately chosen sub-range of possible allocations and then uses VCG payments over this sub-range. We show that obtaining a fully polynomial-time incentive-compatible approximation scheme, at least using VCG payments, is NP-hard. For the case of valuations given by black boxes, we give a polynomial-time incentive-compatible 2-approximation mechanism and show that no better is possible, at least using VCG payments.

We describe a synthesis course that provides a hands-on treatment of many hardware and software topics learned in computer science (CS) programs. Using a modular series of twelve projects, we walk the students through the gradual construction of a simple hardware platform and a modern software hierarchy, yielding a basic yet powerful computer system. In the process of building the computer, the students gain a first-hand understanding of how hardware and software systems are designed and how they work together, as one enterprise. The course web site contains all the materials necessary to run this course in open source, and students and instructors are welcome to use and extend them freely. The course projects are modular and self-contained, and any subset of them can be implemented in any order and in any programming language. Therefore, they comprise a flexible library of exercises that can be used in many applied CS courses. This paper gives a description of the approach and the course, juxtaposed against general educational principles underlying meaningful learning.

We study the computational power of iterative combinatorial auctions. Most existing iterative combinatorial auctions are based on repeatedly suggesting prices for bundles of items and querying the bidders for their “demand” under these prices. We prove several results regarding such auctions that use a polynomial number of demand queries: (1) that such auctions can simulate several other natural types of queries; (2) that they can approximate the optimal allocation as well as generally possible using polynomial communication or computation, while weaker types of queries cannot do so; (3) that such auctions that use only item prices may solve allocation problems in communication cost that is exponentially lower than the cost incurred by auctions that use prices for bundles. For the latter result, we initiate the study of how prices of bundles can be represented when they are not linear and show that the “default” representation has severe limitations. Our results hold for any series of demand queries with polynomial length, without any additional restrictions on the queries (e.g., to ascending prices).

We present FairplayMP (for "Fairplay Multi-Party"), a system for secure multi-party computation. Secure computation is one of the great achievements of modern cryptography, enabling a set of untrusting parties to compute any function of their private inputs while revealing nothing but the result of the function. In a sense, FairplayMP lets the parties run a joint computation that emulates a trusted party which receives the inputs from the parties, computes the function, and privately informs the parties of their outputs. FairplayMP operates by receiving a high-level language description of a function and a configuration file describing the participating parties. The system compiles the function into a description as a Boolean circuit, and perform a distributed evaluation of the circuit while revealing nothing else. FairplayMP supplements the Fairplay system [16], which supported secure computation between two parties. The underlying protocol of FairplayMP is the Beaver-Micali-Rogaway (BMR) protocol which runs in a constant number of communication rounds (eight rounds in our implementation). We modified the BMR protocol in a novel way and considerably improved its performance by using the Ben-Or-Goldwasser-Wigderson (BGW) protocol for the purpose of constructing gate tables. We chose to use this protocol since we believe that the number of communication rounds is a major factor on the overall performance of the protocol. We conducted different experiments which measure the effect of different parameters on the performance of the system and demonstrate its scalability. (We can now tell, for example, that running a second-price auction between four bidders, using five computation players, takes about 8 seconds.)

We study multi-unit auctions where the bidders have a budget constraint, a situation very common in practice that has received very little attention in the auction theory literature. Our main result is an impossibility: there are no incentive-compatible auctions that always produce a Pareto-optimal allocation. We also obtain some surprising positive results for certain special cases.

The Gibbard-Satterthwaite theorem states that every non-trivial voting method among at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with non-negligible probability for every neutral voting method among 3 alternatives that is far from being a dictatorship.

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a Õ (√n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is optimal in a very strong sense. It is known that no compact routing using o ( n ) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√ n ,)space per node.

We present an incentive-compatible polynomial-time approximation scheme for multi-unit auctions with general k-minded playervaluations. The mechanism fully optimizes over an appropriately chosen sub-range of possible allocations and then uses VCG payments over this sub-range. We show that obtaining a fully polynomial-time incentive-compatible approximation scheme, at least using VCG payments, is NP-hard. For the case of valuations given by black boxes, we give a polynomial-time incentive-compatible 2-approximation mechanism and show that no better is possible, at least using VCG payments.

We consider computationally-efficient incentive-compatiblemechanisms that use the VCG payment scheme, and study how well theycan approximate the social welfare in auction settings. We present anovel technique for setting lower bounds on the approximation ratioof this type of mechanisms. Specifically, for combinatorial auctionsamong submodular (and thus also subadditive) bidders we prove an Ω(m1/6) lower bound, which is close to the knownupper bound of O(m1/2), and qualitatively higher than theconstant factor approximation possible from a purely computationalpoint of view.

We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove non-surprising properties of these kinds of auctions, e.g., that in optimal mechanisms bidders simply report the interval in which their valuation lies in, as well as some surprising properties, e.g., that asymmetric auctions are better than symmetric ones and that multi-round auctions reduce the communication complexity only by a linear factor.

A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers. The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithm's output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.

Much recent research concerns systems, such as the Internet, whose components are owned and operated by different parties, each with his own "selfish" goal. The field of Algorithmic Mechanism Design handles the issue of private information held by the different parties in such computational settings. This paper deals with a complementary problem in such settings: handling the "hidden actions" that are performed by the different parties.Our model is a combinatorial variant of the classical principalagent problem from economic theory. In our setting a principal must motivate a team of strategic agents to exert costly effort on his behalf, but their actions are hidden from him. Our focus is on cases where complex combinations of the efforts of the agents influence the outcome. The principal motivates the agents by offering to them a set of contracts, which together put the agents in an equilibrium point of the induced game. We present formal models for this setting, suggest and embark on an analysis of some basic issues, but leave many questions open.

We embark on a systematic analysis of the power and limitations of iterative combinatorial auctions. Most existing iterative combinatorial auctions are based on repeatedly suggesting prices for bundles of items, and querying the bidders for their "demand" under these prices. We prove a large number of results showing the boundaries of what can be achieved by auctions of this kind. We first focus on auctions that use a polynomial number of demand queries, and then we analyze the power of different kinds of ascending-price auctions.

We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number of items $m$ and in the number of bidders n, even though the "input size" is exponential in m. The first algorithm provides an O(log m) approximation. The second algorithm provides an O(√ m) approximation in the weaker model of value oracles. This algorithm is also incentive compatible. The third algorithm provides an improved 2-approximation for the more restricted case of "XOS bidders", a class which strictly contains submodular bidders. We also prove lower bounds on the possible approximations achievable for these classes of bidders. These bounds are not tight and we leave the gaps as open problems.

We consider the problem of a spatially distributed market with strategic agents. In this problem a single good is traded in a set of independent markets, where shipment between markets is possible but incurs a cost. The problem has previously been studied in the non-strategic case, inwhich it can be analyzed and solved as a min-cost-flow problem. We considerthe case where buyers and sellers are strategic. Our first result gives adouble characterization of the VCG prices, first as distances in acertain residue graph and second as the minimal (for buyers) and maximal (forsellers) equilibrium prices. This provides a computationally efficient, individually rational and incentive compatible welfare maximizing mechanism. This mechanism is, necessarily, not budget balanced and we provide alsoa budget-balanced mechanism (which is also computationally efficient,incentive compatible, and individually rational) that achieves highwelfare. Some of our results extend to the cases where buyers andsellers have arbitrary convex demand and supply functions and to the case where transportation is controlled by strategic agents as well.

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a O(√n) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the shortest paths. This is optimal in a very strong sense. It is known that no compact routing using o(n) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√n) space per node.

With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable goods. Such markets, however, will normally need to function in some relationship with markets for other related goods, usually those downstream or upstream in the supply chain. Thus, for example, an electronic market for rubber tires for trucks will likely need to be strongly influenced by the rubber market as well as by the truck market. In this paper we design protocols for exchange of information between a sequence of markets along a single supply chain. These protocols allow each of these markets to function separately, while the information exchanged ensures efficient global behavior across the supply chain. Each market that forms a link in the supply chain operates as a double auction, where the bids on one side of the double auction come from bidders in the corresponding segment of the industry, and the bids on the other side are synthetically generated by the protocol to express the combined information from all other links in the chain. The double auctions in each of the markets can be of several types, and we study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue.

This paper analyzes incentive compatible (truthful) mechanisms over restricted domains of preferences, the leading example being combinatorial auctions. Our work generalizes the characterization of Roberts (1979) who showed that truthful mechanisms over unrestricted domains with at least 3 possible outcomes must be "affine maximizers". We show that truthful mechanisms for combinatorial auctions (and related restricted domains) must be "almost affine maximizers" if they also satisfy an additional requirement of "independence of irrelevant alternatives". This requirement is without loss of generality for unrestricted domains as well as for auctions between two players where all goods must be allocated. This implies unconditional results for these cases, including a new proof of Roberts' theorem. The computational implications of this characterization are severe, as reasonable "almost affine maximizers" are shown to be as computationally hard as exact optimization. This implies the near-helplessness of such truthful polynomial-time auctions in all cases where exact optimization is computationally intractable.

This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to single minded valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions.

We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare-maximizing and revenue-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove unsurprising properties of these kinds of auctions, e.g. that discrete prices are informationally efficient, as well as some surprising properties, e.g. that asymmetric auctions are better than symmetric ones.

With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable goods. Such markets, however, will normally need to function in some relationship with markets for other related goods, usually those downstream or upstream in the supply chain. Thus, for example, an electronic market for rubber tires for trucks, will likely need to be strongly influenced by the rubber market as well as by the truck market.In this paper we design protocols for exchange of information between a sequence of markets along a single supply chain. These protocols allow each of these markets to function separately, while the information exchanged guarantees efficient global behavior across the supply chain. Each market form a link in the supply chain operates as a double auction, where the bids on one side of the double auction come from bidders in the corresponding segment of the industry, and the bids on the other side are synthetically generated by the protocol to express the combined information from all other links in the chain. The double auctions in each of the markets can be of several types, and we study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue.

In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. While we show that the allocation problem among valuations with decreasing marginal utilities is NP-hard, we present an efficient greedy 2-approximation algorithm for this case. No such approximation algorithm exists in a setting allowing for complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.

We propose a heuristic for allocation in combinatorial auctions. We first run an approximation algorithm on the linear programming relaxation of the combinatorial auction. We then run a sequence of greedy algorithms, starting with the order on the bids determined by the approximate linear program and continuing in a hill-climbing fashion using local improvements in the order of bids. We have implemented the algorithm and have tested it on the complete corpus of instances provided by Vohra and de Vries as well as on instances drawn from the distributions of Leyton-Brown, Pearson, and Shoham. Our algorithm typically runs two to three orders of magnitude faster than the reported running times of Vohra and de Vries, while achieving an average approximation error of less than 1%. This algorithm can provide, in less than a minute of CPU time, excellent solutions for problems with over 1000 items and 10,000 bids. We thus believe that combinatorial auctions for most purposes face no practical computational hurdles.

Let $D \subseteq \Sigma^n$ be a dictionary. We look for efficient data structures and algorithms to solve the following approximate query problem: Given a query $u \in \Sigma^n$ list all words $v \in D$ that are close to u in Hamming distance. The problem reduces to the following combinatorial problem: Hash the vertices of the n-dimensional hypercube into buckets so that (1) the c-neighborhood of each vertex is mapped into at most k buckets and (2) no bucket is too large. Lower and upper bounds are given for the tradeoff between k and the size of the largest bucket. These results are used to derive bounds for the approximate query problem.

This paper studies auctions in a setting where the dierent bidders arrive at dierent times and the auction mechanism is required to make decisions about each bid as it is received.Such settings occur in computerized auctions of computational resources as well as in other settings.We call such auctions, on-line auctions.We r s t c haracterize exactly on-line auctions that are incentive compatible, i.e.where rational bidders are always motivated to bid their true valuation.We then embark on a competitive worst-case analysis of incentive compatible on-line auctions.We obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items.This auction has an optimal competitive ratio, both in terms of seller's revenue and in terms of the total social eÆciency obtained.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific

When an auction of multiple items is performed, it is often desirable to allow bids on combinations of items, as opposed to only on single items. Such an auction is often called "combinatorial", and the exponential number of possible combinations results in computational intractability ofmanyaspects regarding such an auction. This paper considers two of these aspects: the bidding language and the allocation algorithm. First we consider which kinds of bids on combinations are allowed and how, i.e. in what language, they are speci ed. The basic tradeo is the expressibility of the language versus its simplicity. Weconsider and formalize several bidding languages and compare their strengths. We proveexponential separations between the expressive power of di erent languages, and show that one language, \\OR-bids with phantom items", can polynomially simulate the others. We then consider the problem of determining the best allocation { a problem known to be computationally intractable. We suggest an approach based on Linear Programming (LP) and motivate it. We provethat the LP approach nds an optimal allocation if and only if prices can be attached to single items in the auction. We pinpoint several classes of auctions where this is the case, and suggest greedy and branch-and-bound heuristics based on LP for other cases.

No abstract available.

We consider algorithmic problems in a distributed setting where the participants annot be assumed to follow the algorithm but rather their own self-interest.As such pxticipants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents' interests are best served by behaving correctly.Following notions from the field of mechanism design, we suggest a framework for studying such algorithms.In this model the algorithmic solution is adorned with payments to the participants and is termed a mechanism.The payments should be carefully chosen a6 to motivate all participants to act as the algorithm designer wishes.We apply the standard tools of mechanism design to algorithmic problems and in particular to the shortest path problem.Our main technical contribution concerns the study of a representative problem, task scheduling, for which the standard tools do not suffice.We present several theorems regarding this problem including an approximation me&anism, lower bounds and a randomized mechanism.We also suggest and motivate extensions to the basic model and prove improved upper bounds in the extended model.Many open problems are suggested as well.

We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm runs in O(log n) time using $(m+n^{1+\epsilon})/\log n$ EREW processors (for any fixed $\epsilon > 0$). A variant uses (m+n)/log n processors and runs in O(log n log log n) time. A deterministic version of the algorithm runs in $O(\log^{1.5}n)$ time using m+n EREW processors.

We investigate two problems concerning the complexity of evaluating a function f on k distinct inputs by k parallel decision-tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best depth-d decision tree is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth-d algorithms are all correct is at most p k , which is the trivial lower bound. We show that if we replace the restriction to depth d by "expected depth d," then this result need not hold. In the help-bits problem, before the decision-tree computations begin, up to k-1 arbitrary binary questions (help-bit queries) can be asked about the k-tuple of inputs. In the second stage, for each possible (k-1)-tuple of answers to the help-bit queries, there is a k-tuple of decision trees where the ith tree is supposed to correctly compute the value of the function on the ith input, for any input that is consistent with the help bits. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg s (f), which is the minimum degree of a multivariate polynomial whose sign is equal to f.

The POPCORN project provides an infrastructure for globally distributed computation over the whole Internet. It provides any programmer connected to the Internet with a single huge virtual parallel computer composed of all processors on the Internet which care to participate at any given moment. The system provides a market-based mechanism of trade in CPU time to motivate processors to provide their CPU cycles for other peoples' computations. Selling CPU time is as easy as visiting a certain Web site with a Java-enabled browser. Buying CPU time is done by writing a parallel program, using our programming paradigm (and libraries). This paradigm was designed to fit the situation of global computation. A third entity in our system is a market for CPU time, which is where buyers and sellers meet and trade. The system has been implemented and may be visited and used on our Web site: http://www.cs.huji.ac.il/-popcorn.

Current formal models for quantum computation deal only with unitary gates operating on "pure quantum states". In these models it is difficult or impossible to deal formally with several central issues: measurements in the middle of the computation; decoherence and noise, using probabilistic subroutines, and more. It turns out, that the restriction to unitary gates and pure states is unnecessary. In this paper we generalize the formal model of quantum circuits to a model in which the state can be a general quantum state, namely a mixed state, or a "density matrix", and the gates can be general quantum operations, not necessarily unitary. The new model is shown to be equivalent in computational power to the standard one, and the problems mentioned above essentially disappear. The main result in this paper is a solution for the subroutine problem. The general function that a quantum circuit outputs is a probabilistic function. However, the question of using probabilistic functions as subroutines was not previously dealt with, the reason being that in the language of pure states, this simply can not be done. We define a natural notion of using general subroutines, and show that using general subroutines does not strengthen the model. As an example of the advantages of analyzing quantum complexity using density matrices, we prove a simple lower bound on depth of circuits that compute probabilistic functions. Finally, we deal with the question of inaccurate quantum computation with mixed states. Using the so called "trace metric" on density matrices, we show how to keep track of errors in the new model. Institutes of Physics and Computer science, The Hebrew University, Jerusalem, Israel y L.D.Landau Institute for Theoretical Physics,Moscow, Russia z Institute of Compu...

Article Free Access Share on Pointer jumping requires concurrent read Authors: Noam Nisan Department of Computer Science, The Hebrew University of Jerusalem, Jerusalem 91904, Israel Department of Computer Science, The Hebrew University of Jerusalem, Jerusalem 91904, IsraelView Profile , Ziv Bar-Yossef Department of Computer Science, The Hebrew University of Jerusalem, Jerusalem 91904, Israel Department of Computer Science, The Hebrew University of Jerusalem, Jerusalem 91904, IsraelView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 549–558https://doi.org/10.1145/258533.258648Online:04 May 1997Publication History 3citation256DownloadsMetricsTotal Citations3Total Downloads256Last 12 Months6Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Extractors are Boolean functions that allow, in some precise sense, extraction of randomness from somewhat random distributions. Extractors, and the closely related "Dispersers", exhibit some of the most "random-like" properties of explicitly constructed combinatorial structures. In turn, extractors and dispersers have many applications in "removing randomness" in various settings and in making randomized constructions explicit. This manuscript surveys extractors and dispersers: what they are, how they can be designed, and some of their applications. The work described is due to of a long list of research papers by various authors-most notably by David Zuckerman.

We describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials and iterated matrix products.

We present several results regarding randomized oneround communication complexity. These include a connection to the VC-dimension, a study of the problem of computing the inner product of two real valued vectors, and a relation between "simultaneous" protocols and one-round protocols. 1 Introduction In this paper we are concerned with randomized twoparty communication complexity as defined by Yao [21]: Alice holds an input x, Bob holds an input y, and they wish to compute a given function f(x; y), to which end they communicate with each other via a randomized protocol. We allow them bounded, twosided error. We study very simple types of protocols which include only one round of communication. These protocols were introduced by Yao in his original communication complexity paper [21] and were later studied by several authors (cf. [17, 1]). In a one-round protocol, Alice is allowed to send a single message (depending upon her input x and upon her random coin flips) to Bob who must then...

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 present a logspace, many-one reduction from the undirected st-connectivity problem to its complement. This shows that SL = co - SL.

This paper provides some new lower and upper bounds on computing bilinear forms by arithmetic circuits. The complexity measures considered are circuit size, formula size and time-space trade-offs.

In this work we study the direct-sum problem with respect to communication complexity: Consider a relation f defined over $\{0,1\}^{n} \times \{0,1\}^{n}$. Can the communication complexity of simultaneously computing f on $\ell $ instances $(x_{1}, y_{1}), \dotsc , (x_{\ell}, y_{\ell})$ be smaller than the communication complexity of separately computing f on the $\ell $ instances? Let the amortized communication complexity of f be the communication complexity of simultaneously computing f on $\ell $ instances divided by $\ell $. We study the properties of the amortized communication complexity. We show that the amortized communication complexity of a relation can be smaller than its communication complexity. More precisely, we present a partial function whose (deterministic) communication complexity is $\Theta (\log n)$ and amortized (deterministic) communication complexity is $O(1)$. Similarly, for randomized protocols we present a function whose randomized communication complexity is $\Theta (\log n)$ and amortized randomized communication complexity is $O(1)$. We also give a general lower bound on the amortized communication complexity of any functionf in terms of its communication complexity $C(f)$: for every function f the amortized communication complexity of f is $\Omega (\sqrt{C(f)} - \log n)$.

It is possible to view communication complexity as the minimum solution of an integer programming problem. This integer programming problem is relaxed to a linear programming problem and from it information regarding the original communication complexity question is deduced. A particularly appealing avenue this opens is the possibility of proving lower bounds on the communication complexity (which is a minimization problem) by exhibiting upper bounds on the maximization problem defined by the dual of the linear program. This approach works very neatly in the case of nondeterministic communication complexity. In this case a special case of Lovász’s fractional cover measure is obtained. Through it the amortized nondeterministic communication complexity is completely characterized. The power of the approach is also illustrated by proving lower and upper bounds on the nondeterministic communication complexity of various functions. In the case of deterministic complexity the situation is more complicated. Two attempts are discussed and some results using each of them are obtaied. The main result regarding the first attempt is negative: one cannot use this method for proving superpolynomial lower bounds for formula size. The main result regarding the second attempt is a “direct-sum” theorem for two-round communication complexity.

We investigate two problems concerning the complexity of evaluating a function f at k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best decision tree algorithm of depth d is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth d algorithms are all correct is at most p/sup k/, which is the trivial lower bound. We show that if we replace the depth d restriction by "expected depth d", then this result fails. In the help-bit problem, we are permitted to ask k-1 arbitrary binary questions about the k-tuple of inputs. For each possible k-1-tuple of answers to these queries we will have a k-tuple of decision trees which are supposed to correctly compute all functions on k-tuples that are consistent with the particular answers. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg/sup s/(f) which is the minimum degree of a multivariate polynomial whose sign is equal to f. Finally, we give a brief discussion of these problems in the context of other complexity models.>

This paper concerns the open problem of Lovasz and Saks (1988) regarding the relationship between the communication complexity of a Boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems.>

We define pseudorandom generators for Yao's twoparty communication complexity model and exhibit a simple construction, based on expanders, for it.We then use a recursive composition of such generators to obtain pseudorandom generators that fool distributed network algorithms.While the construction and the proofs are simple, we demonstrate the generality of such generators by giving several applications.1 a pseudorandom generator, which is said to fool the

We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input.Our model haa p processors that communicate through a shared memory of size m.The input haa size n, and can be read directly by all the processuggest that such new methodologies are likely to be found.

We introduce a fast parallel approximation algorithm for the positive linear programming optimization problem, i.e. the special case of the linear programming optimization problem where the input constraint matrix and constraint vector consist entirely of positive entries.The algorithm is elementary, and has a simple parallel implementation that runs in polylog time using a linear number of processors.

We show that any randomized space(S) algorithm which uses only poly(S) random bits can be simulated deterministically in space(S), for S(n) ~log n.Of independent interest is our main technical tool: a procedure which extracts randomness from a defective random source using a small additional number of truly random bits.

In this paper, Boolean functions in ,4C0 are studied using harmonic analysis on the cube.The main result is that an ACO Boolean function has almost all of its "power spectrum" on the low-order coefficients.An important ingredient of the proof is Hastad's switching lemma [8].This result implies several new properties of functions in -4C[': Functions in AC() have low "average sensitivity;" they may be approximated well by a real polynomial of low degree and they cannot be pseudorandom function generators.Perhaps the most interesting application is an O(n POIYIOg(n ')-time algorithm for learning functions in ACO.The algorithm observes the behavior of an AC'" function on O(nPO'Y'Og(n)) randomly chosen inputs, and derives a good approximation for the Fourier transform of the function.This approximation allows the algorithm to predict, with high probability, the value of the function on other randomly chosen inputs.

The k-round two-party communication complexity was studied in the deterministic model by [P. H. Papadimitriou and M. Sipser, Proc. of the 14th STOC, 1982, pp. 330–337] and [P. Duris, Z. Galil, and G. Schnitger, Proc. of the 16th STOC, 1984, pp. 81–91] and in the probabilistic model by [A. C. Yao, Proc. of the 24th FOCS, 1983, pp. 420–428] and [B. Halstenberg and R. Reischuk, Proc. of the 20th STOC, 1988, pp. 162–172]. This paper presents new lower bounds that give (1) randomization is more powerful than determinism in k-round protocols, and (2) an explicit function which exhibits an exponential gap between its k and $(k - 1)$-round randomized complexity. This paper also studies the three-party communication model, and exhibits an exponential gap in 3-round protocols that differ in the starting player. Finally, this paper shows new connections of these questions to circuit complexity, that motivate further work in this direction.

The authors present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log/sup 1.5/n) space. Thus, the recursive doubling technique of Savich (1970) which requires Theta (log/sup 2/n) space is not optimal for this problem.>

We present fast and ecient parallel algorithms for nding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm runs in O(log n) time using (m+n 1+) = logn EREW processors (for any xed > 0). A variant uses (m+n) = logn processors and runs in O(log n log logn) time. A deterministic version of the algorithm runs in O(log 1:5 n) time using m+ n EREW processors. 1

We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on approximations of the independent distribution for the special case of uniform boolean-valued random variables. Our results yield efficient constructions of small sets with low discrepancy in high dimensional space and have applications to derandomizing randomized algorithms.

We show that any randomized Logspace algorithm (running in polynomial time, with bounded tw~sided error) can be simulated deterministically in polynomial time and 0(log2 n) space.This puts RL in SC, "Steve's Class".In particular, we get a polynomial time 0(log2 n) space algorithm for the connectivity problem on undirected graphs.

Every boolean function may be represented as a real polynomial. In this paper we characterize the degree of this polynomial in terms of certain combinatorial properties of the boolean function.

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].

Article Lower bounds for non-commutative computation Share on Author: Noam Nisan Hebrew Univ., Jerusalem, Israel Hebrew Univ., Jerusalem, IsraelView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 410–418https://doi.org/10.1145/103418.103462Published:03 January 1991 118citation611DownloadsMetricsTotal Citations118Total Downloads611Last 12 Months31Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Rounds in communication complexity revisited Share on Authors: Noam Nisan Hebrew Univ., Jerusalem, Israel Hebrew Univ., Jerusalem, IsraelView Profile , Avi Widgerson Hebrew Univ., Jerusalem, Israel Hebrew Univ., Jerusalem, IsraelView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 419–429https://doi.org/10.1145/103418.103463Online:03 January 1991Publication History 29citation344DownloadsMetricsTotal Citations29Total Downloads344Last 12 Months17Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper gives a full characterization of the time needed to compute a boolean function on a CREW PRAM with an unlimited number of processors.The characterization is given in terms of a new complexity measure of boolean functions: the “block sensitivity,” a generalization of the well-known “critical sensitivity” measure. The block sensitivity is also shown to relate to the boolean decision tree complexity, and the implication is that the decision tree complexity also fully characterizes the CREW PRAM complexity. This solves an open problem of Wegener. The results imply that changes in the instruction set of the processors or in the capacity of the shared memory cells do not change by more than a constant factor the time required by a CREW PRAM to compute any boolean function. Moreover, it is shown that a seemingly weaker version of a CREW PRAM, the CROW PRAM, can compute functions as quickly as a general CREW PRAM. This solves an open problem of Dymond and Ruzzo. Finally, the results have implications regarding the power of randomization in the boolean decision tree model. It is shown that in this model, randomization may achieve only a polynomial speedup over deterministic computation. This was known for Las Vegas randomized computation; it is also proven for one-sided error computation (a quadratic bound) and two-sided error (a cubic bound).

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction.>

The Inclusion-Exclusion formula expresses the size of a union of a family of sets in terms of the sizes of intersections of all subfamilies.This paper considers approximating the size of the union when intersection sizes are known for only some of the subfamilies, or when these quantities are given to within some error, or both.In particular, we consider the case when all k-wise intersections axe given for every k < K.It turns out that the answer changes in a significant way around g = V/'ff : if K < O(v/-ff) then any approximation may err by a factor of O(n/K2), while if K > ft(v/'ff ) it is shown how to approximate the size of the union_to within a multiplicative factor of 1 :t: e -a(g/'/'a).When the sizes of all intersections are only given approximately, good bounds are derived on how well the size of the union may be approximated.Several applications for boolean function are mentioned in conclusion.

Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS = f~(nm).The bound holds in the general boolean branching program model, and thus in essentially any model of computation.As a corollary, computing a + b • c in any field F requires a quadratic time-space tradeoff, and the bound holds for any representation of the elements of the field.Other lower bounds on the complexity of any implementation of universal hashing are given as well: Quadratic AT 2 bound for VLSI implementation; f~(log n) parallel time bound on a CREW PRAM; and exponential size for constant depth circuits.

Article Free Access Share on Pseudorandom generators for space-bounded computations Author: N. Nisan Laboratory for Computer science, MIT, 545 Tech. sq., Cambridge, MA Laboratory for Computer science, MIT, 545 Tech. sq., Cambridge, MAView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 204–212https://doi.org/10.1145/100216.100242Published:01 April 1990Publication History 94citation944DownloadsMetricsTotal Citations94Total Downloads944Last 12 Months41Last 6 weeks12 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Boolean functions in AC/sup O/ are studied using the harmonic analysis of the cube. The main result is that an AC/sup O/ Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in AC/sup O/: functions in AC/sup O/ have low average sensitivity; they can be approximated well be a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wide independent probability distribution is small. An O(n/sup polylog(/ /sup sup)/ /sup (n)/)-time algorithm for learning functions in AC/sup O/ is obtained. The algorithm observed the behavior of an AC/sup O/ function on O(n/sup polylog/ /sup (n)/) randomly chosen inputs and derives a good approximation for the Fourier transform of the function. This allows it to predict with high probability the value of the function on other randomly chosen inputs.>

Let ƒ(x1, ···· xk) be a Boolean function that k parties wish to collaboratively evaluate. The i'th party knows each input argument except xi; and each party has unlimited computational power. They share a blackboard, viewed by all parties, where they can exchange messages. The objective is to minimize the number of bits written on the board.

This paper gives a full characterization of the time needed to compute a Boolean function on a CREW PRAM with an unlimited number of processors.

A technique that yields fast parallel algorithms for several zero-one supply-demand problems is presented. $NC$ algorithms are given for the following related problems: (1) Given a sequence of supplies $a_1 , \cdots ,a_n $ and demands $b_1 , \cdots ,b_m $, construct a zero-one flow pattern satisfying these constraints, where every supply vertex can send at most one unit of flow to each demand vertex. (2) Given a sequence of positive and negative integers summing to zero, representing supplies and demands, respectively, construct a zero-one flow pattern so that the net flow out of (into) each vertex is its supply (demand), where every vertex can send at most one unit of flow to every other vertex. (3) Construct a digraph without self-loops with specified in- and out-degrees. The results are extended to the case where the input represents upper bounds on supplies and lower bounds on demands.

A simple construction for a pseudorandom bit generator is presented. It stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C (e.g. P, NC, PSPACE, etc.), using an arbitrary function that is hard for C. This generator reveals an equivalence between the problems of proving lower bounds and the problem of generating good pseudorandom sequences. Combining this construction with other arguments, a number of consequences are obtained.>