Search

We show that there are planar graphs that require four pages in any book embedding., To be published in Journal of Combinatorial Theory, Series B

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic max(min) polynomial equations, referred to as maxPPSs (and minPPSs, respectively), 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 establish this result using a generalization of Newton's method which applies to maxPPSs and minPPSs, even though the underlying functions are only piecewise-differentiable. This generalizes our recent work which provided a P-time algorithm for purely probabilistic PPSs. These equations form the Bellman optimality equations for several important classes of infinite-state Markov Decision Processes (MDPs). Thus, as a corollary, we obtain the first polynomial time algorithms for computing to within arbitrary desired precision the optimal value vector for several classes of infinite-state MDPs which arise as extensions of classic, and heavily studied, purely stochastic processes. These include both the problem of maximizing and mininizing the termination (extinction) probability of multi-type branching MDPs, stochastic context-free MDPs, and 1-exit Recursive MDPs. Furthermore, we also show that we can compute in P-time an epsilon-optimal policy for both maximizing and minimizing branching, context-free, and 1-exit-Recursive MDPs, for any given desired epsilon > 0. This is despite the fact that actually computing optimal strategies is Sqrt-Sum-hard and PosSLP-hard in this setting. We also derive, as an easy consequence of these results, an FNP upper bound on the complexity of computing the value (within arbitrary desired precision) of branching simple stochastic games (BSSGs).

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.

The paper Structure and Complexity of Bag Consistency by Albert Atserias and Phokion Kolaitis [1] studies fundamental structural and algorithmic questions on the global consistency of databases in the context of bag semantics. A collection D of relations is called globally consistent if there is a (so-called "universal") relation over all the attributes that appear in all the relations of D whose projections yield the relations in D. The basic algorithmic problem for consistency is: given a database D, determine whether D is globally consistent. An obvious necessary condition for global consistency is local (or pairwise) consistency: every pair of relations in D must be consistent. This condition is not sufficient however: It is possible that every pair is consistent, but there is no single global relation over all the attributes whose projections yield the relations in D. A natural structural question is: Which database schemas have the property that every locally consistent database over the schema is also globally consistent?

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.

We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most $\smash{\phi n^{O(\sqrt{\log n})}}$, where $n$ is the number of nodes in the graph and $\phi$ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of $\phi n^{O(\log n)}$ by Etscheid and R\"{o}glin. 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 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.

This paper focuses on joint cyber and physical attacks on power grids and presents methods to retrieve the grid state information following such an attack. We consider a model where 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 linearized power flow model 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 and numerically demonstrate its performance on real power grids.

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.) 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 multi-type branching processes and stochastic context-free grammars.

We study the complexity of a class of Markov decision processes and, more generally, stochastic games, called 1-exit Recursive Markov Decision Processes (1-RMDPs) and 1-exit Recursive Simple Stochastic Games (1-RSSGs), with strictly positive rewards. These are a class of finitely presented countable-state zero-sum turn-based stochastic games that subsume standard finite-state MDPs and Condon's simple stochastic games. They correspond to optimization and game versions of several classic stochastic models, with rewards. In particular, they correspond to the MDP and game versions of multi-type branching processes and stochastic context-free grammars with strictly positive rewards. The goal of the two players in the game is to maximize/minimize the total expected reward generated by a play of the game. Such stochastic models arise naturally as models of probabilistic procedural programs with recursion, and the problems we address are motivated by the goal of analyzing the optimal/pessimal expected running time in such a setting. We first show that in such games both players have optimal deterministic “stackless and memoryless” optimal strategies. We then provide polynomial-time algorithms for computing the exact optimal expected reward (which may be infinite, but is otherwise rational), and optimal strategies, for both the maximizing and minimizing single-player versions of the game, i.e., for (1-exit) Recursive Markov Decision Processes (1-RMDPs). It follows that the quantitative decision problem for positive reward 1-RSSGs is in NP ∩ coNP. We show that Condon's well-known quantitative termination problem for finite-state simple stochastic games (SSGs) which she showed to be in NP ∩ coNP reduces to a special case of the reward problem for 1-RSSGs, namely, deciding whether the value is ∞. By contrast, for finite-state SSGs with strictly positive rewards, deciding if this expected reward value is ∞ is solvable in P-time. We also show that there is a simultaneous strategy improvement algorithm that converges in a finite number of steps to the value and optimal strategies of a 1-RSSG with positive rewards.

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., Comment: 47 pages, full version of SODA 2010 paper

