We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or time-out) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish the following competitive ratio results against the offline adaptive benchmark: 1) A tight 1/2 ratio when the arrival ordering π is chosen adversarially. 2) A 1-1/e ratio when the arrival ordering π is chosen u.a.r. (uniformly at random). If π is generated adversarially, we generalize the prophet inequality matching problem. If π is u.a.r., we generalize the prophet secretary matching problem. Both results improve upon the previous best competitive ratio of 0.46 in the more restricted known i.i.d. (independent and identically distributed) arrival model against the standard offline adaptive benchmark due to Brubach et al. We are the first to study the prophet secretary matching problem in the context of probing, and our 1-1/e ratio matches the best known result without probing due to Ehsani et al. This result also applies to the unconstrained bipartite matching probe-commit problem, where we match the best known result due to Gamlath et al.

A fundamental question in social choice and multi-agent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying cardinal preferences. It aims to optimize distortion, the worst-case approximation ratio of the (utilitarian) social welfare. When agents rank the set of alternatives, prior work identifies near-optimal voting rules for selecting one or more alternatives. However, ranking all the alternatives is prohibitive when there are many alternatives. In this work, we consider the setting where each agent ranks only her t favorite alternatives and identify almost tight bounds on the best possible distortion when selecting a single alternative or a committee of alternatives of a given size k. Our results also extend to approximating higher moments of social welfare. Along the way, we close a gap left open in prior work by identifying asymptotically tight distortion bounds for committee selection given full rankings.

