Abstract. We study the problem of finding a Tarski fixed point over the [Formula: see text]-dimensional grid [Formula: see text]. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique Tarski problem have exactly the same query complexity. Our reduction is based on a novel notion of partial-information functions which we use to fool algorithms for the unique Tarski problem as if they were working on a monotone function with a unique fixed point.

We give an algorithm for finding an ε-fixed point of a contraction map f : [0, 1] k \(\mapsto\) [0, 1] k under the \(\ell _\infty\) -norm with query complexity O ( k log (1/ε).

Abstract. In 1979, Hylland and Zeckhauser [ J. Polit. Econ., 87 (1979), pp. 293–314] gave a simple and general mechanism for a one-sided matching market, given cardinal utilities of agents over goods. They use the power of a pricing mechanism, which endows their mechanism with several desirable properties—it produces an allocation that is Pareto optimal and envy free, and the mechanism is incentive compatible in the large. It therefore provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to characterize the computational complexity of this mechanism. We present the following results: (1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., [Formula: see text] utilities, and more generally, when each agent’s utilities come from a bivalued set. (2) An example that has only irrational equilibria; hence this problem is not in PPAD. (3) A proof of membership of the problem in the class FIXP; as a corollary we get that a Hylland–Zeckhauser (HZ) equilibrium can always be expressed via algebraic numbers. For this purpose, we give a new proof of the existence of an HZ equilibrium using Brouwer’s fixed point theorem; the proof of Hylland and Zeckhauser used Kakutani’s fixed point theorem, which is more involved. (4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. In subsequent work [T. Chen et al., SODA 2022, SIAM, Philadelphia, pp. 2253–2268], the problem of computing an approximate HZ equilibrium was shown to be PPAD-hard, thereby establishing it to be PPAD-complete. We leave open the (difficult) question of determining if computing an exact HZ equilibrium is FIXP-hard. We also give pointers to the substantial body of work on cardinal-utility matching markets which followed [V. V. Vazirani and M. Yannakakis, LIPIcs. Leibniz Int. Proc. Inform. 185, Schloss Dagstuhl, Wadern Germany, 59].

Fairness in clustering has been considered extensively in the past; however, the trade-off between the two objectives --- e.g., can we sacrifice just a little in the quality of the clustering to significantly increase fairness, or vice-versa? --- has rarely been addressed. We introduce novel algorithms for tracing the complete trade-off curve, or Pareto front, between quality and fairness in clustering problems; that is, computing all clusterings that are not dominated in both objectives by other clusterings. Unlike previous work that deals with specific objectives for quality and fairness, we deal with all objectives for fairness and quality in two general classes encompassing most of the special cases addressed in previous work. Our algorithm must take exponential time in the worst case as the Parero front itself can be exponential. Even when the Pareto front is polynomial, our algorithm may take exponential time, and we prove that this is inevitable unless P = NP. However, we also present a new polynomial-time algorithm for computing the entire Pareto front when the cluster centers are fixed, and for perhaps the most natural fairness objective: minimizing the sum, over all clusters, of the imbalance between the two groups in each cluster.

We give the first quasipolynomial upper bound φnpolylog(n) for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width) under the full perturbation model, where n is the number of nodes in the graph and φ is a parameter that measures the magnitude of perturbations applied on its edge weights. More generally, we show that the same quasipolynomial upper bound holds for the smoothed complexity of the 2-FLIP algorithm for any binary Maximum Constraint Satisfaction Problem, including local Max-Cut, for which similar bounds were only known for 1-FLIP. Our results are based on an analysis of a new notion of useful cycles in the multigraph formed by long sequences of double flips, showing that it is unlikely for every double flip in a long sequence to incur a positive but small improvement in the cut weight.

We give an algorithm for finding an є-fixed point of a contraction map f:[0,1]k↦[0,1]k under the ℓ∞-norm with query complexity O (k2log(1/є ) ).

We study the complexity of computational problems arising from existence theorems in extremal combinatorics. For some of these problems, a solution is guaranteed to exist based on an iterated application of the Pigeonhole Principle. This results in the definition of a new complexity class within TFNP, which we call PLC (for "polynomial long choice"). PLC includes all of PPP, as well as numerous previously unclassified total problems, including search problems related to Ramsey's theorem, the Sunflower theorem, the Erdős-Ko-Rado lemma, and König's lemma. Whether the first two of these four problems are PLC-complete is an important open question which we pursue; in contrast, we show that the latter two are PPP-complete. Finally, we reframe PPP as an optimization problem, and define a hierarchy of such problems related to Turán's theorem.

We show subexponential lower bounds (i.e., 2Ω (nc)) on the smoothed complexity of the classical Howard’s Policy Iteration algorithm for Markov Decision Processes. The bounds hold for the total reward and the average reward criteria. The constructions are robust in the sense that the subexponential bound holds not only on the average for independent random perturbations of the MDP parameters (transition probabilities and rewards), but for all arbitrary perturbations within an inverse polynomial range. We show also an exponential lower bound on the worst-case complexity for the simple reachability objective.

We study the complexity of the classic Hylland-Zeckhauser scheme [21] for one-sided matching markets. We show that the problem of finding an ∊-approximate equilibrium in the HZ scheme is PPAD-hard, and this holds even when ∊ is polynomially small and when each agent has no more than four distinct utility values. Our hardness result, when combined with the PPAD membership result of [29], resolves the approximation complexity of the HZ scheme. We also show that the problem of approximating within a certain constant factor the optimal social welfare (the weight of the matching) achievable by HZ equilibria is NP-hard.

We study the optimal lottery problem and the optimal mechanism design problem in the setting of a single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables. For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value). For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly, ${P}^{{NP}}={P}^{{\#P}}$), there is no efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.

Intent-Based Networking (IBN) has been increasingly deployed in production enterprise networks. Automated network configuration in IBN lets operators focus on intents- i.e., the end to end business objectives-rather than spelling out details of the configurations that implement these objectives. Automation brings its own concerns as the administrators cannot rely on traditional network troubleshooting tools. This situation is further exacerbated in the case of stateful Network Functions (NFs) whose packet processing behavior depends on previously observed traffic patterns. To ensure that the network configuration and state derived from network automation matches the administrator’s specified intent, we propose, Epinoia, a network intent checker for stateful networks. Epinoia relies on a unified model for NFs by leveraging the causal precedence relationships that exist between NF packet I/Os and states. Scalability of Epinoia is achieved by decomposing intents into sub-checking tasks and maintaining a causality graph between checked invariants. Epinoia checks for network-wide intent violations incrementally to reduce overhead in the event of network changes. Our evaluation results using real-world network topologies show that Epinoia can perform comprehensive checking within a few seconds per network with intent updates.

In 1979, Hylland and Zeckhauser [Hylland and Zeckhauser, 1979] gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties - it is incentive compatible in the large and produces an allocation that is Pareto optimal - and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 2) An example that has only irrational equilibria, hence proving that this problem is not in PPAD. 3) A proof of membership of the problem in the class FIXP. 4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. We leave open the (difficult) questions of determining if computing an exact HZ equilibrium is FIXP-hard and an approximate HZ equilibrium is PPAD-hard.

This paper presents an efficient topology and route management approach in Software-Defined Wide Area Networks (SD-WAN). Traditional WANs suffer from low utilization and lack of global view of the network. Therefore, during failures, topology/service/traffic changes, or new policy requirements, the system does not always converge to the global optimal state. Using Software Defined Networking architectures in WANs provides the opportunity to design WANs with higher fault tolerance, scalability, and manageability. We exploit the correlation matrix derived from monitoring system between the virtual links to infer the underlying route topology and propose a route update approach that minimizes the total route update cost on all flows. We formulate the problem as an integer linear programming optimization problem and provide a centralized control approach that minimizes the total cost while satisfying the quality of service (QoS) on all flows. Experimental results on real network topologies demonstrate the effectiveness of the proposed approach in terms of disruption cost and average disrupted flows.

The use of monotonicity and Tarski's theorem in existence proofs of equilibria is very widespread in economics, while Tarski's theorem is also often used for similar purposes in the context of verification. However, there has been relatively little in the way of analysis of the complexity of finding the fixed points and equilibria guaranteed by this result. We study a computational formalism based on monotone functions on the $d$-dimensional grid with sides of length $N$, and their fixed points, as well as the closely connected subject of supermodular games and their equilibria. It is known that finding some (any) fixed point of a monotone function can be done in time $\log^d N$, and we show it requires at least $\log^2 N$ function evaluations already on the 2-dimensional grid, even for randomized algorithms. We show that the general Tarski problem of finding some fixed point, when the monotone function is given succinctly (by a boolean circuit), is in the class PLS of problems solvable by local search and, rather surprisingly, also in the class PPAD. Finding the greatest or least fixed point guaranteed by Tarski's theorem, however, requires $d\cdot N$ steps, and is NP-hard in the white box model. For supermodular games, we show that finding an equilibrium is essentially computationally equivalent to the Tarski problem, and finding the maximum or minimum equilibrium is similarly harder. Interestingly, two-player supermodular games where the strategy space of one player is one-dimensional can be solved in $O(\log N)$ steps. We also show that computing (approximating) the value of Condon's (Shapley's) stochastic games reduces to the Tarski problem. An important open problem highlighted by this work is proving better upper or lower bounds on the (blackbox query) complexity of the Tarski problem.

We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most φ n O(√logn), where n is the number of nodes in the graph and φ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of φ n O(logn) by Etscheid and Roglin. Our result is based on an analysis of long sequences of flips, which shows that it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.

We introduce and study the doubly balanced connected graph partitioning problem: Let G =( V , E ) be a connected graph with a weight (supply/demand) function p : V → {−1, +1} satisfying p ( V )=∑ j &isin V p ( j ) = 0. The objective is to partition G into ( V 1 , V 2 ) such that G [ V 1 ] and G [ V 2 ] are connected, ∣ p ( V 1 )∣,∣ p ( V 2 )∣≤ c p , and max{ ∣ V 1 / V 2 ∣,∣ V 2 / V 1 ∣} ≤ c s , for some constants c p and c s . When G is 2-connected, we show that a solution with c p =1 and c s =2 always exists and can be found in randomized polynomial time. Moreover, when G is 3-connected, we show that there is always a “perfect” solution (a partition with p ( V 1 )= p ( V 2 )=0 and ∣ V 1 ∣=∣ V 2 ∣, if ∣ V ∣≡ 0 (mod 4)), and it can be found in randomized polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily ±1), and to the case that p ( V )≠ 0 and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types.

A graph G has an S-factor if there exists a spanning subgraph F of G such that for all v in V: deg_F(v) in S. The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational complexity of finding S-factors in regular graphs. Our techniques combine some classical as well as recent tools from graph theory.

We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperfect-information stochastic games that generalize both finite-state concurrent stochastic reachability games ([L. de Alfaro et al., 2007]) and branching simple stochastic reachability games ([K. Etessami et al., 2018]).

We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, more importantly, even when the optimal solution is guaranteed to be of a very simple kind: the seller picks a price for each individual item and a price for the grand bundle of all the items; the buyer can purchase either the grand bundle at its given price or any subset of items at their total individual prices. The following problems are also #P-hard, as immediate corollaries of the proof: 1. determining if individual item pricing is optimal for a given instance, 2. determining if grand bundle pricing is optimal, and 3. computing the optimal (deterministic) revenue. On the positive side, we show that when the distributions are i.i.d. with support size 2, the optimal revenue obtainable by any mechanism, even a randomized one, can be achieved by a simple solution of the above kind (individual item pricing with a discounted price for the grand bundle) and furthermore, it can be computed in polynomial time. The problem can be solved in polynomial time too when the number of items is constant.

We introduce and study the Doubly Balanced Connected graph Partitioning (DBCP) problem: Let G=(V, E) be a connected graph with a weight (supply/demand) function p:V→{-1, +1} satisfying P(V)=∑j∊v p(j)=0· The objective is to partition G into (V1, V2) such that G[V1] and G[V2] are connected, |p(V1)|, |p(V2)|≤cp, and for some constants cp and cs · When G is 2-connected, we show that a solution with cp=1 and cs=3 always exists and can be found in polynomial time. Moreover, when G is 3-connected, we show that there is always a ‘perfect’ solution (a partition with p(V1)=p(V2)=0 and |V1| = |V2|, if |V|≡0(mod 4)), and it can be found in polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily ±1), and to the case that p(V)=0 and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types.

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone utilities. Building on this result, we settle the long-standing open problem regarding the computation of an approximate Arrow-Debreu market equilibrium in markets with CES utility functions, by proving that it is PPAD-complete when the Constant Elasticity of Substitution parameter ρ is any constant less than − 1.

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in $\log(1/\epsilon)$, where $\epsilon > 0$ is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.) We use this result to resolve several open problems regarding the computational complexity of computing key quantities associated with some classic and well studied stochastic processes, including multitype branching processes and stochastic context-free grammars.

The Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as multiobjective and parametric optimization, computational geometry, and graphics. We analyze the performance of the Chord algorithm, as compared to the optimal approximation that achieves a desired accuracy with the minimum number of points. We prove sharp upper and lower bounds, both in the worst case and average case settings.

We study the optimal lottery problem and the optimal mechanism design problem in the setting of a single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables. For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value). For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly, PNP = P#P), there is no universal efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.

Recent events demonstrated the vulnerability of power grids to cyber attacks and to physical attacks. Therefore, we focus on joint cyber and physical attacks and develop methods to retrieve the grid state information following such an attack. We consider a model in which an adversary attacks a zone by physically disconnecting some of its power lines and blocking the information flow from the zone to the grid's control center. We use tools from linear algebra and graph theory and leverage the properties of the power flow DC approximation to develop methods for information recovery. Using information observed outside the attacked zone, these methods recover information about the disconnected lines and the phase angles at the buses. We identify sufficient conditions on the zone structure and constraints on the attack characteristics such that these methods can recover the information. We also show that it is NP-hard to find an approximate solution to the problem of partitioning the power grid into the minimum number of attack-resilient zones. However, since power grids can often be represented by planar graphs, we develop a constant approximation partitioning algorithm for these graphs. Finally, we numerically study the relationships between the grid's resilience and its structural properties, and demonstrate the partitioning algorithm on real power grids. The results can provide insights into the design of a secure control network for the smart grid.

We introduce Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs), which are classes of (finitely presented) countable-state MDPs and zero-sum turn-based (perfect information) stochastic games. They extend standard finite-state MDPs and stochastic games with a recursion feature. We study the decidability and computational complexity of these games under termination objectives for the two players: one player's goal is to maximize the probability of termination at a given exit, while the other player's goal is to minimize this probability. In the quantitative termination problems , given an RMDP (or RSSG) and probability p , we wish to decide whether the value of such a termination game is at least p (or at most p ); in the qualitative termination problem we wish to decide whether the value is 1. The important 1-exit subclasses of these models, 1-RMDPs and 1-RSSGs, correspond in a precise sense to controlled and game versions of classic stochastic models, including multitype Branching Processes and Stochastic Context-Free Grammars, where the objective of the players is to maximize or minimize the probability of termination (extinction). We provide a number of upper and lower bounds for qualitative and quantitative termination problems for RMDPs and RSSGs. We show both problems are undecidable for multi-exit RMDPs, but are decidable for 1-RMDPs and 1-RSSGs. Specifically, the quantitative termination problem is decidable in PSPACE for both 1-RMDPs and 1-RSSGs, and is at least as hard as the square root sum problem, a well-known open problem in numerical computation. We show that the qualitative termination problem for 1-RMDPs (i.e., a controlled version of branching processes) can be solved in polynomial time both for maximizing and minimizing 1-RMDPs. The qualitative problem for 1-RSSGs is in NP ∩ coNP, and is at least as hard as the quantitative termination problem for Condon's finite-state simple stochastic games, whose complexity remains a well known open problem. Finally, we show that even for 1-RMDPs, more general (qualitative and quantitative) model-checking problems with respect to linear-time temporal properties are undecidable even for a fixed property.

A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multitype branching processes, stochastic context-free grammars, probabilistic pushdown automata and recursive Markov chains) is the computation of termination probabilities, and computing these probabilities in turn boils down to computing the least fixed point (LFP) solution of a corresponding monotone polynomial system (MPS) of equations, denoted x = P ( x ). It was shown in Etessami and Yannakakis [2009] that a decomposed variant of Newton’s method converges monotonically to the LFP solution for any MPS that has a nonnegative solution. Subsequently, Esparza et al. [2010] obtained upper bounds on the convergence rate of Newton’s method for certain classes of MPSs. More recently, better upper bounds have been obtained for special classes of MPSs [Etessami et al. 2010, 2012]. However, prior to this article, for arbitrary (not necessarily strongly connected) MPSs, no upper bounds at all were known on the convergence rate of Newton’s method as a function of the encoding size |P| of the input MPS, x = P ( x ). In this article, we provide worst-case upper bounds, as a function of both the input encoding size |P|, and ε > 0, on the number of iterations required for decomposed Newton’s method (even with rounding) to converge to within additive error ε > 0 of q*, for an arbitrary MPS with LFP solution q*. Our upper bounds are essentially optimal in terms of several important parameters of the problem. Using our upper bounds, and building on prior work, we obtain the first P-time algorithm (in the standard Turing model of computation) for quantitative model checking, to within arbitrary desired precision, of discrete-time QBDs and (equivalently) probabilistic 1-counter automata, with respect to any (fixed) ω -regular or LTL property.

We resolve the complexity of revenue-optimal deterministic auctions in the unit-demand single-buyer Bayesian setting, i.e., the optimal item pricing problem, when the buyer's values for the items are independent. We show that the problem of computing a revenue-optimal pricing can be solved in polynomial time for distributions of support size 2 and its decision version is NP-complete for distributions of support size 3. We also show that the problem remains NP-complete for the case of identical distributions.

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We show that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone utilities. Building on this result, we settle the long-standing open problem regarding the computation of an approximate Arrow-Debreu market equilibrium in markets with CES utilities, by proving that it is PPAD-complete when the Constant Elasticity of Substitution parameter, ρ, is any constant less than -1.

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1/ε), where ε>0 is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.)

Recursive Markov Chains (RMCs) are a natural abstract model of procedural probabilistic programs and related systems involving recursion and probability. They succinctly define a class of denumerable Markov chains that generalize several other stochastic models, and they are equivalent in a precise sense to probabilistic Pushdown Systems. In this article, we study the problem of model checking an RMC against an ω -regular specification, given in terms of a Büchi automaton or a Linear Temporal Logic (LTL) formula. Namely, given an RMC A and a property, we wish to know the probability that an execution of A satisfies the property. We establish a number of strong upper bounds, as well as lower bounds, both for qualitative problems (is the probability = 1, or = 0?), and for quantitative problems (is the probability ≥ p ?, or, approximate the probability to within a desired precision). The complexity upper bounds we obtain for automata and LTL properties are similar, although the algorithms are different. We present algorithms for the qualitative model checking problem that run in polynomial space in the size | A | of the RMC and exponential time in the size of the property (the automaton or the LTL formula). For several classes of RMCs, including single-exit RMCs (a class that encompasses some well-studied stochastic models, for instance, stochastic context-free grammars) the algorithm runs in polynomial time in | A |. For the quantitative model checking problem, we present algorithms that run in polynomial space in the RMC and exponential space in the property. For the class of linearly recursive RMCs we can compute the exact probability in time polynomial in the RMC and exponential in the property. For deterministic automata specifications, all our complexities in the specification come down by one exponential. For lower bounds, we show that the qualitative model checking problem, even for a fixed RMC, is already EXPTIME-complete. On the other hand, even for simple reachability analysis, we know from our prior work that our PSPACE upper bounds in A can not be improved substantially without a breakthrough on a well-known open problem in the complexity of numerical computation.