We give polynomial time algorithms for quantitative (and qualitative) reachability analysis for Branching Markov Decision Processes (BMDPs). Specifically, given a BMDP, and given an initial population, where the objective of the controller is to maximize (or minimize) the probability of eventually reaching a population that contains an object of a desired (or undesired) type, we give algorithms for approximating the supremum (infimum) reachability probability, within desired precision ϵ > 0 , in time polynomial in the encoding size of the BMDP and in log ⁡ ( 1 / ϵ ) . We furthermore give P-time algorithms for computing ϵ-optimal strategies for both maximization and minimization of reachability probabilities. We also give P-time algorithms for all associated qualitative analysis problems, namely: deciding whether the optimal (supremum or infimum) reachability probabilities are 0 or 1. Prior to this paper, approximation of optimal reachability probabilities for BMDPs was not even known to be decidable. Our algorithms exploit the following basic fact: we show that for any BMDP, its maximum (minimum) non-reachability probabilities are given by the greatest fixed point (GFP) solution g ⁎ ∈ [ 0 , 1 ] n of a corresponding monotone max (min) Probabilistic Polynomial System of equations (max/minPPS), x = P ( x ) , which are the Bellman optimality equations for a BMDP with non-reachability objectives. We show how to compute the GFP of max/minPPSs to desired precision in P-time. We also study more general branching simple stochastic games (BSSGs) with (non-)reachability objectives. We show that: (1) the value of these games is captured by the GFP, g ⁎ , of a corresponding max-minPPS, x = P ( x ) ; (2) the quantitative problem of approximating the value is in TFNP; and (3) the qualitative problems associated with the value are all solvable in P-time.