We consider the online bipartite matching problem within the context of stochastic probing with commitment. This is the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching. We consider the competitiveness of online algorithms in the adversarial order model (AOM) and the secretary/random order model (ROM). More specifically, we consider an unknown bipartite stochastic graph G = (U,V,E) where U is the known set of offline vertices, V is the set of online vertices, G has edge probabilities (p_{e})_{e ∈ E}, and G has edge weights (w_{e})_{e ∈ E} or vertex weights (w_u)_{u ∈ U}. Additionally, G has a downward-closed set of probing constraints (𝒞_{v})_{v ∈ V}, where 𝒞_v indicates which sequences of edges adjacent to an online vertex v can be probed. This model generalizes the various settings of the classical bipartite matching problem (i.e. with and without probing). Our contributions include the introduction and analysis of probing within the random order model, and our generalization of probing constraints which includes budget (i.e. knapsack) constraints. Our algorithms run in polynomial time assuming access to a membership oracle for each 𝒞_v. In the vertex weighted setting, for adversarial order arrivals, we generalize the known 1/2 competitive ratio to our setting of 𝒞_v constraints. For random order arrivals, we show that the same algorithm attains an asymptotic competitive ratio of 1-1/e, provided the edge probabilities vanish to 0 sufficiently fast. We also obtain a strict competitive ratio for non-vanishing edge probabilities when the probing constraints are sufficiently simple. For example, if each 𝒞_v corresponds to a patience constraint 𝓁_v (i.e., 𝓁_v is the maximum number of probes of edges adjacent to v), and any one of following three conditions is satisfied (each studied in previous papers), then there is a conceptually simple greedy algorithm whose competitive ratio is 1-1/e. - When the offline vertices are unweighted. - When the online vertex probabilities are "vertex uniform"; i.e., p_{u,v} = p_v for all (u,v) ∈ E. - When the patience constraint 𝓁_v satisfies 𝓁_v ∈ {[1,|U|} for every online vertex; i.e., every online vertex either has unit or full patience. Finally, in the edge weighted case, we match the known optimal 1/e asymptotic competitive ratio for the classic (i.e. without probing) secretary matching problem.

Much of the social choice literature examines direct voting systems, in which voters submit their ranked preferences over candidates and a voting rule picks a winner. Real-world elections and decision-making processes are often more complex and involve multiple stages. For instance, one popular voting system filters candidates through primaries: first, voters affiliated with each political party vote over candidates of their own party and the voting rule picks a candidate from each party, which then compete in a general election.We present a model to analyze such multi-stage elections, and conduct the first quantitative comparison (to the best of our knowledge) of the direct and primary voting systems with two political parties in terms of the quality of the elected candidate. Our main result is that every voting rule is guaranteed to perform almost as well (i.e., within a constant factor) under the primary system as under the direct system. Surprisingly, the converse does not hold: we show settings in which there exist voting rules that perform significantly better under the primary system than under the direct system.

We introduce a new random input model for bipartite matching which we call the Random Type Poisson Arrival Model. Just like in the known i.i.d. model (introduced by Feldman et al. [Feldman et al., 2009]), online nodes have types in our model. In contrast to the adversarial types studied in the known i.i.d. model, following the random graphs studied in Mastin and Jaillet [A. Mastin, 2013], in our model each type graph is generated randomly by including each offline node in the neighborhood of an online node with probability c/n independently. In our model, nodes of the same type appear consecutively in the input and the number of times each type node appears is distributed according to the Poisson distribution with parameter 1. We analyze the performance of the simple greedy algorithm under this input model. The performance is controlled by the parameter c and we are able to exactly characterize the competitive ratio for the regimes c = o(1) and c = omega(1). We also provide a precise bound on the expected size of the matching in the remaining regime of constant c. We compare our results to the previous work of Mastin and Jaillet who analyzed the simple greedy algorithm in the G_{n,n,p} model where each online node type occurs exactly once. We essentially show that the approach of Mastin and Jaillet can be extended to work for the Random Type Poisson Arrival Model, although several nontrivial technical challenges need to be overcome. Intuitively, one can view the Random Type Poisson Arrival Model as the G_{n,n,p} model with less randomness; that is, instead of each online node having a new type, each online node has a chance of repeating the previous type.

Gerrymandering is the process by which parties manipulate boundaries of electoral districts in order to maximize the number of districts they can win. Demographic trends show an increasingly strong correlation between residence and party affiliation; some party’s supporters congregate in cities, while others stay in more rural areas. We investigate both theoretically and empirically the effect of this trend on a party's ability to gerrymander in a two-party model ("urban party" and "rural party"). Along the way, we propose a definition of the gerrymandering power of a party, and an algorithmic approach for near-optimal gerrymandering in large instances. Our results suggest that beyond a fairly small concentration of urban party's voters, the gerrymandering power of a party depends almost entirely on the level of concentration, and not on the party's share of the population. As partisan separation grows, the gerrymandering power of both parties converge so that each party can gerrymander to get only slightly more than what its voting share warrants, bringing about, ultimately, a more representative outcome. Moreover, there seems to be an asymmetry between the gerrymandering power of the parties, with the rural party being more capable of gerrymandering.

We consider auctions in which greedy algorithms, paired with first-price or critical-price payment rules, are used to resolve multiparameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show, for a variety of equilibrium concepts, including Bayes--Nash equilibria, low-regret bidding sequences, and asynchronous best-response dynamics, that the resulting price of anarchy bound is close to the approximation factor of the underlying greedy algorithm.

Result diversification is an important aspect in web-based search, document summarization, facility location, portfolio management, and other applications. Given a set of ranked results for a set of objects (e.g., web documents, facilities, etc.) with a distance between any pair, the goal is to select a subset S satisfying the following three criteria: (a) the subset S satisfies some constraint (e.g., bounded cardinality), (b) the subset contains results of high “quality,” and (c) the subset contains results that are “diverse” relative to the distance measure. The goal of result diversification is to produce a diversified subset while maintaining high quality as much as possible. We study a broad class of problems where the distances are a metric, where the constraint is given by independence in a matroid, where quality is determined by a monotone submodular function and diversity is defined as the sum of distances between objects in S . Our problem is a generalization of the max-sum diversification problem studied in Gollapudi and Sharma [2009], which in turn is a generalization of the max-sum p-dispersion problem studied extensively in location theory. It is NP-hard even with the triangle inequality. We propose two simple and natural algorithms: a greedy algorithm for a cardinality constraint and a local search algorithm for an arbitrary matroid constraint. We prove that both algorithms achieve constant approximation ratios.

We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a “take-it-or-leave-it” offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most k of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the case of a continuous valuation distribution when various standard assumptions hold simultaneously. In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to the ratio of the highest and lowest possible valuation. We prove that for two simple generalizations of these mechanisms, a better revenue performance can be achieved: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a $$\varOmega (1/\max \{1,d\})$$ fraction of the optimal revenue can be extracted, where d denotes the “degree of dependence” of the valuations, ranging from complete independence ( $$d=0$$ ) to arbitrary dependence ( $$d = n-1$$ ). When we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the i-th buyer that depends on the valuations of all buyers except i, we prove that a constant fraction $$(2 - \sqrt{e})/4 \approx 0.088$$ of the optimal revenue can be always extracted.

Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The resulting framework gives rise to complex preferences that depend on the specifics of the stochastic diffusion model and the network topology.

Result diversification has many important applications in databases, operations research, information retrieval, and finance. In this paper, we study and extend a particular version of result diversification, known as max-sum diversification. More specifically, we consider the setting where we are given a set of elements in a metric space and a set valuation function f defined on every subset. For any given subset S, the overall objective is a linear combination of f(S) and the sum of the distances induced by S. The goal is to find a subset S satisfying some constraints that maximizes the overall objective.

In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = ( V, E ) with n vertices is said to have an inductive neighborhood property with respect to P if there is an ordering of vertices v 1 , …, v n such that the property P holds on the induced subgraph G [ N ( v i )∩ V i ], where N ( v i ) is the neighborhood of v i and V i = { v i , …, v n }. It turns out that if we take P as a graph with maximum independent set size no greater than k , then this definition gives a natural generalization of both chordal graphs and ( k + 1)-claw-free graphs. We refer to such graphs as inductive k -independent graphs. We study properties of such families of graphs, and we show that several natural classes of graphs are inductive k -independent for small k . In particular, any intersection graph of translates of a convex object in a two dimensional plane is an inductive 3 -independent graph; furthermore, any planar graph is an inductive 3 -independent graph. For any fixed constant k , we develop simple, polynomial time approximation algorithms for inductive k -independent graphs with respect to several well-studied NP-complete problems. Our generalized formulation unifies and extends several previously known results.

We consider a model (BT) for backtracking algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as interval scheduling, knapsack and satisfiability.

We define an algorithmic paradigm, the stack model, that captures many primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations and hence our approximation bounds are independent of the P versus NP question. Using the stack model, we bound the performance of a broad class of primal-dual and local-ratio algorithms and supply a (log n +1)/2 inapproximability result for set cover, a 4/3 inapproximability for min Steiner tree, and a 0.913 inapproximability for interval scheduling on two machines.

We study mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded. This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, and others. We focus on the problem of designing mechanisms that approximately optimize social welfare at every Bayes-Nash equilibrium (BNE), which is the standard notion of equilibrium in settings of incomplete information. For a broad class of greedy approximation algorithms, we give a general black-box reduction to deterministic mechanisms with almost no loss to the approximation ratio at any BNE. We also consider the special case of Nash equilibria in full-information games, where we obtain tightened results. This solution concept is closely related to the well-studied price of anarchy. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for our mechanisms. For many problems, the approximation factors we obtain at equilibrium improve upon the best known results for deterministic truthful mechanisms. In particular, we exhibit a simple deterministic mechanism for general combinatorial auctions that obtains an approximation at every BNE.

The explosive growth and the widespread accessibility of the Web has led to a surge of research activity in the area of information retrieval on the World Wide Web. The seminal papers of Kleinberg [1998, 1999] and Brin and Page [1998] introducedLink Analysis Ranking, where hyperlink structures are used to determine the relativeauthorityof a Web page and produce improved algorithms for the ranking of Web search results. In this article we work within the hubs and authorities framework defined by Kleinberg and we propose new families of algorithms. Two of the algorithms we propose use a Bayesian approach, as opposed to the usual algebraic and graph theoretic approaches. We also introduce a theoretical framework for the study of Link Analysis Ranking algorithms. The framework allows for the definition of specific properties of Link Analysis Ranking algorithms, as well as for comparing different algorithms. We study the properties of the algorithms that we define, and we provide an axiomatic characterization of the INDEGREE heuristic which ranks each node according to the number of incoming links. We conclude the article with an extensive experimental evaluation. We study the quality of the algorithms, and we examine how different structures in the graphs affect their performance.

A novel algorithm for actively trading stocks is presented. While traditional expert advice and ``universal'' algorithms (as well as standard technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirical results on historical markets provide strong evidence that this type of technical trading can ``beat the market'' and moreover, can beat the best stock in the market. In doing so we utilize a new idea for smoothing critical parameters in the context of expert learning.

A novel algorithm for actively trading stocks is presented. While tradi- tional universal algorithms (and technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirical results on historical markets provide strong evidence that this type of techni- cal trading can “beat the market” and moreover, can beat the best stock in the market. In doing so we utilize a new idea for smoothing critical parameters in the context of expert learning. 1 Introduction: The Portfolio Selection Problem The portfolio selection (PS) problem is a challenging problem for machine learning, online algorithms and, of course, computational finance. As is well known (e.g. see Lugosi [1]) sequence prediction under the log loss measure can be viewed as a special case of portfo- lio selection, and perhaps more surprisingly, from a certain worst case minimax criterion, portfolio selection is not essentially any harder (than prediction) as shown in [2] (see also [1], Thm. 20 & 21). But there seems to be a qualitative difference between the practical utility of “universal” sequence prediction and universal portfolio selection. Simply stated, universal sequence prediction algorithms under various probabilistic and worst-case mod- els work very well in practice whereas the known universal portfolio selection algorithms do not seem to provide any substantial benefit over a naive investment strategy (see Sec. 4). A major pragmatic question is whether or not a computer program can consistently out- perform the market. A closer inspection of the interesting ideas developed in information theory and online learning suggests that a promising approach is to exploit the natural volatility in the market and in particular to benefit from simple and rather persistent statis- tical relations between stocks rather than to try to predict stock prices or “winners”. We present a non-universal portfolio selection algorithm1, which does not try to predict win- ners. The motivation behind our algorithm is the rationale behind constant rebalancing algorithms and the worst case study of universal trading introduced by Cover [3]. Not only does our proposed algorithm substantially “beat the market” on historical markets, it also beats the best stock. So why are we presenting this algorithm and not just simply making money? There are, of course some caveats and obstacles to utilizing the algorithm. But for large investors the possibility of a goose laying silver (if not golden) eggs is not impossible. 1Any PS algorithm can be modified to be universal by investing any fixed fraction of the initial wealth in a universal algorithm.

Recently, ther have been a number of algorH#-9 prC osed for analyzing hyperDCC link str5#TDso as todeterCDthe best "authorODHUM for a given topic or quer . While such analysis is usually combined with content analysis, ther is a sense in which some algorUO-9 ar deemed to be"mor balanced" andother "mor focused". WeunderDe a compar --C e study of hyperDTD link analysisalgor-CDCO Guided by some experD#C tal quer5CD we prD ose somefor-C crC5O r for evaluating and comparTlink analysisalgor-CUH5 Keywords link analysis, websear hing, hubs, author-9TD5 SALSA, KleinberMU algor9T#5 thrCHHE-9 Bayesian 1.

We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.

IntroductionThe cw.w of dimensionality describes the phenomenon whereby (in spite of extensive and continuing research) for various geometric search problems we only have algorithms with performance that grows exponentially in the dimension.Recent results [31,30, 331 show that in some sense it is possible to avoid the curse of dimensionality for the approximate nearest neighbor search problem.But must the exact nearest neighbor search problem suffer this curse?We provide some evidence in support of the curse.Specifically we investigate the exact nearest neighbor search problem and the related problem of exact partial match within the asymmetric communication model first used by Miltersen [36] to study data structure problems.We derive non-trivial asymptotic lower bounds for the exact problem that stand in contrast to known algorithms for approximate nearest neighbor search.Background.

One of the central problems in information retrieval, data mining, computational biology, statistical analysis, computer vision, geographic analysis, pattern recognition, distributed protocols is the question of classification of data according to some clustering rule. Often the data is noisy and even approximate classification is of extreme importance. The difficulty of such classification stems from the fact that usually the data has many incomparable attributes, and often results in the question of clustering problems in high dimensional spaces. Since they require measuring distance between every pair of data points, standard algorithms for computing the exact clustering solutions use quadratic or "nearly quadratic" running time; i.e., O(dn 2\\Gammaff(d) ) time where n is the number of data points, d is the dimen- Computer Science Department, University of Toronto. Part of this work was done while visiting Bell Communications Research. y Bell Communications Research, MCC-1C365...

We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff's "jumping automata for graphs."

This paper concerns two fundamental but somewhat neglected issues both related to the design and analysis of randomized online algorithms. Motivated by early results in game theory we define several types of randomized online algorithms discuss known conditions for their equivalence and give a natural example distinguishing between two kinds of randomizations. In particular we show that mixed randomized memoryless paging algorithms can achieve strictly better competitive performance than behavioral randomized algorithms. Next we summarize known-and derive new-"Yao Principle" theorems for lower bounding competitive ratios of randomized online algorithms. This leads to six different theorems for bounded/unbounded and minimization/maximization problems.

We study the extent to which complex hardware can speed up routing. Specifically, we consider the following questions. How much does adaptive routing improve over oblivious routing? How much does randomness help? How does it help if each node can have a large number of neighbors? What benefit is available if a node can send packets to several neighbors within a single time step? Some of these features require complex networking hardware, and it is thus important to investigate whether the performance justifies the investment. By varying these hardware parameters, we obtain a hierarchy of time bounds for worst-case permutation routing.

We consider algorithms for many-to-many hot potato routing. In hot potato (deflection) routing, a packet cannot be buffered, and is therefore always moving until it reaches its destination. We give optimal and nearly optimal deterministic algorithms for many-to-many packet routing in commonly occurring networks such as the hypercube, meshes, and tori of various dimensions and sizes, trees, and hypercubic networks such as the butterfly. All these algorithms are analyzed using a charging scheme that may be applicable to other algorithms as well. Moreover, all bounds hold in a dynamic setting in which packets can be injected at arbitrary times.

We introduce a new approach to the study of dynamic (or continuous) packet routing, where packets are being continuously injected into a network. Our objective is to study what happens to packet routing under continuous injection as a function of network load, for various queueing policies. Our approach is based on the adversarial generation of packets, so that the results are more robust in that they do not hinge upon particular probabilistic assumptions. In suggesting a new approach to studying a classical phenomenon, it is important to give careful consideration to all the relevant previous work in packet routing, queueing theory and probabilistic analysis. We give a more detailed account of previous work in Appendix A, to permit comparison with our work. Here we summarize the salient features of prior work in order to motivate our model. Most prior work on packet routing has been in the static model in which there is a fixed initial set of packet ro

We study the extent to which complex hardware can speed up routing.Specifically, we consider the following questions.How much does adaptive routing improve over oblivious routing?How much does randomness help?How does it help if each node can have a large number of neighbors?What benefit is available if a node can send packets to several neighbors within a single time step?Some of these features require complex networking

In practice, almost all dynamic systems require decisions to be made on-line, without full knowledge of their future impact on the system. A general model for the processing of sequences of tasks is introduced, and a general on-line decision algorithm is developed. It is shown that, for an important class of special cases, this algorithm is optimal among all on-line algorithms. Specifically, a task system ( S,d ) for processing sequences of tasks consists of a set S of states and a cost matrix d where d ( i, j is the cost of changing from state i to state j (we assume that d satisfies the triangle inequality and all diagonal entries are 0). The cost of processing a given task depends on the state of the system. A schedule for a sequence T 1 , T 2 ,…, T k of tasks is a sequence s 1 , s 2 ,…, s k of states where s i is the state in which T i is processed; the cost of a schedule is the sum of all task processing costs and the state transition costs incurred. An on-line scheduling algorithm is one that chooses s i only knowing T 1 T 2 … T i . Such an algorithm is w -competitive if, on any input task sequence, its cost is within an additive constant of w times the optimal offline schedule cost. The competitive ratio w ( S , d ) is the infimum w for which there is a w -competitive on-line scheduling algorithm for ( S , d ). It is shown that w ( S , d ) = 2|S|–1 for every task system in which d is symmetric, and w ( S, d ) = O (| S | 2 ) for every task system. Finally, randomized on-line scheduling algorithms are introduced. It is shown that for the uniform task system (in which d ( i,j ) = 1 for all i,j ), the expected competitive ratio w¯ ( S,d ) = O (log|S|).

The Sleator-Tarjan competitive analysis of paging [19] gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input.Nevertheless practitioners voice reservations about the model, citing its inability to discern between is that it is more robust than probabilistic analysis, while more practical than worst-case analysis.With these definitions, Sleator and Tarjan showed that no deterministic on-line paging algorithm can achieve a competitiveness less than k, and that a number of algorithms used in practice (including Least Recently Used or LRU and First-In First-Out or FIFO) are kcompetitive and thus optimal by this measure.

Time-space tradeoffs for traversing undirected graphs are proved. One of these tradeoffs is a quadratic lower bound on a deterministic model that closely matches the probabilistic upper bound of A.Z. Broder et al. (1989). The models used are variants of S.A. Cook and C.W. Rackoff's (1980) jumping automata for graphs. Some open problems are stated.>

No abstract available.

We consider the problem of determining whether or not there exists a sparse univariate polynomial p(x) that interpolates a given set S = {(xi, Yi)} of points.Several important cases are resolved, e.g., the case when the zi's are all positive.But the general problem remains open.

Universal traversal sequences for d-regular n-vertex graphs require length Ω(d2n2 + dn2 log n/d), for 3 ≤ d ≤ n/3 - 2. This is nearly tight for d = Θ(n). We also introduce and study several variations on the problem, e.g. edge-universal traversal sequences, showing how improved lower bounds on these would improve the bounds given above.

Universal sequences for graphs, a concept introduced by Aleliunas [M.Sc. thesis, University of Toronto, Toronto, Ontario, Canada, January 1978] and Aleliunas et al. [Proc. 20th Annual Symposium on Foundation of Computer Science, 1979, pp. 218–223] are studied. By letting $U(d,n)$ denote the minimum length of a universal sequence for d-regular undirected graphs with n nodes, the latter paper has proved the upper bound $U(d,n) = O(d^2 n^3 \log n)$ using a probabilistic argument. Here a lower bound of $U(2,n) = \Omega (n\log n)$ is proved from which $U(d,n) = \Omega (n\log n)$ for all d is deduced. Also, for complete graphs $U(n - 1,n) = \Omega ({{n\log ^2 n} / {\log \log n}})$. An explicit construction of universal sequences for cycles $(d = 2)$ of length $n^{O(\log n)} $ is given.

Following the recent independent proofs of Immerman [SIAM J. Comput., 17 (1988), pp. 935–938] and Szelepcsenyi [Bull. European Assoc. Theoret. Comput. Sci., 33 (1987), pp. 96–100] that nondeterministic space-bounded complexity classes are closed under complementation, two further applications of the inductive counting technique are developed. First, an errorless probabilistic algorithm for the undirected graph s-t connectivity problem that runs in $O(\log n)$ space and polynomial expected time is given. Then it is shown that the class LOGCFL is closed under complementation. The latter is a special case of a general result that shows closure under complementation of classes defined by semi-unbounded fan-in circuits (or, equivalently, nondeterministic auxiliary pushdown automata or tree-size bounded alternating Turing machines). As one consequence, it is shown that small numbers of “role switches” in two-person pebbling can be eliminated.

Previous article Full AccessErratum: Two Applications of Indctive Counting for Complementation ProblemsAllan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin TompaAllan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompahttps://doi.org/10.1137/0218084PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: Two Applications of Indctive Counting for Complementation Problems." SIAM Journal on Computing, 18(6), p. 1283[1] Allan Borodin, , Stephen A. Cook, , Patrick W. Dymond, , Walter L. Ruzzo and , Martin Tompa, Two applications of inductive counting for complementation problems, SIAM J. Comput., 18 (1989), 559–578 10.1137/0218038 90k:68049a 0678.68031 LinkISIGoogle Scholar[2] John Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6 (1977), 675–695 10.1137/0206049 57:4616 0366.02024 LinkISIGoogle Scholar[3] Hermann Jung, On probabilistic time and spaceAutomata, languages and programming (Nafplion, 1985), Lecture Notes in Comput. Sci., Vol. 194, Springer, Berlin, 1985, 310–317 87b:68039 0599.68043 CrossrefGoogle Scholar Previous article FiguresRelatedReferencesCited byDetails Dual VP Classes23 September 2016 | computational complexity, Vol. 26, No. 3 Cross Ref Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages Cross Ref Computational Complexity Cross Ref Trading Space for Time in Undirected s-t ConnectivityAndrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, and Eli Upfal31 July 2006 | SIAM Journal on Computing, Vol. 23, No. 2AbstractPDF (1266 KB)My favorite ten complexity theorems of the past decade1 June 2005 Cross Ref Lower bounds on the length of universal traversal sequencesJournal of Computer and System Sciences, Vol. 45, No. 2 Cross Ref A very hard log space counting class Cross Ref Volume 18, Issue 6| 1989SIAM Journal on Computing History Submitted:03 August 1989Accepted:30 August 1989Published online:13 July 2006 InformationCopyright © 1989 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0218084Article page range:pp. 1283-1283ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes that communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against process failure through unannounced stopping, making it attractive also for use in an environment of processes of widely differing speeds. In addition to its practical advantages, we show that for fixed k , the shared space complexity of the algorithm as a function of the number N of processes is optimal to within a constant factor.

In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms.

In A time space tradeoff for sorting on non-oblivious machines, Borodin et al. [J. Comput. System Sci., 22 (1981), pp. 351–364] proved that to sort n elements requires $TS = \Omega (n^2 )$ where $T = $ time and $S = $ space on a comparison based branching program. Although element distinctness and sorting are equivalent problems on a computation tree, the stated tradeoff result does not immediately follow for element distinctness or indeed for any decision problem. In this paper, we are able to show that $TS = \Omega (n^{{3 / 2}} \sqrt {\log n} )$ for deciding element distinctness (or the sign of a permutation).

Branching programs have been studied as a fundamental model for space bounded computations and, in particular, as a model in which to try to establish nontrivial space lower bounds and time-space trade-offs. At present, there still do not exist any results for single output functions. We consider a class of severely constrained programs (those having width 2) and establish characterizations as well as lower bounds for some Boolean functions computable within this model.

Branching programs for the computation of Boolean functions were first studied in the Master's thesis of Masek.7 In a rather straightforward manner they generalize the concept of a decision tree to a decision graph.

We present parallel algorithms to compute the determinant and characteristic polynomial of n×n-matrices and the gcd of polynomials of degree ≤n. The algorithms use parallel time O(log2n) and a polynomial number of processors. We also give a fast parallel Las Vegas algorithm for the rank of matrices. All algorithms work over arbitrary fields.

A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. We distinguish two classes of models, fixed connection networks and models based on a shared memory. Routing is the prototype problem for the networks. In particular, routing provides the basis for simulating the more powerful shared memory models. We show that a simple but important class of deterministic strategies (oblivious routing) is necessarily inefficient with respect to worst case analysis. Routing can be viewed as a special case of sorting and the existence of a deterministic O(logn) routing or sorting algorithm for an n processor fixed connection network remains open. However, if we consider the more powerful class of shared memory models, we are “almost” able to achieve such an efficient sort via Valiant's parallel merging algorithm. Within a spectrum of models, we show that log log n - log log r is asymptotically optimal for rn processors to merge two sorted lists of n elements.

In a general sequential model of computation, no restrictions are placed on the way in which the computation may proceed, except that parallel operations are not allowed. We show that in such an unrestricted environment ${\text{TIME}} \cdot {\text{SPACE}} = \Omega (N^2 /\log N)$ in order to sort N integers, each in the range $[1,N^2 ]$.

In a general sequential model of computation, no restrictions are placed on the way in which the computation may proceed, except parallel operations are not allowed. We show that in such an unrestricted environment TIME•SPACE=Ω(N2/log N) in order to sort N elements, each in the range [1,N2].

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

Upper and lower bounds are proved for the shared space requirements for solution of several problems involving resource allocation among asynchronous processes. Controlling the degradation of performance when a limited number of processes fail is of particular interest.

Turing machine space complexity is related to circuit depth complexity. The relationship complements the known connection between Turing machine time and circuit size, thus enabling us to expose the related nature of some important open problems concerning Turing machine and circuit complexity. We are also able to show some connection between Turing machine complexity and arithmetic complexity.

The number of addition-subtraction operations required to compute univariate pol nomials is investigated. The existence of rational coefficient polynomials of degree n requiring $ \sim (\sqrt n ) \pm $ operations is established using an argument based on algebraic independence. A more analytic argument is used to relate $ \pm $ complexity to the number of distinct real zeros possessed by a given real coefficient polynomial.

It is well known from the work of Motzkin [55], Belaga [58] and Pan [66], that “most” nth degree polynomials p ε R[x] require about n/2 ×, ÷ ops and n ± ops and that these bounds can always be achieved within the framework of preconditioned evaluation (1). More precisely, if p can be computed using less than [equation] ×, ÷ or less than n ± ops, then the coefficients of p are algebraically dependent.

Some consequences of the Blum axioms for step counting functions are investigated.Complexity classes of recursive functions are introduced analogous to the Hartmanis-Stearns classes of recursive sequences.Arbitrarily large "gaps" are shown to occur throughout any complexity hierarchy.

No abstract available.

The structural complexity of programming languages, and therefore of programs as well, can be measured by the subrecursive class of functions which characterize the language.Using such a measure of structural complexity, we examine the trade-off relationship between structural and computational complexity.Since measures of structural complexity directly related to high level languages interest us most, we use abstract language models which approximate highly structured languages like Algol.