Hybrid switching for data center networks (DCN) has received considerable research attention recently. A hybrid-switched DCN employs a much faster circuit switch that is reconfigurable with a nontrivial cost, and a much slower packet switch, to interconnect its racks of servers. The research problem is, given a traffic demand (between the racks), how to properly schedule the circuit switch so that it removes most of the traffic demand, leaving little for the slower packet switch to handle. All existing solutions make a convenient but unnecessarily restrictive assumption that when the circuit switch changes from one configuration to another, all input ports have to stop data transmission during the reconfiguration period. However, the circuit switch can usually readily support partial reconfiguration in the following sense: Only the input ports affected by the reconfiguration need to pay a reconfiguration delay, while unaffected input ports can continue to transmit data during the reconfiguration. In this work, we propose BFF (best first fit), the first solution to exploit this partial reconfigurability in hybrid-switched DCNs. BFF not only significantly outperforms but also has much lower computational complexity than the state of the art solutions that do not exploit this partial reconfigurability.

In this work, we study a challenging research problem that arises in minimizing the cost of storing customer data online for reliable access in a cloud. It is how to near-perfectly balance the remaining capacities of all disks across the cloud system while adding new file blocks so that the inevitable event of capacity expansion can be postponed as much as possible. The challenges of solving this problem are twofold. First, new file blocks are added to the cloud concurrently by many dispatchers (computing servers) that have no communication or coordination among themselves. Though each dispatcher is updated with information on disk occupancies, the update is infrequent and not synchronized. Second, for fault-tolerance purposes, a combinatorial constraint has to be satisfied in distributing the blocks of each new file across the cloud system. We propose a randomized algorithm, in which each dispatcher independently samples a blocks-to-disks assignment according to a probability distribution on a set of assignments conforming to the aforementioned combinatorial requirement. We show that this algorithm allows a cloud system to near-perfectly balance the remaining disk capacities as rapidly as theoretically possible, when starting from any unbalanced state that is correctable mathematically.

We strengthen the nondeterministic hierarchy theorem for non-deterministic polynomial time to show that the lower bound holds against sub-linear advice. More formally, we show that for any constants d and d' such that 1 <= d < d', and for any time-constructible bound t=o(n^d), there is a language in NTIME(n^d) which is not in NTIME(t)/n^{1/d'}. The best known earlier separation of Fortnow, Santhanam and Trevisan could only handle o(log(n)) bits of advice in the lower bound, and was not tight with respect to the time bounds. We generalize our hierarchy theorem to work for other syntactic complexity measures between polynomial time and polynomial space, including alternating polynomial time with any fixed number of alternations. We also use our technique to derive an almost-everywhere hierarchy theorem for non-deterministic classes which use a sub-linear amount of non-determinism, i.e., the lower bound holds on all but finitely many input lengths rather than just on infinitely many. As one application of our main result, we derive a new lower bound for NP against NP-uniform non-deterministic circuits of size O(n^k) for any fixed k. This result is a significant strengthening of a result of Kannan, which states that not all of NP can be solved with P-uniform circuits of size O(n^k) for any fixed k. As another application, we show strong non-uniform lower bounds for the complexity class RE of languages decidable in randomized linear exponential time with one sided error.

In this work, we study a challenging research problem that arises in minimizing the cost of storing customer data online for reliable accesses in a cloud. It is how to near-perfectly balance the remaining capacities of all disks across the cloud system while adding new file blocks so that the inevitable event of capacity expansion can be postponed as much as possible. The challenges of solving this problem are twofold. First, new file blocks are added to the cloud concurrently by many dispatchers (computing servers) that have no communication or coordination among themselves. Though each dispatcher is updated with information on disk occupancies, the update is infrequent and not synchronized. Second, for fault-tolerance purposes, a combinatorial constraint has to be satisfied in distributing the blocks of each new file across the cloud system. We propose a randomized algorithm, in which each dispatcher independently samples a blocks-to-disks assignment according to a probability distribution on a set of assignments conforming to the aforementioned combinatorial requirement. We show that this algorithm allows a cloud system to near-perfectly balance the remaining disk capacities as rapidly as theoretically possible, when starting from any unbalanced state that is correctable mathematically.

Given samples from two distributions over an n -element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in n , specifically, O ( n 2/3 ε −8/3 log n ), independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than { ε 4/3 n −1/3 /32, εn −1/2 /4}) or large (more than ε ) in ℓ 1 distance. This result can be compared to the lower bound of Ω ( n 2/3 ε −2/3 ) for this problem given by Valiant [2008]. Our algorithm has applications to the problem of testing whether a given Markov process is rapidly mixing. We present sublinear algorithms for several variants of this problem as well.

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time- bounded Kolmogorov complexity and traditional Kolmogorov complexity. We show unconditionally how to probabilistically find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumption though fails if BPP = FewP = EXP. We also show that assuming good pseudorandom generators one cannot increase the depth of a string efficiently.