This paper studies the problem of passive grasp stability under an external disturbance, that is, the ability of a grasp to resist a disturbance through passive responses at the contacts. To obtain physically consistent results, such a model must account for friction phenomena at each contact; the difficulty is that friction forces depend in non-linear fashion on contact behavior (stick or slip). We develop the first polynomial-time algorithm which either solves such complex equilibrium constraints for two-dimensional grasps, or otherwise concludes that no solution exists. To achieve this, we show that the number of possible `slip states' (where each contact is labeled as either sticking or slipping) that must be considered is polynomial (in fact quadratic) in the number of contacts, and not exponential as previously thought. Our algorithm captures passive response behaviors at each contact, while accounting for constraints on friction forces such as the maximum dissipation principle., Comment: Robotics: Science and Systems June 26-30, 2018 (9 pages, 7 figures)

We study cyber attacks on power grids that affect both the physical infrastructure and the data at the control center? which therefore are cyber-physical in nature. In particular, we assume that an adversary attacks an area by: (i) remotely disconnecting some lines within the attacked area, and (ii) modifying the information received from the attacked area to mask the line failures and hide the attacked area from the control center. For the latter, we consider two types of attacks: (i) data distortion: which distorts the data by adding powerful noise to the actual data, and (ii) data replay: which replays a locally consistent old data instead of the actual data. We use the DC power flow model and prove that the problem of finding the set of line failures given the phase angles of the nodes outside of the attacked area is strongly NP-hard, even when the attacked area is known. However, we introduce the polynomial time REcurrent Attack Containment and deTection (REACT) Algorithm to approximately detect the attacked area and line failures after a cyber-physical attack.

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 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.

Motivated by the recent cyber attack on the Ukrainian power grid, we study cyber attacks on power grids that affect both the physical infrastructure and the data at the control center–which therefore are cyber-physical in nature. In particular, we assume that an adversary attacks an area by: (i) remotely disconnecting some lines within the attacked area, and (ii) modifying the information received from the attacked area to mask the line failures and hide the attacked area from the control center. For the latter, we consider two types of attacks: (i) data distortion: which distorts the data by adding powerful noise to the actual data, and (ii) data replay: which replays a locally consistent old data instead of the actual data. We use the DC power flow model and prove that the problem of finding the set of line failures given the phase angles of the nodes outside of the attacked area is strongly NP-hard, even when the attacked area is known. However, we introduce the polynomial time REcurrent Attack Containment and deTection (REACT) Algorithm to approximately detect the attacked area and line failures after a cyber-physical attack. We numerically show that it performs well in detecting the attacked area, and detecting single, double, and triple line failures in small and large attacked areas.

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.

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.

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.

We begin by observing that (discrete-time) Quasi-Birth-Death Processes (QBDs) are equivalent, in a precise sense, to probabilistic 1-Counter Automata (p1CAs), and both Tree-Like QBDs (TL-QBDs) and Tree-Structured QBDs (TS-QBDs) are equivalent to both probabilistic Pushdown Systems (pPDSs) and Recursive Markov Chains (RMCs). We then proceed to exploit these connections to obtain a number of new algorithmic upper and lower bounds for central computational problems about these models. Our main result is this: for an arbitrary QBD, we can approximate its termination probabilities (i.e., its $G$ matrix) to within $i$ bits of precision (i.e., within additive error $1/2^i$), in time polynomial in \underline{both} the encoding size of the QBD and in $i$, in the unit-cost rational arithmetic RAM model of computation. Specifically, we show that a decomposed Newton's method can be used to achieve this. We emphasize that this bound is very different from the well-known ``linear/quadratic convergence'' of numerical analysis, known for QBDs and TL-QBDs, which typically gives no constructive bound in terms of the encoding size of the system being solved. In fact, we observe (based on recent results) that for the more general TL-QBDs such a polynomial upper bound on Newton's method fails badly. Our upper bound proof for QBDs combines several ingredients: a detailed analysis of the structure of 1-counter automata, an iterative application of a classic condition number bound for errors in linear systems, and a very recent constructive bound on the performance of Newton's method for strongly connected monotone systems of polynomial equations. We show that the quantitative termination decision problem for QBDs (namely, ``is $G_{u,v} \geq 1/2$?'') is at least as hard as long standing open problems in the complexity of exact numerical computation, specifically the square-root sum problem. On the other hand, it follows from our earlier results for RMCs that any non-trivial approximation of termination probabilities for TL-QBDs is sqrt-root-sum-hard.

We show that there is no discrete-time price-adjustment mechanism (any process that at each period looks at the history of prices and excess demands and updates the prices) such that for any market (a set of goods and consumers with endowments and strictly concave utilities) the price-adjustment mechanism will achieve excess demands that are at most an ϵ fraction of the total supply within a number of periods that is polynomial in the number of goods and . This holds even if one restricts markets so that excess demand functions are differentiable with derivatives bounded by a small constant. For the convergence time to the actual price equilibrium, we show by a different method a stronger result: Even in the case of three goods with a unique price equilibrium, there is no function of ϵ that bounds the number of periods needed by a price-adjustment mechanism to arrive at a set of prices that is ϵ -close to the equilibrium.

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.

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

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 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 give polynomial time algorithms for quantitative and qualitative reachability analysis for Branching Markov Decision Processes BMDPs. Specifically, given a BMDP, and given an initial population, where the objective of the controller is to maximize or minimize the probability of eventually reaching a population that contains an object of a desired or undesired type, we give algorithms for approximating the supremum infimum reachability probability, within desired precision $$\epsilon > 0$$, in time polynomial in the encoding size of the BMDP and in $$\log 1/\epsilon $$. We furthermore give P-time algorithms for computing $$\epsilon $$-optimal strategies for both maximization and minimization of reachability probabilities. We also give P-time algorithms for all associated qualitative analysis problems, namely: deciding whether the optimal supremum or infimum reachability probabilities are 0 or 1. Prior to this paper, approximation of optimal reachability probabilities for BMDPs was not even known to be decidable. Our algorithms exploit the following basic fact: we show that for any BMDP, its maximum minimum non-reachability probabilities are given by the greatest fixed point GFP solution $$g^* \in [0,1]^n$$ of a corresponding monotone max min Probabilistic Polynomial System of equations max/min-PPS, $$x=Px$$, which are the Bellman optimality equations for a BMDP with non-reachability objectives. We show how to compute the GFP of max/min PPSs to desired precision in P-time.

We consider the case where inconsistencies are present between a system and its corresponding model, used for automatic verification. Such inconsistencies can be the result of modeling errors or recent modifications of the system. Despite such discrepancies, we can still attempt to perform automatic verification. In fact, as we show, we can sometimes exploit the verification results to assist in automatically learning the required updates to the model. In a related previous work, we have suggested the idea of black box checking, where verification starts without any model, and the model is obtained while repeated verification attempts are performed. Under the current assumptions, an existing inaccurate (but not completely obsolete) model is used to expedite the updates. We use techniques from black box testing and machine learning. We present an implementation of the proposed methodology called AMC (for Adaptive Model Checking). We discuss some experimental results, comparing various tactics of updating a model while trying to perform model checking.

Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in Papadimitriou and Yannakakis [On the approximability of trade-offs and optimal access of web sources, in: Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000] that there exist polynomial size e approximations for any e > 0, and that under certain general conditions, such approximate e-Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an e-Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax e to any e' > e, then we can efficiently construct an e'-curve that uses no more points than the smallest e-curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger e value. We present an algorithm that is 4-competitive for any e' > (1 + e)2 - 1. We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax e by an arbitrary constant.

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.

Scenario-based specifications such as message sequence charts (MSC) offer an intuitive and visual way to describe design requirements. MSC-graphs allow convenient expression of multiple scenarios, and can be viewed as an early model of the system that can be subjected to a variety of analyses. Problems such as LTL model checking are undecidable for MSC-graphs in general, but are known to be decidable for the class of bounded MSC-graphs.Our first set of results concerns checking realizability of bounded MSC-graphs. An MSC-graph is realizable if there is a distributed implementation that generates precisely the behaviors in the graph. There are two notions of realizability, weak and safe, depending on whether or not we require the implementation to be deadlock-free. It is known that for a finite set of MSCs, weak realizability is coNP-complete while safe realizability has a polynomial-time solution. We establish that for bounded MSC-graphs, weak realizability is, surprisingly, undecidable, while safe realizability is in EXPSPACE.Our second set of results concerns verification of MSC-graphs. While checking properties of a graph G, besides verifying all the scenarios in the set L(G) of MSCs specified by G, it is desirable to verify all the scenarios in the set Lw(G)—the closure of G, that contains the implied scenarios that any distributed implementation of G must include. For checking whether a given MSC M is a possible behavior, checking M∈L(G) is NP-complete, but checking M∈Lw(G) has a quadratic solution. For temporal logic specifications, considering the closure makes the verification problem harder: while checking LTL properties of L(G) is PSPACE-complete for bounded graphs G, checking even simple “local” properties of Lw(G) is undecidable.

A (2 - 2/k) approximation algorithm is presented for the node multiway cut problem, thus matching the result of Dahlhaus et al. (SIAM J. Comput. 23 (4) (1994) 864-894) for the edge version of this problem. This is done by showing that the associated LP-relaxation always has a half-integral optimal solution.

We consider the one-dimensional bin packing problem under the discrete uniform distributions $U\{j,k\}$, $1 \leq j \leq k-1$, in which the bin capacity is $k$ and item sizes are chosen uniformly from the set $\{1,2,\ldots,j\}$. Note that for $0 < u = j/k \leq 1$ this is a discrete version of the previously studied continuous uniform distribution $U(0,u]$, where the bin capacity is 1 and item sizes are chosen uniformly from the interval $(0,u]$. We show that the average-case performance of heuristics can differ substantially between the two types of distributions. In particular, there is an online algorithm that has constant expected wasted space under $U\{j,k\}$ for any $j,k$ with $1 \leq j < k-1$, whereas no online algorithm can have $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 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 also survey other recent results comparing the behavior of heuristics under discrete and continuous uniform distributions.

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.

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 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

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. On the positive side, we show that this exponential dependence can be avoided for the extension of acyclic queries with ≠ (but not

We study the maximum integral multicommodity flow problem and the minimum multicut problem restricted to trees. This restriction is quite rich and contains as special cases classical optimization problems such as matching and vertex cover for general graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut problem are NP-hard and MAX SNP-hard on trees, although the maximum integral flow can be computed in polynomial time if the edges have unit capacity. We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most twice the value of the flow. This gives a 2-approximation algorithm for minimum multicut and a 1/2-approximation algorithm for maximum integral multicommodity flow in trees.

We address the problem of performing simultaneously reachability analysis and minimization of real-time transition systems represented by timed automata, i.e., automata extended with a finite set of clock variables. The transitions of the automaton may depend on the values of the clocks and may reset some of the clocks. An efficient algorithm is presented for minimizing a system with respect to a given initial partition that respects the enabling conditions of the transitions of the timed automaton. Our algorithm generates the portion of the minimized system that is reachable from a given initial configuration in time polynomial in the input and the size of the minimal reachable system.

The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently, via arithmetic circuits using only multiplication and division gates, and integer inputs. Input instance: Four lists of positive integers: a 1,..., an ∈N+ n ; b 1,..., bn ∈N+ n ; c 1,..., cm ∈N+ m ; d 1, ..., dm ∈N+ m ; where each of the integers is represented in binary. Problem 1 (equality testing): Decide whether a 1 b 1 a 2 b 2⋯ anbn = c 1 d 1 c 2 d 2⋯ cmdm . Problem 2 (inequality testing): Decide whether a 1 b 1 a 2 b 2⋯ anbn ≥ c 1 d 1 c 2 d 2⋯ cmdm . Problem 1 is easily decidable in polynomial time using a simple iterative algorithm. Problem 2 is much harder. We observe that the complexity of Problem 2 is intimately connected to deep conjectures and results in number theory. In particular, if a refined form of the ABC conjecture formulated by Baker in 1998 holds, or if the older Lang-Waldschmidt conjecture (formulated in 1978) on linear forms in logarithms holds, then Problem 2 is decidable in P-time (in the standard Turing model of computation). Moreover, it follows from the best available quantitative bounds on linear forms in logarithms, namely, by Baker and Wüstholz [1993] or Matveev [2000], that if m and n are fixed universal constants then Problem 2 is decidable in P-time (without relying on any conjectures). This latter fact was observed earlier by Shub [1993]. We describe one application: P-time maximum probability parsing for arbitrary stochastic context-free grammars (where ε -rules are allowed).

We study the problem of computing the probability that a given stochastic context-free grammar (SCFG), G, generates a string in a given regular language L(D) (given by a DFA, D). This basic problem has a number of applications in statistical natural language processing, and it is also a key necessary step towards quantitative ω-regular model checking of stochastic context-free processes (equivalently, 1-exit recursive Markov chains, or stateless probabilistic pushdown processes). We show that the probability that G generates a string in L(D) can be computed to within arbitrary desired precision in polynomial time (in the standard Turing model of computation), under a rather mild assumption about the SCFG, G, and with no extra assumption about D. We show that this assumption is satisfied for SCFG's whose rule probabilities are learned via the well-known inside-outside (EM) algorithm for maximum-likelihood estimation (a standard method for constructing SCFGs in statistical NLP and biological sequence analysis). Thus, for these SCFGs the algorithm always runs in P-time.

A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multi-type 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 by Etessami and Yannakakis [11] that a decomposed variant of Newton's method converges monotonically to the LFP solution for any MPS that has a non-negative solution. Subsequently, Esparza, Kiefer, and Luttenberger [7] 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 ([10, 9]). However, prior to this paper, 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 paper we provide worst-case upper bounds, as a function of both the input encoding size |P|, and e>0, on the number of iterations required for decomposed Newton's method (even with rounding) to converge to within additive error e>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.

Boolean programs are a popular abstract domain for static-analysis-based software model checking. Yet little is known about the complexity of model checking for this model of computation. This paper aims to fill this void by providing a comprehensive study of the worst-case complexity of several basic analyses of Boolean programs, including reachability analysis, cycle detection, LTL, CTL, and CTL* model checking. We present algorithms for these problems and show that our algorithms are all optimal by providing matching lower bounds. We also identify particular classes of Boolean programs which are easier to analyse, and compare our results to prior work on pushdown model checking.

We characterize precisely the complexity of several natural computational problems in NP, which have been proposed but not categorized satisfactorily in the literature: Computing the Vapnik–Chervonenkis dimension of a 0–1 matrix; finding the minimum dominating set of a tournament; satisfying a Boolean expression by perturbing the default truth assignment; and several others. These problems can be solved innO(logn)time, and thus, they are probably not NP-complete. We define two new complexity classes between P and NP, very much in the spirit of MAXNP and MAXSNP. We show that computing the V–C dimension is complete for the more general class, while the other two problems are complete for the weaker class.

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.