Temporal synthesis is the automated construction of a system from its temporal specification. It is by now realized that requiring the synthesized system to satisfy the specifications against all possible environments may be too demanding, and, dually, allowing all systems may be not demanding enough. In this work we study bounded temporal synthesis, in which bounds on the sizes of the state space of the system and the environment are additional parameters to the synthesis problem. This study is motivated by the fact that such bounds may indeed change the answer to the synthesis problem, as well as the theoretical and computational aspects of the synthesis problem. In particular, a finer analysis of synthesis, which takes system and environment sizes into account, yields deeper insight into the quantificational structure of the synthesis problem and the relationship between strong synthesis -- there exists a system such that for all environments, the specification holds, and weak synthesis -- for all environments there exists a system such that the specification holds. We first show that unlike the unbounded setting, where determinacy of regular games implies that strong and weak synthesis coincide, these notions do not coincide in the bounded setting. We then turn to study the complexity of deciding strong and weak synthesis. We show that bounding the size of the system or both the system and the environment, turns the synthesis problem into a search problem, and one cannot expect to do better than brute-force search. In particular, the synthesis problem for bounded systems and environment is Sigma^P_2-complete (in terms of the bounds, for a specification given by a deterministic automaton). We also show that while bounding the environment may lead to the synthesis of specifications that are otherwise unrealizable, such relaxation of the problem comes at a high price from a complexity-theoretic point of view.

We consider Fisher and Arrow--Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written using polynomially many bits. There is no simple necessary and sufficient condition for the existence of an equilibrium: The problem of checking for existence of an equilibrium is NP-complete for both market models; the same holds for existence of an ε-approximate equilibrium, for ε = O ( n −5 ). Under standard (mild) sufficient conditions, the problem of finding an exact equilibrium is in PPAD for both market models. Finally, building on the techniques of Chen et al. [2009a] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard.

The Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjective and parametric optimization, computational geometry, and graphics. We analyze the performance of the Chord algorithm, as compared to the optimal approximation that achieves a desired accuracy with the minimum number of points. We prove sharp upper and lower bounds, both in the worst case and average case setting.

We reexamine what it means to compute Nash equilibria and, more generally, what it means to compute a fixed point of a given Brouwer function, and we investigate the complexity of the associated problems. Specifically, we study the complexity of the following problem: given a finite game, $\Gamma$, with 3 or more players, and given $\epsilon>0$, compute an approximation within $\epsilon$ of some (actual) Nash equilibrium. We show that approximation of an actual Nash equilibrium, even to within any nontrivial constant additive factor $\epsilon<1/2$ in just one desired coordinate, is at least as hard as the long-standing square-root sum problem, as well as a more general arithmetic circuit decision problem that characterizes P-time in a unit-cost model of computation with arbitrary precision rational arithmetic; thus, placing the approximation problem in P, or even NP, would resolve major open problems in the complexity of numerical computation. We show similar results for market equilibria: it is hard to estimate with any nontrivial accuracy the equilibrium prices in an exchange economy with a unique equilibrium, where the economy is given by explicit algebraic formulas for the excess demand functions. We define a class, FIXP, which captures search problems that can be cast as fixed point computation problems for functions represented by algebraic circuits (straight line programs) over basis $\{+,*,-,/,\max,\min\}$ with rational constants. We show that the (exact or approximate) computation of Nash equilibria for 3 or more players is complete for FIXP. The price equilibrium problem for exchange economies with algebraic demand functions is another FIXP-complete problem. We show that the piecewise linear fragment of FIXP equals PPAD. Many other problems in game theory, economics, and probability theory can be cast as fixed point problems for such algebraic functions. We discuss several important such problems: computing the value of Shapley's stochastic games and the simpler games of Condon, extinction probabilities of branching processes, probabilities of stochastic context-free grammars, and termination probabilities of recursive Markov chains. We show that for some of them, the approximation, or even exact computation, problem can be placed in PPAD, while for others, they are at least as hard as the square-root sum and arithmetic circuit decision problems.

We define Recursive Markov Chains (RMCs), a class of finitely presented denumerable Markov chains, and we study algorithms for their analysis. Informally, an RMC consists of a collection of finite-state Markov chains with the ability to invoke each other in a potentially recursive manner. RMCs offer a natural abstract model for probabilistic programs with procedures. They generalize, in a precise sense, a number of well-studied stochastic models, including Stochastic Context-Free Grammars (SCFG) and Multi-Type Branching Processes (MT-BP). We focus on algorithms for reachability and termination analysis for RMCs: what is the probability that an RMC started from a given state reaches another target state, or that it terminates? These probabilities are in general irrational, and they arise as (least) fixed point solutions to certain (monotone) systems of nonlinear equations associated with RMCs. We address both the qualitative problem of determining whether the probabilities are 0, 1 or in-between, and the quantitative problems of comparing the probabilities with a given bound, or approximating them to desired precision. We show that all these problems can be solved in PSPACE using a decision procedure for the Existential Theory of Reals. We provide a more practical algorithm, based on a decomposed version of multi-variate Newton's method, and prove that it always converges monotonically to the desired probabilities. We show this method applies more generally to any monotone polynomial system. We obtain polynomial-time algorithms for various special subclasses of RMCs. Among these: for SCFGs and MT-BPs (equivalently, for 1-exit RMCs) the qualitative problem can be solved in P-time; for linearly recursive RMCs the probabilities are rational and can be computed exactly in P-time. We show that our PSPACE upper bounds cannot be substantially improved without a breakthrough on long standing open problems: the square-root sum problem and an arithmetic circuit decision problem that captures P-time on the unit-cost rational arithmetic RAM model. We show that these problems reduce to the qualitative problem and to the approximation problem (to within any nontrivial error) for termination probabilities of general RMCs, and to the quantitative decision problem for termination (extinction) of SCFGs (MT-BPs).

We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy $\epsilon$ the Pareto curve of a multiobjective optimization problem. We show that for a broad class of biobjective problems (containing many important widely studied problems such as shortest paths, spanning tree, matching, and many others), we can compute in polynomial time an $\epsilon$-Pareto set that contains at most twice as many solutions as the minimum set. Furthermore we show that the factor of 2 is tight for these problems; i.e., it is NP-hard to do better. We present upper and lower bounds for three or more objectives, as well as for the dual problem of computing a specified number k of solutions which provide a good approximation to the Pareto curve.

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in 2-player normal form games, and (mixed) Nash equilibria in normal form games with 3 (or more) players. This paper reviews the underlying computational principles and the corresponding classes.

We study and provide efficient algorithms for multi-objective model checking problems for Markov Decision Processes (MDPs). Given an MDP, M, and given multiple linear-time (\omega -regular or LTL) properties \varphi\_i, and probabilities r\_i \epsilon [0,1], i=1,...,k, we ask whether there exists a strategy \sigma for the controller such that, for all i, the probability that a trajectory of M controlled by \sigma satisfies \varphi\_i is at least r\_i. We provide an algorithm that decides whether there exists such a strategy and if so produces it, and which runs in time polynomial in the size of the MDP. Such a strategy may require the use of both randomization and memory. We also consider more general multi-objective \omega -regular queries, which we motivate with an application to assume-guarantee compositional reasoning for probabilistic systems. Note that there can be trade-offs between different properties: satisfying property \varphi\_1 with high probability may necessitate satisfying \varphi\_2 with low probability. Viewing this as a multi-objective optimization problem, we want information about the "trade-off curve" or Pareto curve for maximizing the probabilities of different properties. We show that one can compute an approximate Pareto curve with respect to a set of \omega -regular properties in time polynomial in the size of the MDP. Our quantitative upper bounds use LP methods. We also study qualitative multi-objective model checking problems, and we show that these can be analysed by purely graph-theoretic methods, even though the strategies may still require both randomization and memory.

We reexamine, what it means to compute Nash equilibria and, more, generally, what it means to compute a fixed point of a given Brouwer function, and we investigate the complexity of the associated problems. Specifically, we study the complexity of the following problem: given a finite game, Gamma, with 3 or more players, and given epsiv > 0, compute a vector x' (a mixed strategy profile) that is within distance e (say in t^) of some (exact) Nash equilibrium. We show that approximation of an (actual) Nash equilibrium for games with 3 players, even to within any non-trivial constant additive factor epsiv*, -, /, max, min}, with rational constants. We show that the linear fragment of FIXP equals PPAD. Many problems in game theory, economics, and probability theory, can be cast as fixed point problems for such algebraic functions. We discuss several important such problems: computing the value of Shapley's stochastic games, and the simpler games of Condon, extinction probabilities of branching processes, termination probabilities of stochastic context-free grammars, and of Recursive Markov Chains. We show that for some of them, the approximation, or even exact computation, problem can be placed-in PPAD, while for others, they are at least as hard as the square-root sum and arithmetic circuit decision problems.

We study Recursive Concurrent Stochastic Games (RCSGs), extending our recent analysis of recursive simple stochastic games to a concurrent setting where the two players choose moves simultaneously and independently at each state. For multi-exit games, our earlier work already showed undecidability for basic questions like termination, thus we focus on the important case of single-exit RCSGs (1-RCSGs). We first characterize the value of a 1-RCSG termination game as the least fixed point solution of a system of nonlinear minimax functional equations, and use it to show PSPACE decidability for the quantitative termination problem. We then give a strategy improvement technique, which we use to show that player 1 (maximizer) has \epsilon-optimal randomized Stackless & Memoryless (r-SM) strategies for all \epsilon > 0, while player 2 (minimizer) has optimal r-SM strategies. Thus, such games are r-SM-determined. These results mirror and generalize in a strong sense the randomized memoryless determinacy results for finite stochastic games, and extend the classic Hoffman-Karp strategy improvement approach from the finite to an infinite state setting. The proofs in our infinite-state setting are very different however, relying on subtle analytic properties of certain power series that arise from studying 1-RCSGs. We show that our upper bounds, even for qualitative (probability 1) termination, can not be improved, even to NP, without a major breakthrough, by giving two reductions: first a P-time reduction from the long-standing square-root sum problem to the quantitative termination decision problem for finite concurrent stochastic games, and then a P-time reduction from the latter problem to the qualitative termination problem for 1-RCSGs.