Abstract The Church-Turing thesis has stood the test of time, capturing computation models Turing could not have conceived of, including digital computation, probabilistic, parallel and quantum computers and the Internet. The thesis has become accepted doctrine in computer science and the ACM has named its highest honor after Turing. Many now view computation as a fundamental part of nature, like atoms or the integers.

We consider a repeated Matching Pennies game in which players have limited access to randomness. Playing the (unique) Nash equilibrium in this n-stage game requires n random bits. Can there be Nash equilibria (or epsilon-Nash equilibria) that use less than n random coins?

In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings R_K. It was previously known that PSPACE, and hence BPP is Turing-reducible to R_K. The earlier proof relied on the adaptivity of the Turing-reduction to find a Kolmogorov-random string of polynomial length using the set R_K as oracle. Our new non-adaptive result relies on a new fundamental fact about the set R_K, namely each initial segment of the characteristic sequence of R_K has high Kolmogorov complexity. As a partial converse to our claim we show that strings of very high Kolmogorov-complexity when used as advice are not much more useful than randomly chosen strings.

This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2(n k))-inseparable. We also relate these conditions to strong hypotheses concerning randomness and genericity of disjoint pairs.

The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P≠UP and TFNP NP functions are not computable in polynomial-time with an NP oracle.

Under a standard hardness assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all polynomial-time samplable distributions. More precisely we show that if exponential time is not infinitely often in subexponential space, then the following are equivalent for any algorithm A: (1) For all P-samplable distributions mu, A runs in time polynomial on mu-average. (2) For all polynomial p, the running time for A is bounded by 2O(Kp(x)-K(x)+log(|x|))for all inputs x. where K(x) is the Kolmogorov complexity (size of smallest program generating x) and Kp(x) is the size of the smallest program generating x within time p(|x|). To prove this result we show that, under the hardness assumption, the polynomial-time Kolmogorov distribution, mp(x) = 2-Kp(x), is universal among the P-samplable distributions.

In 1982, Kannan showed that SigmaP2does not have nk-sized circuits for any k. Do smaller classes also admit such circuit lower bounds? Despite several improvements of Kannan's result, we still cannot prove that PNPdoes not have linear size circuits. Work of Aaronson and Wigderson provides strong evidence - the "algebrization'' barrier - that current techniques have inherent limitations in this respect. We explore questions about fixed-polynomial size circuit lower bounds around and beyond the algebrization barrier. We find several connections, including 1) The following are equivalent: -NP is in SIZE(nk) (has O(nk)-size circuit families) for some k -For each c, PNP[nc]is in SIZE(nk) for some k -ONP/1 is in SIZE(nk) for some k, where ONP is the class of languages accepted obliviously by NP machines, with witnesses for "yes" instances depending only on the input length. 2) For a large number of natural classes C and all k ges C is in SIZE(nk) if and only if C/1 cap P/poly is in SIZE(nk). 3) If there is a d such that MATIME(n) sube NTIME(nd), then PNPdoes not have O(nk) size circuits for any k > 0. 4) One cannot show n2-size circuit lower bounds for oplusP without new nonrelativizing techniques. In particular, the proof that PP nsube SIZE(nk) for all k relies on the (relativizing) result that PPPsube MA rArr PP nsube SIZE(nk), and we give an oracle relative to which PoplusPsube MA and oplusP sube SIZE(n2) both hold.

We exhibit a new computational-based definition of awareness, informally that our level of unawareness of an object is the amount of time needed to generate that object within a certain environment. We give several examples to show this notion matches our intuition in scenarios where one organizes, accesses and transfers information. We also give a formal process-independent definition of awareness based on Levin's universal enumeration.

Tennenholtz (GEB 2004) developed Program Equilibrium to model play in a finite two-player game where each player can base their strategy on the other player's strategies. Tennenholtz's model allowed each player to produce a "loop-free" computer program that had access to the code for both players. He showed a folk theorem where the result of any mixed-strategy individually rational play could be an equilibrium payoff in this model even in a one-shot game. Kalai et al. gave a general folk theorem for correlated play in a more generic commitment model.

We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our goal is to implicitly maintain correct LMSR prices across an exponentially large outcome space. We examine both permutation combinatorics, where outcomes are permutations of objects, and Boolean combinatorics, where outcomes are combinations of binary events. We look at three restrictive languages that limit what traders can bet on. Even with severely limited languages, we find that LMSR pricing is #P-hard, even when the same language admits polynomial-time matching without the market maker. We then propose an approximation technique for pricing permutation markets based on an algorithm for online permutation learning. The connections we draw between LMSR pricing and the literature on online learning with expert advice may be of independent interest.

Consider a weather forecaster predicting the probability of rain for the next day. We consider tests that given a finite sequence of forecast predictions and outcomes will either pass or fail the forecaster. It is known that any test which passes a forecaster who knows the distribution of nature can also be probabilistically passed by a forecaster with no knowledge of future events. This note summarizes and examines the computational complexity of such forecasters.

The OR-SAT problem asks, given Boolean formulae Φ1,...,Φm each of size at most n, whether at least one of the Φi's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n, unless NP ⊆ coNP/poly, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et. al. [4] and Harnik and Naor [15] and has a number of implications. A number of parametric $\NP$ problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless NP ⊆ coNP/poly. Satisfiability does not have PCPs of size polynomial in the number of variables unless NP ⊆ coNP/poly. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (Buhrman-Hitchcock) There are no subexponential-size hard sets for NP unless NP is in co-NP/poly. We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis, and discuss how it relates to traditional derandomization assumptions.

We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j) = C(i,j). We complement the known EXP-hardness of computing the exact value of a succinct zero-sum game by several results on approximating the value. (1) We prove that approximating the value of a succinct zero-sum game to within an additive error is complete for the class promise- $$S^{p}_{2}$$ , the “promise” version of $$S^{p}_{2}$$ . To the best of our knowledge, it is the first natural problem shown complete for this class. (2) We describe a ZPP NP algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct zero-sum game. As a corollary, we obtain, in a uniform fashion, several complexity-theoretic results, e.g., a ZPP NP algorithm for learning circuits for SAT (Bshouty et al., JCSS, 1996) and a recent result by Cai (JCSS, 2007) that $$S^{p}_{2} \subseteq$$ ZPP NP . (3) We observe that approximating the value of a succinct zero-sum game to within a multiplicative factor is in PSPACE, and that it cannot be in promise- $$S^{p}_{2}$$ unless the polynomial-time hierarchy collapses. Thus, under a reasonable complexity-theoretic assumption, multiplicative-factor approximation of succinct zero-sum games is strictly harder than additive-error approximation.

A language L has a property tester if there exists a probabilistic algorithm that given an input x queries only a small number of bits of x and distinguishes the cases as to whether x is in L and x has large Hamming distance from all y in L. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.

We consider a permutation betting scenario, where people wager on the final ordering of n candidates: for example, the outcome of a horse race. We examine the auctioneer problem of risklessly matching up wagers or, equivalently, finding arbitrage opportunities among the proposed wagers. Requiring bidders to explicitly list the orderings that they'd like to bet on is both unnatural and intractable, because the number of orderings is n! and the number of subsets of orderings is 2n!. We propose two expressive betting languages that seem natural for bidders, and examine the computational complexity of the auctioneer problem in each case. Subset betting allows traders to bet either that a candidate will end up ranked among some subset of positions in the final ordering, for example, "horse A will finish in positions 4, 9, or 13-21", or that a position will be taken by some subset of candidates, for example "horse A, B, or D will finish in position 2". For subset betting, we show that the auctioneer problem can be solved in polynomial time if orders are divisible. Pair betting allows traders to bet on whether one candidate will end up ranked higher than another candidate, for example "horse A will beat horse B". We prove that the auctioneer problem becomes NP-hard for pair betting. We identify a sufficient condition for the existence of a pair betting match that can be verified in polynomial time. We also show that a natural greedy algorithm gives a poor approximation for indivisible orders.

Abstract A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is a k(n)-enumerator if for every input x of length n. h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A.