Emergency alerting capability is crucial for the prompt response to natural disasters and terrorist attacks. The emerging network infrastructure and secure broadcast techniques enable prompt and secure delivery of emergency notification messages. With the ubiquitous deployment of alert systems, scalability and heterogeneity pose new challenges for the design of secure broadcast schemes. In this paper, we discuss the key generation problem with the goal of minimizing the total number of keys which need to be generated by the alert center and distributed to the users. Two encryption schemes, zero message scheme and extended header scheme, are modeled formally. For both schemes we show the equivalence of the general optimal key generation (OKG) problem and the bipartite clique cover (BCC) problem, and show that OKG problem is NP-hard. The result is then generalized to the case with resource constraints, and we provide a heuristic algorithm for solving the restricted BCC (and OKG) problem.

Recursive state machines (RSMs) enhance the power of ordinary state machines by allowing vertices to correspond either to ordinary states or to potentially recursive invocations of other state machines. RSMs can model the control flow in sequential imperative programs containing recursive procedure calls. They can be viewed as a visual notation extending Statecharts-like hierarchical state machines, where concurrency is disallowed but recursion is allowed. They are also related to various models of pushdown systems studied in the verification and program analysis communities.After introducing RSMs and comparing their expressiveness with other models, we focus on whether verification can be efficiently performed for RSMs. Our first goal is to examine the verification of linear time properties of RSMs. We begin this study by dealing with two key components for algorithmic analysis and model checking, namely, reachability (Is a target state reachable from initial states?) and cycle detection (Is there a reachable cycle containing an accepting state?). We show that both these problems can be solved in time O ( n θ 2 ) and space O ( n θ), where n is the size of the recursive machine and θ is the maximum, over all component state machines, of the minimum of the number of entries and the number of exits of each component. From this, we easily derive algorithms for linear time temporal logic model checking with the same complexity in the model. We then turn to properties in the branching time logic CTL*, and again demonstrate a bound linear in the size of the state machine, but only for the case of RSMs with a single exit node.

We discuss algorithmic problems arising in the testing of reactive systems, i.e. systems that interact with their environment. The goal is to design test sequences so that we can deduce desired information about the given system under test, such as whether it conforms to a given specification model, or whether it satisfies given requirement properties. Test generation can be approached from different points of view - as an optimization problem of minimizing cost and maximizing the effectiveness of the tests; as a game between tester and system under test; or as a learning problem. We touch on some of these aspects and related algorithmic questions.

Software designers draw message sequence charts for early modeling of the individual behaviors they expect from the concurrent system under design. Can they be sure that precisely the behaviors they have described are realizable by some implementation of the components of the concurrent system? If so, can we automatically synthesize concurrent state machines realizing the given MSCs? If, on the other hand, other unspecified and possibly unwanted scenarios are "implied" by their MSCs, can the software designer be automatically warned and provided the implied MSCs? In this paper, we provide a framework in which all these questions are answered positively. We first describe the formal framework within which one can derive implied MSCs and then provide polynomial-time algorithms for implication, realizability, and synthesis.

Finite-state machines are widely used to model systems in diverse areas. Often, the modeling machines can be decomposed into smaller component machines and this decomposition can facilitate the system design, implementation and analysis. J. Hartmanis and R.E. Stearns (1966) developed an elegant algebraic theory for machine decomposition that is based on the closed-partition lattice of a machine. In this paper, we study the computation of the closed-partition lattice of finite-state machines for the application to their decomposition. We present efficient algorithms for constructing the closed-partition lattice and for machine decomposition.

The optimization of queries in distributed database systems is known to be subject to delicate trade-offs. For example, the Mariposa database system allows users to specify a desired delay-cost tradeoff (that is, to supply a decreasing function u(d), specifying how much the user is willing to pay in order to receive the query results within time d); Mariposa divides a query graph into horizontal “strides,” analyzes each stride, and uses a greedy heuristic to find the “best” plan for all strides. We show that Mariposa's greedy heuristic can be arbitrarily far from the desired optimum. Applying a recent approach in multiobjective optimization algorithms to this problem, we show that the optimum cost-delay trade-off (Pareto) curve in Mariposa's framework can be approximated fast within any desired accuracy. We also present a polynomial algorithm for the general multiobjective query optimization problem, which approximates arbirarily well the optimum cost-delay tradeoff (without the restriction of Mariposa's heuristic stride subdivision).

Model checking is emerging as a practical tool for detecting logical errors in early stages of system design. We investigate the model checking of sequential hierarchical (nested) systems, i.e., finite-state machines whose states themselves can be other machines. This nesting ability is common in various software design methodologies, and is available in several commercial modeling tools. The straightforward way to analyze a hierarchical machine is to flatten it (thus incurring an exponential blow up) and apply a model-checking tool on the resulting ordinary FSM. We show that this flattening can be avoided. We develop algorithms for verifying linear-time requirements whose complexity is polynomial in the size of the hierarchical machine. We also address the verification of branching time requirements and provide efficient algorithms and matching lower bounds.

We study problems in multiobjective optimization, in which solutions to a combinatorial optimization problem are evaluated with respect to several cost criteria, and we are interested in the trade-off between these objectives (the so-called Pareto curve). We point out that, under very general conditions, there is a polynomially succinct curve that /spl epsiv/-approximates the Pareto curve, for any /spl epsiv/>0. We give a necessary and sufficient condition under which this approximate Pareto curve can be constructed in time polynomial in the size of the instance and 1//spl epsiv/. In the case of multiple linear objectives, we distinguish between two cases: when the underlying feasible region is convex, then we show that approximating the multi-objective problem is equivalent to approximating the single-objective problem. If however the feasible region is discrete, then we point out that the question reduces to an old and recurrent one: how does the complexity of a combinatorial optimization problem change when its feasible region is intersected with a hyperplane with small coefficients; we report some interesting new findings in this domain. Finally, we apply these concepts and techniques to formulate and solve approximately a cost-time-quality trade-off for optimizing access to the World-Wide Web, in a model first studied by Etzioni et al. (1996) (which was actually the original motivation for this work).

Software designers draw Message Sequence Charts for early modeling of the individual behaviors they expect from the concurrent system under design. Can they be sure that precisely the behaviors they have described are realizable by some implementation of the components of the concurrent system? If so, can one automatically synthesize concurrent state machines realizing the given MSCs? If, on the other hand, other unspecified and possibly unwanted scenarios are “implied” by their MSCs, can the software designer be automatically warned and provided the implied MSCs?

We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution U{j,k}, $1 < j \leq k,$ where each item size in {1/k,2/k,. . .,j/k} has probability 1/j of being chosen. Note that for fixed j,k as $m\rightarrow\infty$ the discrete distributions U{mj,mk} approach the continuous distribution U(0,j/k], where the item sizes are chosen uniformly from the interval (0,j/k]. We show that average-case behavior can differ substantially between the two types of distributions. In particular, for all j,k with j < k-1, there exist on-line algorithms that have constant expected wasted space under U{j,k}, whereas no on-line algorithm has even o(n 1/2 ) expected waste under U(0,u] for any $0 < u \leq 1$. Our U{j,k} result is an application of a general theorem of Courcoubetis and Weber [C. Courcoubetis and R.R. Weber, Probab. Engrg. Inform. Sci., 4 (1990), pp. 447--460] that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of n items must be either $\Theta (n)$, $\Theta (n^{1/2} )$, or O(1), depending on whether certain"perfect" packings exist. The perfect packing theorem needed for the U{j,k} distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper.

We study the approximability of two classes of network routing problems.The first class of problems in our study corre spend to classical multicommodity flow problems of the following form: We are given a network G with integer capacities on its edges, together with source-sink pairs (a, ti), 1 5 i 2 k, such that a positive integer demand di and a positive "profit" t'i is associated with eah pair.A feasible solution is a subset S of the (sir ti) pairs such that demands associated with pairs in S can be fully met through a routing which respects all capacity constraints, and the objective is to maximize the total profit associated with the satisfied pairs.We consider two natural variants: unsplittable flow (USF) where each pair must be satisfied by routing all its demand on a single

No abstract available.

Model checking is emerging as a practical tool for detecting logical errors in early stages of system design. We investigate the model checking of hierarchical (nested) systems, i.e. finite state machines whose states themselves can be other machines. This nesting ability is common in various software design methodologies and is available in several commercial modeling tools. The straightforward way to analyze a hierarchical machine is to flatten it (thus, incurring an exponential blow up) and apply a model checking tool on the resulting ordinary FSM. We show that this flattening can be avoided. We develop algorithms for verifying linear time requirements whose complexity is polynomial in the size of the hierarchical machine. We address also the verification of branching time requirements and provide efficient algorithms and matching lower bounds.

forefront of today's science (often referred to dramatically as "breaking the genetic code" or "the last phase of the We ahow that the protein folding problem in the two-dimensional Mendelian revolution").This mapping cm be rou&ly &-H-P model io NP-complete.

We revisit the issue of the complexity of database queries, in the light of the recent parametric refinement of complexity theory.We show that, if the query size (or the number of variables in the query) is considered as a parameter, then the relational calculus and its fragments (conjunctive queries, positive queries) are classified at appropriate levels of the so-called W hierarchy of Downey and Fellows.These results strongly suggest that the query size is inherently in the exponent of the data complexity of any query evaluation algorithm, with the implication becoming stronger as the expressibility of the query language increases.For recursive languages (fixpoint logic, Datalog) this is provably the case [14].On the positive side, we show that this exponential dependence can be avoided for the extension of acyclic queries with # (but not <) inequalities.IA third kind, expression complezify assun~cs that tho database instance is fixed, and is rarely differentiated from tho combined complexity.

In feature testing of communication protocols, we want to construct a minimal number of tests with a desirable fault coverage. We model the protocols by extended finite state machines and reduce the test generation process to optimization problems on graphs. We study efficient algorithms and their complexity. We report experimental results on real systems, including Personal HandyPhone System, a 5ESS based ISDN wireless system, and 5ESS Intelligent Network Application Protocol.

With advanced computer technology, systems are getting larger to fulfill more complicated tasks: however, they are also becoming less reliable. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of testing finite stare machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of states and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse areas, including sequential circuits, certain types of programs, and, more recently, communication protocols. In a testing problem we have a machine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and observing the outputs produced. Because of its practical importance and theoretical interest, the problem of testing finite state machines has been studied in different areas and at various times. The earliest published literature on this topic dates back to the 1950's. Activities in the 1960's mid early 1970's were motivated mainly by automata theory and sequential circuit testing. The area seemed to have mostly died down until a few years ago when the testing problem was resurrected and is now being studied anew due to its applications to conformance testing of communication protocols. While some old problems which had been open for decades were resolved recently, new concepts and more intriguing problems from new applications emerge. We review the fundamental problems in testing finite state machines and techniques for solving these problems, tracing progress in the area from its inception to the present and the stare of the art. In addition, we discuss extensions of finite state machines and some other topics related to testing.

Consider the multicommodity flow problem in which the object is to maximize the sum of commodities routed. We prove the following approximate max-flow min-multicut theorem: \[ \frac{{\min {\text{multicut}}}}{{O(\log k)}} \leqslant \max {\text{flow}} \leqslant \min {\text{multicut}}, \] where k is the number of commodities. Our proof is constructive; it enables us to find a multicut within $O(\log k)$ of the max flow (and hence also the optimal multicut). In addition, the proof technique provides a unified framework in which one can also analyse the case of flows with specified demands of Leighton and Rao and Klein et al. and thereby obtain an improved bound for the latter problem.

Database management systems address the need to store, retrieve, and manipulate large amounts of data in an organized fashion. The database held has grown tremendously in the last 25 years. It is reported that the database industry generated $7 billion in revenue in 1994 and is growing at a rate of 35% per year. Industrial and academic research have been instrumental to this growth. Theory has played an important role in defining the right abstractions and concepts, and providing a firm foundation for the field. In order to access effectively a large volume of data, one needs an abstract logical view of the data, which must be separate from the physical storage of data. The important first component of a database is therefore an abstract view of data (called the data model) and the accompanying specialized high-level language that is used to access the data. The second important component is the data structures that are used to store the data along with the algorithms to support the efficient translation from the logical to the physical world. The third important component is the mechanisms that allow the database to be accessed concurrently by many users, without violating its integrity. Theory has contributed to all three fronts, starting with what is undoubtedly the cornerstone of the area, the introduction and formal definition of the relational model by F.P. Codd (1970). It is a highly unusual compliment for theory when the major commercial products in the field have at their core a mathematically rigorous, formal model. Our primary aims in this paper will be to give a flavor of the types of problems that database theory addresses, and to review how research in the area has evolved over the years. At the end we will try to point to some topics that may be of interest to people in the FOCS community tempted to work in database theory.

We study the problem of uniquely identifying the initial state of a given finite-state machine from among a set of possible choices, based on the input-output behavior. Equivalently, given a set of machines, the problem is to design a test that distinguishes among them. We consider nondeterministic machines as well as probabilistic machines. In both cases, we show that it is Pspace-complete to decide whether there is a preset distinguishing strategy (i.e. a sequence of inputs fixed in advance), and it is Exptime-complete to decide whether there is an adaptive distinguishing strategy (i.e. when the next input can be chosen based on the outputs observed so far). The probabilistic testing is closely related to probabilistic games, or Markov Decision Processes, with incomplete information. We also provide optimal bounds for deciding whether such games have strategies winning with probability 1. 1 Introduction Finite-state machines have been widely used to model systems in diverse areas o...

We determine the complexity of testing whether a finite state, sequential or concurrent probabilistic program satisfies its specification expressed in linear-time temporal logic. For sequential programs, we present an algorithm that runs in time linear in the program and exponential in the specification, and also show that the problem is in PSPACE, matching the known lower bound. For concurrent programs, we show that the problem can be solved in time polynomial in the program and doubly exponential in the specification, and prove that it is complete for double exponential time. We also address these questions for specifications described by ω-automata or formulas in extended temporal logic.

Article Free Access Share on On complexity as bounded rationality (extended abstract) Authors: Christos H. Papadimitriou Department of Computer Science and Engineering, University of California at San Diego Department of Computer Science and Engineering, University of California at San DiegoView Profile , Mihalis Yannakakis AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 726–733https://doi.org/10.1145/195058.195445Online:23 May 1994Publication History 60citation1,269DownloadsMetricsTotal Citations60Total Downloads1,269Last 12 Months76Last 6 weeks9 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

We consider the following problem: given a collection of strings s 1 ,…, s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s . Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2 n ), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n ) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4 n . Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3 n . We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.