A set A is autoreducible if one can compute, for all x, the value $A(x)$ by querying A only at places $y \neq x$. Furthermore, A is infinitely‐often autoreducible if, for infinitely many x, the value $A(x)$ can be computed by querying A only at places $y \neq x$. For all other x, the computation outputs a special symbol to signal that the reduction is undefined. It is shown that for polynomial time Turing and truth‐table autoreducibility there are A, B, C in the class EXP of all exponential‐time computable sets such that A is not infinitely‐often Turing autoreducible, B is Turing autoreducible but not infinitely‐often truth‐table autoreducible and C is truth‐table autoreducible with $g(n)+1$ queries but not infinitely‐often Turing autoreducible with $g(n)$ queries. Here n is the length of the input, g is nondecreasing, and there exists a polynomial p such that $p(n)$ bounds both the computation time and the value of g at input of length n. Furthermore, connections between notions of infinitely‐often autoreducibility and notions of approximability are investigated. The Hausdorff‐dimension of the class of sets which are not infinitely‐often autoreducible is shown to be 1.

A property tester with high probability accepts inputs satisfying a given property and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We construct two properties of binary functions for which there exists a test making a constant number of queries, but yet there exists no such tolerant test. The first construction uses Hadamard codes and long codes. Then, using probabilistically checkable proofs of proximity as constructed by Ben-Sasson et. al., we exhibit a property which has constant query intolerant testers but for which any tolerant tester requires n/sup /spl Omega/(1)/ queries.

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP /spl sube/ NP/log if and only if EXP = P/sub /spl par///sup NP/ Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in P/sub /spl par///sup NP/ implies EXP in NP/poly.

Shortly after Steve Cook and Richard Karp showed the ex-istence of many natural NP-complete languages, researchers started to realize the great importance of the P versus NP problem and the difficulty of settling it. One graduate student at the Massachusetts Institute of Technology started to look beyond NP, asking what problems have a higher complexity and how do we classify them. Larry Stockmeyer discovered an amazing structure of complexity classes that continues to direct the research in complexity to this day. Stockmeyer passed away on July 31, 2004 at the age of 55 and in this paper we review some of his research and the legacy he has left on the community.

We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(na)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all common semantic time classes including RTIME, NTIME ∩ coNTIME, UTIME, MATIME, AMTIME and BQTIME.We show a stronger hierarchy for RTIME: For every constant c, RP/1 is not contained in RTIME(nc)/(log n)1/2c. To prove this result we first prove a similar statement for NP by building on Zák's proof of the nondeterministic time hierarchy.

We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic random-access Turing machine can solve satisfiability in time n c and space n d , where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than √2.Our lower bounds apply to nondeterministic linear time and almost all natural NP-complete problems known. In fact, they even apply to the class of languages that can be solved on a nondeterministic machine in linear time and space n 1/c .Our proofs follow the paradigm of indirect diagonalization. We also use that paradigm to prove time-space lower bounds for languages higher up in the polynomial-time hierarchy.

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.