We prove results indicating that it is hard to compute efficiently good approximate solutions to the Graph Coloring, Set Covering and other related minimization problems.Specifically, there is an E > 0 such that Graph Coloring cannot be approximated with ratio n' unless P = NP.Set Covering cannot be approximated with ratio c log n for any c < l/4 unless NP is contained in DTIME(nP"Y'"~").Similar results follow for related problems such as Clique Cover, Fractional Chromatic Number, Dominating Set, and others.

In the multiterminal cut problem one is given an edge-weighted graph and a subset of the vertices called terminals, and is asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the mincut, max-flow problem, and can be solved in polynomial time. It is shown that the problem becomes NP-hard as soon as $k = 3$, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. A simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of ${{2 - 2} / k}$ of the optimal cut weight is also described.

We study the complexity of two fundamental problems in the testing of finite-state machines. 1) Distinguishing sequences (state identification). We show that it is PSPACE-complete to determine whether a finite-state machine has a preset distinguishing sequence. There are machines that have distinguishing sequences, but only of exponential length. We give a polynomial time algorithm that determines whether a finite-state machine has an adaptive distinguishing sequence. (The previous classical algorithms take exponential time.) Furthermore, if there is an adaptive distinguishing sequence, then we give an efficient algorithm that constructs such a sequence of length at most n(n/spl minus/1)/2 (which is the best possible), where n is the number of states. 2) Unique input output sequences (state verification). It is PSPACE-complete to determine whether a state of a machine has a unique input output sequence. There are machines whose states have unique input output sequences but only of exponential length.>

Article Approximate max-flow min-(multi)cut theorems and their applications Share on Authors: Naveen Garg View Profile , Vijay V. Vazirani View Profile , Mihalis Yannakakis View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 698–707https://doi.org/10.1145/167088.167266Online:01 June 1993Publication History 60citation1,484DownloadsMetricsTotal Citations60Total Downloads1,484Last 12 Months30Last 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

We prove results indicating that it is hard to compute efficiently good approximate solutions to the Graph Coloring, Set Covering and other related minimization problems.Specifically, there is an c >0 such that Graph Coloring cannot be approximated with ratio n' unless P=NP.Set Covering cannot be approximated with ratio clog n for any c < 1/4 unless NP is contained in DTIME[nPOIY log ~].Similar results follow for related problems such as Clique Cover, Fractional Chromatic Number, Dominating Set and others. 1

We address the question of when the structure of a Datalog program with negation guarantees the existence of a fixpoint. We propose a semantics of Datalog programs with negation, which we call the tie–breaking semantics. The tie–breaking semantics can be computed in polynomial time, and results in a fix-point whenever the rule–goal graph of the program has no cycle with an odd number of negative edges. We show that, in some well-defined sense, this is the most general fixpoint semantics of negation possible; in particular we show that if a cycle with an odd number of negative edges is present, then the logic program is not structurally total, that is, it has an alphabetic variant which has no fixpoint semantics whatsoever. Determining whether a program is (nonstructurally) total is undecidable.

In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2–2/k of the optimal cut weight.

We are given a transition system implicitly through a compact representation and wish to perform simultaneously reachability analysis and minimization without constructing first the whole system graph. We present an algorithm for this problem that applies to general systems, provided we have appropriate primitive operations for manipulating blocks of states and we can determine termination; the number of operations needed to construct the minimal reachable graph is quadratic in the size of this graph. We specialize the method to obtain efficient algorithms for extended finite state machines that apply separable affine transformations on the variables.

We show that certain monotonic polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a “Pumping Lemma” for Datalog queries.

Article Free Access Share on Linear approximation of shortest superstrings Authors: Avrim Blum Massachusetts Institute of Technology, Cambridge, MA Massachusetts Institute of Technology, Cambridge, MAView Profile , Tao Jiang McMaster Univ., Hamilton, Ontario, CANADA McMaster Univ., Hamilton, Ontario, CANADAView Profile , Ming Li Univ. of Waterloo, Ontario, CANADA Univ. of Waterloo, Ontario, CANADAView Profile , John Tromp CWI, Amsterdam, The Netherlands CWI, Amsterdam, The NetherlandsView Profile , Mihalis Yannakakis AT&T Bell Labs. Murray Hill, NJ AT&T Bell Labs. Murray Hill, NJView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 328–336https://doi.org/10.1145/103418.103455Published:03 January 1991Publication History 37citation440DownloadsMetricsTotal Citations37Total Downloads440Last 12 Months21Last 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

We consider the average case behavior of onedmensional bin paekmg algorithms in the case where bins have unit capacity and item sizes are chosen according to the ' 'dficrete uniform" distribution U~; k), 1 s j < k, where each item size in the set {llk,21k,..., ji k) has probability 1/j of beiig chosen.Note that for fixed j,k the distributions U{?nj;mk]' approach the continuous distribution U(O, jlk] as m A W, where in U(O, jl k] the item sizes are chosen uniformly horn the half-open interval (O,jik].In this paper, we show that average case behavior can differ substantially under the two types of distributions.We show that for all j, k, j < k-1, there exist on-line algorithms that have constant expected waste under U~; k], whereas no on-line algorithm can have less than C2(n1'2) waste under U(O, U] for any u s 1. Conmariwise, although the First Fit Decreasing (off-line) algorithm has constant expected waste under U(O, u] for all u < 1/2,

Article Testing finite state machines Share on Author: Mihalis Yannakakis AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile , Editor: David Lee AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 476–485https://doi.org/10.1145/103418.103468Online:03 January 1991Publication History 37citation1,310DownloadsMetricsTotal Citations37Total Downloads1,310Last 12 Months13Last 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

Certain problems related to the length of cycles and paths modulo a given integer are studied. Linear-time algorithms are presented that determine whether all cycles in an undirected graph are of length P mod Q and whether all paths between two specified nodes are of length P mod Q , for fixed integers P . Q . These results are compared to those for directed graphs.

Many algorithms for NP-hard optimization problems find solutions that are locally optimal, in the sense that the solutions cannot be improved by a polynomially computable perturbation. Very little is known about the complexity of finding locally optimal solutions, either by local search algorithms or using other indirect methods. Johnson, Papadimitriou, and Yannakakis [J. Comput. System Sci., 37 (1988), pp. 79–100] studied this question by defining a complexity class PLS that captures local search problems. It was proved that finding a partition of a graph that is locally optimal into equal parts with respect to the acclaimed Kernighan-Lin algorithm is PLS-complete. It is shown here that several natural, simple local search problems are PLS-complete, and thus just as hard. Two examples are: finding a partition that cannot be improved by a single swap of two vertices, and finding a stable configuration for an undirected connectionist network. When edges or other objects are unweighted, then a local optimum can always be found in polynomial time. It is shown that the unweighted versions of the local search problems studied in this paper are P-complete.

There is a straightforward algorithm for computing the transitive-closure of an n-node graph in $O(\log ^2 n)$ time on an EREW-PRAM, using $n^3 / \log n$ processors, or indeed with $M(n) / \log n$ processors if serial matrix multiplication in $M(n)$ time can be done. This algorithm is within a log factor of optimal in work (processor-time product), for solving the all-pairs transitive-closure problem for dense graphs. However, this algorithm is far from optimal when either (a) the graph is sparse, or (b) we want to solve the single-source transitive-closure problem. It would be ideal to have an $\mathcal{NC}$ algorithm for transitive-closure that took about e processors for the single-source problem on a graph with n nodes and $e \geqq n$ arcs, or about $en$ processors for the all-pairs problem on the same graph. While an algorithm that good cannot be offered, algorithms with the following performance can be offered. (1) For single-source, $\tilde{O}(n^\varepsilon )$ time with $\tilde O(en^{1 - 2\varepsilon } )$ processors, provided $e > n^{2 - 3\varepsilon } $, and (2) forall-pairs, $\tilde{O}(n^\varepsilon )$ time and $\tilde O(en^{1 - \varepsilon } )$ processors, provided $e \geqq n^{2 - 2\varepsilon } $. Each of these claims assumes that $0 < \varepsilon \leqq \frac{1}{2}$. Importantly, the algorithms are (only) high-probability algorithms; that is, if they find a path, then a path exists, but they may fail to find a path that exists with probability at most $2^{ - \alpha c} $, where $\alpha $ is some positive constant, and c is a multiplier for the time taken by the algorithm. However, it is shown that incorrect results can be detected, thus putting the algorithm in the “Las Vegas” class. Finally, it is shown how to do “breadth-first-search” with the same performance as can be achieved for single-source transitive closure.

Article Free AccessGraph-theoretic methods in database theory Author: Mihalis Yannakakis AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims PODS '90: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsApril 1990 Pages 230–242https://doi.org/10.1145/298514.298576Published:02 April 1990Publication History 146citation2,012DownloadsMetricsTotal Citations146Total Downloads2,012Last 12 Months139Last 6 weeks17 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

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holding s “values” is available, and that s lies between n, the number of nodes of the graph, and e, the number of arcs. The cost measure we use for algorithms is the I/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.