We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for all real numbers 1 /spl les/ /spl alpha/ /spl les/ /spl beta/, BPTIME(n/sup /spl alpha//)/l /spl sube/ BPTIME(n/sup /spl beta//)/l. This result builds on and improves an earlier hierarchy of Barak using O(log log n) bits of advice. We also show that for any constant d > 0, there is a language L computable on average in BPP but not on average in BPTIME (n/sup d/). We build on Barak's techniques by using a different translation argument and by a careful application of the fact that there is a PSPACE-complete problem L such that worst-case probabilistic algorithms for L take only slightly more time than average-case algorithms.

We consider the question whether there exists a set A such that every set polynomial-time Turing equivalent to A is also many-one equivalent to A. We show that if E=NE then no sparse set has this property. We give the first relativized world where there exists a set with this property, and in this world the set A is sparse.

We show that if SAT does not have small circuits, then there must exist a small number of formulas such that every small circuit fails to compute satisfiability correctly on at least one of these formulas. We use this result to show that if P/sup NP[1]/=P/sup NP[2]/, then the polynomial-time hierarchy collapses to S/sub 2//sup P//spl sube//spl Sigma//sub 2//sup p//spl cap//spl Pi//sub 2//sup p/. Even showing that the hierarchy collapsed to /spl Sigma//sub 2//sup p/ remained open.

According to economic theory supported by empirical and laboratory evidence, the equilibrium price of a financial security reflects all of the information regarding the security's value. We investigate the computational process on the path toward equilibrium, where information distributed among traders is revealed step-by-step over time and incorporated into the market price. We develop a simplified model of an information market, along with trading strategies, in order to formalize the computational properties of the process. We show that securities whose payoffs cannot be expressed as weighted threshold functions of distributed input bits are not guaranteed to converge to the proper equilibrium predicted by economic theory. On the other hand, securities whose payoffs are threshold functions are guaranteed to converge, for all prior probability distributions. Moreover, these threshold securities converge in at most $n$ rounds, where $n$ is the number of bits of distributed information. We also prove a lower bound, showing a type of threshold security that requires at least $n/2$ rounds to converge in the worst case.

We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling securities---which can be thought of as betting on or against a particular future outcome---allows agents both to hedge risk and to profit (in expectation) on subjective predictions. A compound securities market allows agents to place bets on arbitrary boolean combinations of events, enabling them to more closely achieve their optimal risk exposure, and enabling the market as a whole to more closely achieve the social optimum.The tradeoff for allowing such expressivity is in the complexity of the agents' and auctioneer's optimization problems.We develop and motivate the concept of a compound securities market, presenting the framework through a series of formal definitions and examples. We then analyze in detail the auctioneer's matching problem. We show that, with numevents events, the matching problem is co-NP-complete in the divisible case and complete in the indivisible case. We show that the latter hardness result holds even under severe language restrictions on bids. With events, and numevents securities, the problem is polynomial in the divisible case and NP-complete in the indivisible case. We briefly discuss matching algorithms and tractable special cases.

Summary form only given. We describe several trends in the history of computational complexity, including: the early history of complexity; the development of NP-completeness and the structure of complexity classes; how randomness, parallelism and quantum mechanics has forced us to reexamine our notions of efficient computation and how computational complexity has responded to these new models; the meteoric rise and fall of circuit complexity; and the marriage of complexity and cryptography and how research on a cryptographic model led to limitations of approximation.

Introduces computational depth, a measure for the amount of "non-random" or "useful" information in a string, by considering the difference of various Kolmogorov complexity measures. We investigate three instantiations of computational depth: (1) basic computational depth, a clean notion capturing the spirit of C.H. Bennett's (1988) logical depth; (2) time-t computational depth and the resulting concept of shallow sets, a generalization of sparse and random sets based on low depth properties of their characteristic sequences (we show that every computable set that is reducible to a shallow set has polynomial-size circuits); and (3) distinguishing computational depth, measuring when strings are easier to recognize than to produce (we show that if a Boolean formula has a non-negligible fraction of its satisfying assignments with low depth, then we can find a satisfying assignment efficiently).

Most of the hypotheses of full derandomization fall into two sets of equivalent statements: those equivalent to the existence of efficient pseudorandom generators and those equivalent to approximating the accepting probability of a circuit. We give the first relativized world where these sets of equivalent statements are not equivalent to each other.

Given access to independent samples of a distribution A over [n] /spl times/ [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i.e., whether A is /spl epsi/-close in the L/sub 1/ norm to the product distribution A/sub 1//spl times/A/sub 2/ for some distributions A/sub 1/ over [n] and A/sub 2/ over [m]. The sample complexity of our test is O/spl tilde/(n/sup 2/3/m/sup 1/3/poly(/spl epsi//sup -1/)), assuming without loss of generality that m/spl les/n. We also give a matching lower bound, up to poly (log n, /spl epsi//sup -1/) factors. Furthermore, given access to samples of a distribution X over [n], we show how to test if X is /spl epsi/-close in L/sub 1/ norm to an explicitly specified distribution Y. Our test uses O/spl tilde/(n/sup 1/2/poly(/spl epsi//sup -1/)) samples, which nearly matches the known tight bounds for the case when Y is uniform.

Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and effort required to sequence the DNA in the missing gaps. This procedure has been used in a number of microbial sequencing projects including Streptococcus pneumoniae and other bacteria. In this paper we describe a theoretical framework for this problem and propose an improved method that guarantees to minimize the number of steps involved in the gap closure procedures. In given particular collection of n/2 DNA fragments we describe a strategy that requires. 0.75 log n work in eight parallel rounds of experiment closely matching a corresponding lower bound 0.5 log of n

We take a fresh look at CD complexity, where CD t (x) is the size of the smallest program that distinguishes x from all other strings in time t(|x|). We also look at CND complexity, a new nondeterministic variant of CD complexity, and time-bounded Kolmogorov complexity, denoted by C complexity. We show several results relating time-bounded C, CD, and CND complexity and their applications to a variety of questions in computational complexity theory, including the following: Showing how to approximate the size of a set using CD complexity without using the random string as needed in Sipser's earlier proof of a similar result. Also, we give a new simpler proof of this result of Sipser's. Improving these bounds for almost all strings, using extractors. A proof of the Valiant--Vazirani lemma directly from Sipser's earlier CD lemma. A relativized lower bound for CND complexity. Exact characterizations of equivalences between C, CD, and CND complexity. Showing that satisfying assignments of a satisfiable Boolean formula can be enumerated in time polynomial in the size of the output if and only if a unique assignment can be found quickly. This answers an open question of Papadimitriou. A new Kolmogorov complexity-based proof that BPP\subseteq\Sigma_2^p$. New Kolmogorov complexity based constructions of the following relativized worlds: There exists an infinite set in P with no sparse infinite NP subsets. EXP=NEXP but there exists a NEXP machine whose accepting paths cannot be found in exponential time. Satisfying assignments cannot be found with nonadaptive queries to SAT.

We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time n/sup 1.618/ and space n/sup o(1)/. This improves recent results of Fortnow and of Lipton and Viglas. In general, for any constant a less than the golden ratio, we prove that satisfiability cannot be solved in time n/sup a/ and space n/sup /spl delta// for some positive constant b. Our techniques allow us to establish this result for b< 1/2 (/spl alpha/+2/a(2)-a). We can do better for a close to the golden ratio, for example, satisfiability cannot be solved by a random-access Turing machine using n/sup 1.46/ time and n/sup .11/ space. We also show tradeoffs for nondeterministic linear time computations using sublinear space. For example, there exists a language computable in nondeterministic linear time and n/sup 619/ space that cannot be computed in deterministic n/sup 1.618/ time and n/sup o(1)/ space. Higher up the polynomial-time hierarchy we can get better bounds. We show that linear-time /spl Sigma//sub l/-computations require essentially n/sup l/ time on deterministic machines that use only n/sup o(1)/ space. We also show new lower bounds on conondeterministic versus nondeterministic computation.

Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n/sup 2/3//spl epsiv//sup -4/ log n) independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than max(/spl epsiv//sup 2//32/sup 3//spl radic/n,/spl epsiv//4/spl radic/n=)) or large (more than /spl epsiv/) in L/sub 1/-distance. We also give an /spl Omega/(n/sup 2/3//spl epsiv//sup -2/3/) lower bound. Our algorithm has applications to the problem of checking whether a given Markov process is rapidly mixing. We develop sublinear algorithms for this problem as well.

A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from exponential space by showing that all Turing complete sets for certain levels of the exponential-time hierarchy are autoreducible but there exists some Turing complete set for doubly exponential space that is not. Although we already knew how to separate these classes using diagonalization, our proofs separate classes solely by showing they have different structural properties, thus applying Post's program to complexity theory. We feel such techniques may prove unknown separations in the future. In particular, if we could settle the question as to whether all Turing complete sets for doubly exponential time are autoreducible, we would separate either polynomial time from polynomial space, and nondeterministic logarithmic space from nondeterministic polynomial time, or else the polynomial-time hierarchy from exponential time. We also look at the autoreducibility of complete sets under nonadaptive, bounded query, probabilistic, and nonuniform reductions. We show how settling some of these autoreducibility questions will also lead to new complexity class separations.

We consider the question whether two queries to SAT are as powerful as one query. We show that if P/sup NP[1]/=P/sup NP[2]/ then; locally either NP=coNP or NP has polynomial-size circuits; P/sup NP/=P/sup NP[1]/; /spl Sigma//sub 2//sup p/=UP/sup NP[1]//spl cap/RP/sup NP[1]/; PH=BPP/sup NP[1]/. Moreover we extend work of E. Hemaspaandra et al. (1997) to show that if P(/spl Sigma//sub 2//sup p/[1])=P(/spl Sigma//sub 2//sup p/[2]) then /spl Sigma//sub 2//sup p/=/spl Pi//sub 2//sup p/. We also give a relativized world where P/sup NP[1]/=P/sup NP[2]/ but NP/spl ne/coNP.

We show that MA/sub EXP/, the exponential time version of the Merlin-Arthur class, does not have polynomial size circuits. This significantly improves the previous known result due to Kannan since we furthermore show that our result does not relativize. This is the first separation result in complexity theory that does not relativize. As a corollary to our separation result we also obtain that PEXP, the exponential time version of PP is nor in P/poly.

Ladner (1975) showed that there are no minimal recursive sets under polynomial-time reductions. Given any recursive set A, Ladner constructs a set B such that B strictly reduces to A but B does not lie in P. The set B does have very long sequences of input lengths of easily computable instances. We examine whether Ladner's results hold if we restrict ourselves to "uniformly hard languages" which have no long sequences of easily computable instances. Under a hard to disprove assumption, we show that there exists a minimal recursive uniformly hard set under honest many-one polynomial-time reductions.

Theorem 1.3There exists a relativized world where we can detect unique solutions for NP problems yet P # NP.

A language is L-printable if there is a logspace algorithm which, on input 1 n , prints all members in the language of length n. Following the work of Allender and Rubinstein [SIAM J. Comput., 17 (1988), pp. 1193--1202] on P-printable sets, we present some simple properties of the L-printable sets. This definition of "L-printable" is robust and allows us to give alternate characterizations of the L-printable sets in terms of tally sets and Kolmogorov complexity. In addition, we show that a regular or context-free language is L-printable if and only if it is sparse, and we investigate the relationship between L-printable sets, L-rankable sets (i.e., sets A having a logspace algorithm that, on input x, outputs the number of elements of A that precede x in the standard lexicographic ordering of strings), and the sparse sets in L. We prove that under reasonable complexity-theoretic assumptions, these three classes of sets are all different. We also show that the class of sets of small generalized Kolmogorov space complexity is exactly the class of sets that are L-isomorphic to tally languages.

We consider the following six hypotheses: *P=NP. *SAT is truth-table reducible to a P-selective set. *SAT is truth-table reducible to a k-approximable set for some k. *FP/sub /spl par///sup NP/=FP/sup NP[log]/ *SAT is O(log n)-approximable. *Solving SAT is in P on formulae with at most one assignment. We discuss their importance and relationships among them.

We give the first nontrivial model-independent time-space tradeoffs for satisfiability. Namely, we show that SAT cannot be solved simultaneously in n/sup 1+0(1)/ time and n/sup 1-/spl epsiv// space for any /spl epsiv/>0 on general random-access nondeterministic Turing machines. We also give several other related results. Our proof uses two basic ideas. First we show that if SAT can be solved nondeterministically with a small amount of space then we can collapse a nonconstant number of levels of the polynomial-time hierarchy. Next we extend work of V. Nepomnjascii (1970) to show that a nondeterministic computation of super linear time and sublinear space can be simulated in alternating linear time. Combining these facts with simple diagonalization yields our main result. We discuss how these bounds lead to a new approach to separating the complexity classes NL and NP. We give some possibilities and limitations of this approach.

In this paper, we give an oracle under which BPP is equal to probabilistic linear time, an unusual collapse of a complexity time hierarchy. In addition, we also give oracles where DP2 is contained in probabilistic linear time and where BPP has linear sized circuits, as well as oracles for the negation of these questions. This indicates that these questions will not be solved by techniques that relativize. Finally, we note that probabilistic linear time can not contain both NP and BPP, implying that there are languages solvable by interactive proof systems that can not be solved in probabilistic linear time.

We address two questions about self-reducibility-the power of adaptiveness in examiners that take advice and the relationship between random-self-reducibility and self-correctability. We first show that adaptive examiners are more powerful than nonadaptive examiners, even if the nonadaptive ones are nonuniform. Blum et al. (1993) showed that every random-self-reducible function is self-correctable. However, whether self-correctability implies random-self-reducibility is unknown. We show that, under a reasonable complexity hypothesis, there exists a self-correctable function that is not random-self-reducible. For P-sampleable distributions, however, we show that constructing a self-correctable function that is not random-self-reducible is as hard as proving that P/spl ne/PP.

We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including: One can find accepting paths of nondeterministic polynomial-time Turing machines that accept /spl Sigma/*. Every total multivalued nondeterministic function has a polynomial-time computable refinement. One can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. One can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse, path, etc.

Properties of L-printable sets are considered, and it is shown that two sets A and B that are L-printable and have similar density are L-isomorphic. L-printable sets are characterized as those sets L-isomorphic to tally sets in L, and as subsets of KS[k log n, k log n]. Several classes of L-printable sets are given, including sparse regular and context-free sets; a characterization of sparse regular sets is given. The relationship of the sparse sets in L to the sparse L-rank able and L-printable sets is considered, and strong indications are given that these classes are all different. An oracle is constructed relative to which there are sparse L-rankable sets that are in L and not L-printable, and L-rankable sets of similar density that are not L-isomorphic.

Beigel, Reingold, and Spielman (J. Comput. System Sci.50, 191–202 (1995)) showed that PP is closed under intersection and a variety of special cases of polynomial-time truth-table closure. We extend their techniques to show that PP is closed under general polynomial-time truth-table reductions. We also show that PP is closed under constant-round truth-table reductions.

The authors introduce symmetric perfect generic sets. These sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. We then show that the Berman–Hartmanis isomorphism conjecture holds relative to any sp-generic oracle, i.e., for any symmetric perfect generic set A, all ${\bf NP}^A $-complete sets are polynomial-time isomorphic relative to A. Prior to this work, there were no known oracles relative to which the isomorphism conjecture held. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets, it is also shown that ${\bf P} = {textbf{Few}}{\bf P}^{\bf A} $ for any symmetric perfect generic A.

A language is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate exponential space from doubly exponential space by showing that all Turing complete sets for exponential space are autoreducible but there exists some Turing complete set for doubly exponential space that is not. We immediately also get a separation of logarithmic space from polynomial space. Although we already know how to separate these classes using diagonalization, our proofs separate classes solely by showing they have different structural properties, thus applying Post's Program (E. Pos, 1944) to complexity theory. We feel such techniques may prove unknown separations in the future. In particular if we could settle the question as to whether all complete sets for doubly exponential time were autoreducible we would separate polynomial time from either logarithmic space or polynomial space. We also show several other theorems about autoreducibility.

We examine questions of optimality and domination in repeated stage games where one or both players may draw their strategies only from (perhaps different ) computationally bounded sets.We also consider optimality and domination when bounded convergence rates of the infinite payoff.We develop a notion of a "grace period" to handle the problem of vengeful strategies.

This paper generalizes the previous formal definitions of random-self-reducibility. It is shown that, even under a very general definition, sets that are complete for any level of the polynomial hierarchy are not nonadaptively random-self-reducible, unless the hierarchy collapses. In particular, NP-complete sets are not nonadaptively random-self-reducible, unless the hierarchy collapses at the third level. By contrast, we show that sets complete for the classes PP and ${\text{MOD}}_m {\text{P}}$ are random-self-reducible.

Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-learnable by an inductive inference machine with oracle A. A and F are EX-equivalent if EX[A] = EX[B]. The equivalence classes induced are the degrees of inferability. We prove several results about these degrees: (1) There are an uncountable number of degrees. (2) For A r.e., REC e BC[A] iff O'' ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T B iff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).

The authors introduce symmetric perfect generic sets. these sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. They then show that the Berman-Hartmanis (1977) isomorphism conjecture holds relative to any sp-generic oracle, i.e., for any symmetric perfect generic set A, all NP/sup A/-complete sets are polynomial-time isomorphic relative to A. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets they also show that P/sup A/=FewP/sup A/ for any symmetric perfect generic/sup /A.>

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

. Motivated by Manuel Blum's concept of instance checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof protocols [LFKN92], [Sha92], and especially the MIP = NEXP protocol from [BFL91]. We show that every nondeterministic computational task S(x; y), defined as a polynomial time relation between the instance x, representing the input and output combined, and the witness y can be modified to a task S 0 such that: (i) the same instances remain accepted; (ii) each instance/witness pair becomes checkable in polylogarithmic Monte Carlo time; and (iii) a witness satisfying S 0 can be computed in polynomial time from a witness satisfying S. Here the instance and the description of S have to be provided in error-correcting code (since the checker will not notice slight changes). A modification of the MIP proof was required to achieve polynomial time in (iii); the earlier technique yields N O(log log N)...

Hash P functions are characterized by certain straight-line programs of multivariate polynomials. The power of this characterization is illustrated by a number of consequences. These include a somewhat simplified proof of S. Toda's (1989) theorem that PH contained in P/sup Hash P/, as well as an infinite class of potentially inequivalent checkable functions.>

The exact power of two-prover interactive proof systems (MIP) introduced by M. Ben-Or et al. (Proc. 20th Symp. on Theory of Computing, 1988, p.113-31) is determined. In this system, two all-powerful noncommunicating provers convince a randomizing polynomial-time verifier in polynomial time that the input x belongs to the language L. It was previously suspected (and proved in a relativized sense) that coNP-complete languages do not admit such proof systems. In sharp contrast, it is shown that the class of languages having two-prover interactive proof systems is computable in nondeterministic exponential time (NEXP). This represents a further step demonstrating the unexpectedly immense power for randomization and interaction in efficient provability.>

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

A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof system, its complement has a short interactive protocol. This result implies that there are not any perfect zero-knowledge protocols for NP-complete languages unless the polynomial time hierarchy collapses. This paper demonstrates that knowledge complexity can be used to show that a language is easy to prove.