There is a straightforward algorithm for computing the transitive-closure of an n-node graph in $O(\log ^2 n)$ time on an EREW-PRAM, using $n^3 / \log n$ processors, or indeed with $M(n) / \log n$ processors if serial matrix multiplication in $M(n)$ time can be done. This algorithm is within a log factor of optimal in work (processor-time product), for solving the all-pairs transitive-closure problem for dense graphs. However, this algorithm is far from optimal when either (a) the graph is sparse, or (b) we want to solve the single-source transitive-closure problem. It would be ideal to have an $\mathcal{NC}$ algorithm for transitive-closure that took about e processors for the single-source problem on a graph with n nodes and $e \geqq n$ arcs, or about $en$ processors for the all-pairs problem on the same graph. While an algorithm that good cannot be offered, algorithms with the following performance can be offered. (1) For single-source, $\tilde{O}(n^\varepsilon )$ time with $\tilde O(en^{1 - 2\varepsil...

We prove a number of complexity results on the computational paradigm of local optimality.Our main results are these: (a) Finding a local optimum under the Lin-Kernighan heuristic for the traveling salesman problemis PLS-complete.(b) Finding stable configurations in neural networks in the Hopfield mode/is PLS-complete.(c) We show that a host of simple unweighted local optimality problems are P-complete.(d) We introduce a general framework for establishing exponential worstcase bounds for local optimization heuristics.(e)And we show that local search problems become PSPACE-complete if we insist that the local optimum returned be attainable by local improvements from a given initial solution.In [JPY] two problems were shown to be PLScomplete and thus as hard as any problem in PLS; they were a "generic" problem called FLIP, and the problem of finding a local optimum in the Kernighan-Lin heuristic for the graph partitioning problem [KL].

A simple and efficient method for evaluating the performance of an algorithm, rendered as a directed acyclic graph, on any parallel computer is presented. The crucial ingredient is an efficient approximation algorithm for a particular scheduling problem. The only parameter of the parallel computer needed by our method is the message-to-instruction ratio $\tau$. Although the method used in this paper does not take into account the number of processors available, its application to several common algorithms shows that it is surprisingly accurate.

The following issues in computational complexity remain imprecisely understood: The striking difference in the complexities of computing the permanent and determinant of a matrix despite their similar looking formulae, the complexity of checking if a directed graph contains an even length cycle, and the complexity of computing the number of perfect matchings in a graph using Pfaffian orientations. Via polynomial time equivalences, we show inter-relationships among these issues.

The complexity of testing whether a finite-state (sequential or concurrent) probabilistic program satisfies its specification expressed in linear temporal logic. For sequential programs an exponential-time algorithm is given and it is shown that the problem is in PSPACE; this improves the previous upper bound by two exponentials and matches the known lower bound. For concurrent programs is is shown that the problem is complete in double exponential time, improving the previous upper and lower bounds by one exponential each. These questions are also addressed for specifications described by omega -automata or formulas in extended temporal logic.>

We define a natural variant of NP, MAX NP, and also a subclass called MAX SNP. These are classes of optimization problems, and in fact contain several natural, well-studied ones. We show that problems in these classes can be approximated with some bounded error. Furthermore, we show that a number of common optimization problems are complete under a kind of careful transformation (called L-reduction) that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme iff the whole class does. These results may help explain the lack of progress on the approximability of a host of optimization problems.

Article Free Access Share on Towards an architecture-independent analysis of parallel algorithms Authors: Christos Papadimitriou Department of Computer Science and Engineering, University of California at San Diego Department of Computer Science and Engineering, University of California at San DiegoView Profile , Mihalis Yannakakis AT&T Bell Laboratories AT&T Bell LaboratoriesView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 510–513https://doi.org/10.1145/62212.62262Published:01 January 1988Publication History 83citation928DownloadsMetricsTotal Citations83Total Downloads928Last 12 Months81Last 6 weeks28 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

Many combinatorial optimization problems call for the optimization of a linear function over a certain polytope. Typically, these polytopes have an exponential number of facets. We explore the problem of finding small linear programming formulations when one may use any new variables and constraints. We show that expressing the matching and the Traveling Salesman Problem by a symmetric linear program requires exponential size. We relate the minimum size needed by a LP to express a polytope to a combinatorial parameter, point out some connections with communication complexity theory, and examine the vertex packing polytope for some classes of graphs.

We define what it means for a schedule to be reliable, that is, correct in the face of possible transaction failures (assuming that aborting a transaction to restore correctness is not allowed). It turns out that the right definition is recursive, and surprisingly involved. We show that, in fact, testing a schedule for reliability is PSPACE-complete, and thus in some sense even harder than the ordinary NP-complete notions of correctness examined in the past. However, we also prove that all conflict serializable schedules are always reliable, and thus reliability should not be an extra complication for practical concurrency control systems. Finally, we examine two other notions of reliability, related to multiple versions and aborts.

Article Deleting completed transactions Share on Authors: Thanasis Hadzilacos National Technical University of Athens National Technical University of AthensView Profile , Mihalis Yannakakis AT&T Bell Labs AT&T Bell LabsView Profile Authors Info & Claims PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systemsJune 1985 Pages 43–46https://doi.org/10.1145/6012.15402Online:01 June 1985Publication History 9citation206DownloadsMetricsTotal Citations9Total Downloads206Last 12 Months2Last 6 weeks0 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 Free Access Share on The complexity of reliable concurrency control Authors: Christos H. Papadimitriou View Profile , Mihalis Yannakakis View Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985 Pages 230–234https://doi.org/10.1145/325405.325445Online:25 March 1985Publication History 4citation84DownloadsMetricsTotal Citations4Total Downloads84Last 12 Months4Last 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Deadlock-freedom (and saftey) of transactions in a distributed database Authors: Ouri Wolfson Technica, Israel Institute of Technology, Computer Science Dept., Haifa 32000, Israel and AT&T Bell Laboratories, Short Hills, New Jersey Technica, Israel Institute of Technology, Computer Science Dept., Haifa 32000, Israel and AT&T Bell Laboratories, Short Hills, New JerseyView Profile , Mihalis Yannakakis AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985 Pages 105–112https://doi.org/10.1145/325405.325418Published:25 March 1985Publication History 3citation321DownloadsMetricsTotal Citations3Total Downloads321Last 12 Months7Last 6 weeks0 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

An algorithm is presented that finds a min-cut linear arrangement of a tree in O ( n log n ) time. An extension of the algorithm determines the number of pebbles needed to play the black and white pebble game on a tree.

Previous article Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic HypergraphsRobert E. Tarjan and Mihalis YannakakisRobert E. Tarjan and Mihalis Yannakakishttps://doi.org/10.1137/0214020PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs." SIAM Journal on Computing, 14(1), pp. 254–255 Previous article FiguresRelatedReferencesCited ByDetails Learning Hyperedge Replacement Grammars for Graph GenerationIEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 41, No. 3 | 1 Mar 2019 Cross Ref Paired threshold graphsDiscrete Applied Mathematics, Vol. 250 | 1 Dec 2018 Cross Ref Detecting Highly Overlapping Community Structure by Model-based Maximal Clique Expansion2018 IEEE International Conference on Big Data (Big Data) | 1 Dec 2018 Cross Ref Strict chordal and strict split digraphsDiscrete Applied Mathematics, Vol. 216 | 1 Jan 2017 Cross Ref Growing Graphs from Hyperedge Replacement Graph GrammarsProceedings of the 25th ACM International on Conference on Information and Knowledge Management | 24 October 2016 Cross Ref Tree decompositions and social graphsInternet Mathematics, Vol. 12, No. 5 | 16 May 2016 Cross Ref Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland SubgraphsNathan Lindzey and Ross M. McConnellSIAM Journal on Discrete Mathematics, Vol. 30, No. 1 | 12 January 2016AbstractPDF (857 KB)A faster algorithm to recognize even-hole-free graphsJournal of Combinatorial Theory, Series B, Vol. 113 | 1 Jul 2015 Cross Ref Edge deletion problems: Branching facilitated by modular decompositionTheoretical Computer Science, Vol. 573 | 1 Mar 2015 Cross Ref A new augmentation based algorithm for extracting maximal chordal subgraphsJournal of Parallel and Distributed Computing, Vol. 76 | 1 Feb 2015 Cross Ref A New Class of Lineage Expressions over Probabilistic Databases Computable in P-TimeScalable Uncertainty Management | 1 Jan 2013 Cross Ref On Finding Tucker Submatrices and Lekkerkerker-Boland SubgraphsGraph-Theoretic Concepts in Computer Science | 1 Jan 2013 Cross Ref BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSESDiscrete Mathematics, Algorithms and Applications, Vol. 04, No. 01 | 13 April 2012 Cross Ref On $3$-Colorable $P_5$-Free GraphsFrédéric Maffray and Grégory MorelSIAM Journal on Discrete Mathematics, Vol. 26, No. 4 | 27 November 2012AbstractPDF (1151 KB)Certifying algorithmsComputer Science Review, Vol. 5, No. 2 | 1 May 2011 Cross Ref A Novel Branching Strategy for Parameterized Graph Modification ProblemsCombinatorial Optimization and Applications | 1 Jan 2010 Cross Ref Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphsDiscrete Applied Mathematics, Vol. 157, No. 15 | 1 Aug 2009 Cross Ref Polarity of chordal graphsDiscrete Applied Mathematics, Vol. 156, No. 13 | 1 Jul 2008 Cross Ref A Fixed-Parameter Tractable Approach for the Wavelength Assignment Problem in Transparent NetworksIEEE Communications Letters, Vol. 12, No. 7 | 1 Jul 2008 Cross Ref Two fixed-parameter algorithms for Vertex Covering by Paths on TreesInformation Processing Letters, Vol. 106, No. 2 | 1 Apr 2008 Cross Ref Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic EncodingsLogic for Programming, Artificial Intelligence, and Reasoning | 1 Jan 2008 Cross Ref A Fixed-Parameter Tractable Algorithm for the Wavelength Assignment in WDM Mesh Networks2008 IEEE International Conference on Communications | 1 Jan 2008 Cross Ref Advances in Register Allocation TechniquesThe Compiler Design Handbook | 7 December 2009 Cross Ref Certifying Algorithms for Recognizing Interval Graphs and Permutation GraphsDieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, and Jeremy P. SpinradSIAM Journal on Computing, Vol. 36, No. 2 | 17 February 2012AbstractPDF (253 KB)Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc GraphsGraph-Theoretic Concepts in Computer Science | 1 Jan 2006 Cross Ref On Split-Coloring ProblemsJournal of Combinatorial Optimization, Vol. 10, No. 3 | 1 Nov 2005 Cross Ref Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval BigraphsPavol Hell and Jing HuangSIAM Journal on Discrete Mathematics, Vol. 18, No. 3 | 1 August 2006AbstractPDF (199 KB)Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval GraphsHaim Kaplan, Ron Shamir, and Robert E. TarjanSIAM Journal on Computing, Vol. 28, No. 5 | 28 July 2006AbstractPDF (361 KB)Minimal elimination ordering inside a given chordal graphGraph-Theoretic Concepts in Computer Science | 17 June 2005 Cross Ref Fixed-parameter tractability of graph modification problems for hereditary propertiesInformation Processing Letters, Vol. 58, No. 4 | 1 May 1996 Cross Ref Parallel computation of perfect elimination schemes using partition techniques on triangulated graphsComputers & Mathematics with Applications, Vol. 29, No. 6 | 1 Mar 1995 Cross Ref An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graphTheoretical Computer Science, Vol. 134, No. 2 | 1 Nov 1994 Cross Ref An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph30th Annual Symposium on Foundations of Computer Science | 1 Jan 1989 Cross Ref Doubly Lexical Orderings of MatricesAnna LubiwSIAM Journal on Computing, Vol. 16, No. 5 | 31 July 2006AbstractPDF (3081 KB)Tractability of parameterized completion problems on chordal and interval graphs: minimum fill-in and physical mappingProceedings 35th Annual Symposium on Foundations of Computer Science Cross Ref Volume 14, Issue 1| 1985SIAM Journal on Computing1-255 History Submitted:29 May 1984Published online:13 July 2006 InformationCopyright © 1985 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0214020Article page range:pp. 254-255ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

Article Free Access Share on Querying weak instances Author: Mihalis Yannakakis AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims PODS '84: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systemsApril 1984 Pages 275–280https://doi.org/10.1145/588011.588051Online:02 April 1984Publication History 2citation146DownloadsMetricsTotal Citations2Total Downloads146Last 12 Months2Last 6 weeks0 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

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with πk-formula of size n for which every σk-formula has size exp ω(n1/(k−1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a σk-formula of size exp o(n1/(k−1)). Thus our hierarchy theorem is the best possible.

The power of locking as a primitive for controlling concurrency in database systems is examined.It is accepted that the concurrent execution (or schedule) of different transactions must be serializable; that is, it must behave like a serial schedule, one in which the transactions run one at a time.It is shown that locking cannot achieve the full power of serializability.An exact characterization of the schedules that can be produced if locking is used to control concurrency is given for two versions of serializability.In the first one, state serializabdity, only the effect of the schedule on the database is taken into account.In the second one, vww serializability, the view of the data received by the transactions is also taken into account.We show that it is possible to determine efficiently whether the transactions in a given set can be permitted to run safely by themselves without the need of any control while ensuring view serializability, although the problem is NP-complete in the case of state serializability.

Chordal graphs arise naturally in the study of Gaussian elimination on sparse symmetric matrices; acyclic hypergraphs arise in the study of relational data bases. Rose, Tarjan and Lueker [SIAM J. Comput., 5 (1976), pp. 266–283] have given a linear-time algorithm to test whether a graph is chordal, which Yannakakis has modified to test whether a hypergraph is acyclic. Here we develop a simplified linear-time test for graph chordality and hypergraph acyclicity. The test uses a new kind of graph (and hypergraph) search, which we call maximum cardinality search A variant of the method gives a way to selectively reduce acyclic hypergraphs, which is needed for evaluating queries in acyclic relational data bases.

An algorithm is presented which finds a min-cut linear arrangement of a tree in O(nlogn) time. An extension of the algorithm determines the number of pebbles needed to play the black and white pebble game on a tree.

Several papers have recently dealt with techniques for proving area-time lower bounds for VLSI computation by “crossing sequence” methods. A number of natural questions are raised by these definitions.

A class of database schemes, called acychc, was recently introduced.It is shown that this class has a number of desirable properties.In particular, several desirable properties that have been studied by other researchers m very different terms are all shown to be eqmvalent to acydicity.In addition, several equivalent charactenzauons of the class m terms of graphs and hypergraphs are given, and a smaple algorithm for determining acychclty is presented.Also given are several eqmvalent characterizations of those sets M of multivalued dependencies such that M is the set of muRlvalued dependencies that are the consequences of a given join dependency.Several characterizations for a conflict-free (in the sense of Lien) set of muluvalued dependencies are provided.

Template dependencies (TD’s) are a class of data dependencies that include multivalued and join dependencies and embedded versions of these. A collection of techniques, examples and results about TD’s are presented. The principal results are: 1) Finite implication (implication over relations with a finite number of tuples) is distinct from unrestricted implication for TD’s. 2) There are, for TD’s over three or more attributes, infinite chains of increasingly weaker and increasingly stronger full TD’s. 3) However, there are weakest (nontrivial) and strongest full TD’s over any given set of attributes. 4) Over two attributes, there are only three distinct TD’s. 5) There is no weakest (not necessarily full) TD over any set of three or more attributes. 6) There is a finite relation that obeys every strictly partial TD but no full TD. 7) The conjunction of each finite set of full TD’s is equivalent to a single full TD. However, the conjunction of a finite set of (not necessarily full) TD’s is not necessarily equivalent to a single TD and the disjunction of a finite set of full TD’s is not necessarily equivalent to a single TD. 8) There is a finite set of TD’s with an infinite Armstrong relation but no finite Armstrong relation. 9) A necessary and sufficient condition for the existence of finite Armstrong relations for sets of TD’s can be formulated in terms of the implication structure of TD’s.

Article Free Access Share on Independent database schemas Authors: Marc H. Graham University of Toronto, Toronto, Canada University of Toronto, Toronto, CanadaSearch about this author , Mihalis Yannakakis Bell Laboratories, Murray Hill, N.J. Bell Laboratories, Murray Hill, N.J.Search about this author Authors Info & Claims PODS '82: Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1982Pages 199–204https://doi.org/10.1145/588111.588144Published:29 March 1982Publication History 12citation246DownloadsMetricsTotal Citations12Total Downloads246Last 12 Months6Last 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 SiteeReaderPDF

Many important combinatorial optimization problems, including the traveling salesman problem (TSP), the clique problem and many others, call for the optimization of a linear functional over some discrete set of vectors.

The complexity of the foUowmg class of problems Is investigated: Given a distance matrix, fred the shortest spanning tree that is isomorphic to a given prototype.Several classical combinatorial problems, both easy and hard, fall into this category for an appropriate choice of the family of prototypes, for example, taking the family to be the set of all paths gives the traveling salesman problem or taking the family to be the set of all 2-stars gives the weighted matching problem It is shown that the complexity of these problems depends explicitly on the rate of growth of a sLmple parameter of the family of prototypes.

When several transacuons access (read and update) the same database concurrently, there must be some kind of coordmauon to ensure that all transacuons receive a consistent view of the data Such coordination is usually achieved by locking the transactions according to some locking policy A locking policy that guarantees the preservation of consistency of the database is called safe Necessary and sufficient conditions are found for a locking pohcy to be safe, but it is shown that in general it is NPcomplete to test for these conditions.However, when the database has a given structure, a simple set of rules which is sufficient for safety and, moreover, necessary for a wide class of natural locking pohcles is developed Categories and SubJect Descriptors DA I [Operating Systems] Process Management--concurrency, H 2 2 [Database Management] Physical Design--deadlock avoMance General Terms.Theory

The usual method for preserving the consistency of a database when accessed (read and updated) concurrently by several transactions, is by locking the transactions according to some locking policy; a locking policy that guarantees the preservation of consistency of the database is called safe. Furthermore, if no deadlocks can arise the policy is called deadlock-free. In this paper we are concerned with the freedom from deadlock of safe locking policies. We show that a simple extension of the DAG policy of [Y] is the most general safe and deadlock-free policy for a pair of transactions. We prove however, that it is NP-complete to test whether a set of transactions is not deadlock-free even for the simplest kind of transactions, those that are two-phase locked [E]. We show that for the natural class of safe locking policies, the L-policies, studied in [Y], freedom from deadlock is determined only by the order in which entities are accessed by the transactions and not by the way in which safety is ensured. As a consequence of this fact we develop simple conditions that guarantee the freedom from deadlock of a safe L-policy.

There is a class of database descriptions, involving one “acyclic” join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. Further, this class has many desirable properties. Some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. Other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. It is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. This paper is intended to summarize the results that will appear in more detail in [FMU] and [BFMY].

Our aim in this paper is to show that there is a mathematically inherent reason why existing systems enforce D-serializability (rather than just because of its simplicity): it is because they are based on locking. Our main result is a characterization of the power of locking which states that if a locking policy is safe then it must allow only D-serializable schedules. Furthermore any such schedule can be produced by some safe locking policy.

It iS shown that testing whether a dependency o is unpiled by a set ~ of functional and join dependencies is NP-hard if o is a join dependency, but it reqmres only O(l u Ill ~ II) time ff o Is either a funcuonal or a multivalued dependency ( j U [ is the number of elements in the set of all the attributes U, and II ~ II as the space required to write down ~).The fact that inferring join dependencies is NP-hard follows from the followmg stronger result.It is proved that if ~ is a set of one jom dependency and several funcuonal dependencies, then testing whether Z implies a join dependency o is NP-complete By combming this result with a recent result of Beeri and Var& ~t can be proved that if 2 is a set of one join dependency and several multivalued dependencies, then testing whether ~ unphes a join dependency o Is NP-hard It is also shown that the problem of deciding whether a JD-rule can be applied to a tableau T and the problem of testing whether a relation r does not obey a join dependency are NP-complete.The first problem is NP-complete even if T can be obtamed from a tableau corresponding to a join dependency by applying some FD-rules.As a result, It follows that deciding whether the join of several relations obtained by projecUon from a umversal instance is not equal to the universal instance is NP-complete.Finally, it is proved that there is no umversal constant n such that for every set of multlvalued dependencies ~ and a join dependency o that is not unpiled by ~, there is a relation with no more than n tuples in which holds but o fails.

If $\pi $ is a property on graphs or digraphs, the edge-deletion problem can be stated as follows: find the minimum number of edges whose deletion results in a subgraph (or subdigraph) satisfying property $\pi $. Several well-studied graph problems can be formulated as edge-deletion problems. In this paper we show that the edge-deletion problem is NP-complete for the following properties: (1) without cycles of specified length l, or of any length $ \leqq l$, (2) connected and degree-constrained, (3) outerplanar, (4) transitive digraph, (5) line-invertible, (6) bipartite, (7) transitively orientable. For problems (5), (6), (7) we determine the best possible bounds on the node-degrees for which the problems remain NP-complete.

A set of problems which has attracted considerable interest recently is the set of node-deletion problems. The general node-deletion problem can be stated as follows: Given a graph, find the minimum number of nodes whose deletion results in a subgraph satisfying property $\pi $. In [LY] this problem was shown to be NP-complete for a large class of properties (the class of properties that are hereditary on induced subgraphs) using a small number of reduction schemes from the node cover problem. Since the node cover problem becomes polynomial on bipartite graphs, it might be hoped that this is the case with other node-deletion problems too. In this paper we characterize those properties for which the bipartite restriction of the node-deletion problem is polynomial and those for which it remains NP-complete. Similar results follow for analogous problems on other structures such as families of sets, hypergraphs and 0,1 matrices. For example, in the case of matrices, our result states that if M is a class of 0,1 matrices which is closed under permutation and deletion of rows and columns, then finding the largest submatrix in M of a matrix is polynomial if the matrices of M have bounded rank and NP-complete otherwise.

We examine the class of matrices that satisfy Commoner's sufficient condition for total unimodularity [C], which we call restricted totally unimodular (RTUM). We show that a matrix is RTUM if and only if it can be decomposed in a very simple way into the incidence matrices (or their transposes) of bipartite graphs or directed graphs, and give a linear time algorithm to perform this task. Based on this decomposition, we show that the 0,1 Integer Programming Problem with an RTUM matrix of constraints has the same time complexity as the b-matching and the max flow problems.

We propose a new kind of data dependencies called algebraic dependencies, which generalize all previous known kinds. We give a complete axiomatization of algebraic dependencies in terms of simple algebraic rewriting rules. In the process we characterize exactly the expressive power of tableaux, thus solving an open problem of Aho, Sagiv and Ullman; we show that it is NP-complete to tell whether a tableau is realizable by an expression; and we give an interesting dual interpretation of the chase procedure. We also show that algebraic dependencies over a language augmented to contain union and set difference can express arbitrary domain-independent predicates of finite index over finite relations. The class of embedded implicational dependencies recently - and independently - introduced by Fagin is shown to coincide with our algebraic dependencies. Based on this, we give a simple proof of Fagin's Armstrong relation theorem.

Queries in relational databases can be formulated in terms of relational expressions using the relational operations select, project, join, union, and difference The equivalence problem for these queries is studied with query optimization m mind It ts shown that testmg eqmvalence of relational expressions with the operators select, project, join, and union is complete m the class FIt of the polynomial-time hierarchy A nonprocedural representation for queries formulated by these expressions is proposed This method of query representation can be viewed as a generahzatlon of tableaux or conjunctive queries (which are used to represent expressions with only select, project, and join) Furthermore, this method is extended to queries formulated by relatmnal expressions that also contain the difference operator, provided that the project operator is not applied to subexpresstons with the difference operator A procedure for testing eqmvalence of these queries is given It ts shown that testmg containment of tableaux is a necessary step in testing equivalence of queries with union and difference Three important cases m which containment of tableaux can be tested m polynomial time are described, although the containment problem is shown to be NP-complete even for tableaux that correspond to expressions with only one project and several join operators

Using a pair of finite-state automata to model the transmitter-receiver protocol in a data communications system, we derive lower bounds on the size of automata needed to achieve reliable communication across an error-phone channel. We also show that, at the cost of increasing the size of the automata, a transmission rate close to the theoretical maximum can be achieved.

article Free Access Share on The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems Author: Mihalis Yannakakis Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ and Princeton University, Princeton, New Jersey Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ and Princeton University, Princeton, New JerseyView Profile Authors Info & Claims Journal of the ACMVolume 26Issue 4Oct. 1979 pp 618–630https://doi.org/10.1145/322154.322157Published:01 October 1979Publication History 45citation611DownloadsMetricsTotal Citations45Total Downloads611Last 12 Months32Last 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We show that unit execution time jobs subject to a precedence constraint whose complement is chordal can be scheduled in linear time on m processors. Generalizations to arbitrary execution times are NP-complete.

If π is a graph property, the general node(edge) deletion problem can be stated as follows: Find the minimum number of nodes(edges), whose deletion results in a subgraph satisfying property π. In this paper we show that if π belongs to a rather broad class of properties (the class of properties that are hereditary on induced subgraphs) then the node-deletion problem is NP-complete, and the same is true for several restrictions of it. For the same class of properties, requiring the remaining graph to be connected does not change the NP-complete status of the problem; moreover for a certain subclass, finding any "reasonable" approximation is also NP-complete. Edge-deletion problems seem to be less amenable to such generalizations. We show however that for several common properties (e.g. planar, outer-planar, line-graph, transitive digraph) the edge-deletion problem is NP-complete.