On the Complexity of 2-Monotone Restarting Automata

The -automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jančar et al. to model the so-called analysis by reduction. Here it is shown that the class ℒ(R) of languages that are accepted by -automata is incomparable under set inclusion to the class of Church-Rosser languages and to the class of growing context-sensitive languages. In fact this already holds for the class of languages that are accepted by 2-monotone -automata. In addition, we prove that already the latter class contains -complete languages, showing that already the 2-monotone -automaton has a surprisingly large expressive power. The results of this paper have been announced at DLT 2004 in Auckland, New Zealand. This work was mainly carried out while T. Jurdziński was visiting the University of Kassel, supported by a grant from the Deutsche Forschungsgemeinschaft (DFG). F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by the program ‘Information Society’ under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University in Prague under Grant-No. 358/2006/A-INF/MFF.     

Two Algorithms in Search of a Type-System

The authors’ programming formalism is a version of call-by-value under a complexity-theoretically motivated type system. programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are -definable ( types are confined to levels 0, 1, and 2). A limitation of the original version of is that the only directly expressible recursions are tail-recursions. Here we extend so that a broad range of affine recursions are directly expressible. In particular, the revised can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper’s main work is in refining the original time-complexity semantics for to show that these new recursion schemes do not lead out of the realm of feasibility.     

Feasible Operations on Proofs: The Logic of Proofs for Bounded Arithmetic

This paper presents a semantics for the logic of proofs in which all the operations on proofs are realized by feasibly computable functions. More precisely, we will show that the completeness of for the semantics of proofs of Peano Arithmetic extends to the semantics of proofs in Buss’ bounded arithmetic . In view of applications in epistemology of in particular and justification logics in general this result shows that explicit knowledge in the propositional framework can be made computationally feasible. This research supported by CUNY Community College Collaborative Incentive Research Grant 91639-0001 “Mathematical Foundations of Knowledge Representation”.     

An $\mathsf{EDF}$ -based restricted-migration scheduling algorithm for multiprocessor soft real-time systems

There has been much recent interest in the use of the earliest-deadline-first ( ) algorithm for scheduling soft real-time sporadic task systems on identical multiprocessors. In hard real-time systems, a significant disparity exists between -based schemes and Pfair scheduling: on M processors, the worst-case schedulable utilization for all known variants is approximately M/2, whereas it is M for optimal Pfair algorithms. This is unfortunate because -based algorithms entail lower scheduling and task-migration overheads. However, such a disparity in schedulability can be alleviated by easing the requirement that all deadlines be met, which may be sufficient for soft real-time systems. In particular, in recent work, we have shown that if task migrations are not restricted, then (i.e. , global ) can ensure bounded tardiness for a sporadic task system with no restrictions on total utilization. Unrestricted task migrations in global may be unappealing for some systems, but if migrations are forbidden entirely, then bounded tardiness cannot be guaranteed. In this paper, we address the issue of striking a balance between task migrations and system utilization by proposing an algorithm called , which is based upon and treads a middle path, by restricting, but not eliminating, task migrations. Specifically, under , the ability to migrate is required for at most M−1 tasks, and it is sufficient that every such task migrate between two processors and at job boundaries only. , like global , can ensure bounded tardiness to a sporadic task system as long as the available processing capacity is not exceeded, but, unlike global , may require that per-task utilizations be capped. The required cap is quite liberal, hence, should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization.

Tuples of Disjoint $\mathsf{NP}$ -Sets

Disjoint -pairs are a well studied complexity-theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint -pairs to disjoint k-tuples of -sets for k≥2. We define subclasses of the class of all disjoint k-tuples of -sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system. In our main result we show that complete disjoint -pairs exist if and only if complete disjoint k-tuples of -sets exist for all k≥2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all k-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof systems. An extended abstract of this paper appeared in the proceedings of the conference CSR 2006 (Lecture Notes in Computer Science 3967, 80–91, 2006). Supported by DFG grant KO 1053/5-1.     

On “Exploiting” Node-Heterogeneous Clusters Optimally

It is proved that “FIFO” worksharing protocols provide asymptotically optimal solutions to two problems related to sharing large collections of independent tasks in a heterogeneous network of workstations (HNOW) . In the , one seeks to accomplish as much work as possible on during a prespecified fixed period of L time units. In the , one seeks to complete W units of work by “renting” for as short a time as necessary. The worksharing protocols we study are crafted within an architectural model that characterizes via parameters that measure ’s workstations’ computational and communicational powers. All valid protocols are self-scheduling, in the sense that they determine completely both an amount of work to allocate to each of ’s workstations and a schedule for all related interworkstation communications. The schedules provide either a value for W given L, or a value for L given W, hence solve both of the motivating problems. A protocol observes a FIFO regimen if it has ’s workstations finish their assigned work, and return their results, in the same order in which they are supplied with their workloads. The proven optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other protocol during all sufficiently long worksharing episodes, and that they complete sufficiently large given collections of tasks at least as fast as any other protocol. Simulation experiments illustrate that the superiority of FIFO protocols is often observed during worksharing episodes of only a few minutes’ duration. A portion of this research was presented at the 15th ACM Symp. on Parallelism in Algorithms and Architectures (2003).     

A schedulable utilization bound for the multiprocessor \mathsf{EPDF} Pfair algorithm

The earliest-pseudo-deadline-first ( ) Pfair scheduling algorithm is less expensive than some other known Pfair algorithms, but is not optimal for scheduling recurrent real-time tasks on more than two processors. In prior work, sufficient per-task weight (i.e., utilization) restrictions were established for ensuring that tasks either do not miss their deadlines or have bounded tardiness when scheduled under . Implicit in these restrictions is the assumption that the total system utilization may equal the total available processing capacity (i.e., the total number of processors). This paper considers an orthogonal issue, namely, determining a sufficient restriction on the total utilization of a task set for it to be schedulable (i.e., a schedulable utilization bound) under , assuming that there are no per-task weight restrictions. We prove that a task set with total utilization at most is correctly scheduled under on M processors, regardless of how large each task’s weight is. At present, we do not know whether this value represents the worst-case for , but we do provide a counterexample that shows that it cannot be improved to exceed 86% of the total processing capacity. The schedulable utilization bound we derive is expressed in terms of the maximum weight of any task, and hence, if this value is known, may be used to schedule task sets with total utilization greater than .

Characterizing Programming Systems Allowing Program Self-Reference

The interest is in characterizing insightfully the power of program self-reference in effective programming systems ( ), the computability-theoretic analogs of programming languages (for the partial computable functions). In an in which the constructive form of Kleene’s Recursion Theorem (KRT) holds, it is possible to construct, algorithmically, from an arbitrary algorithmic task, a self-referential program that, in a sense, creates a self-copy and then performs that task on the self-copy. In an in which the not-necessarily-constructive form of Kleene’s Recursion Theorem (krt) holds, such self-referential programs exist, but cannot, in general, be found algorithmically. In an earlier effort, Royer proved that there is no collection of recursive denotational control structures whose implementability characterizes the in which KRT holds. One main result herein, proven by a finite injury priority argument, is that the in which krt holds are, similarly, not characterized by the implementability of some collection of recursive denotational control structures. On the positive side, however, a characterization of such of a rather different sort is shown herein. Though, perhaps not the insightful characterization sought after, this surprising result reveals that a hidden and inherent constructivity is always present in krt. This paper is an expanded version of [6]. This paper received support from NSF Grant CCR-0208616. “Know thyself.” Greek proverb     

Adaptive Energy Management for Incremental Deployment of Heterogeneous Wireless Sensors

We introduce a new modelling assumption for wireless sensor networks, that of node redeployment (addition of sensor devices during protocol evolution) and we extend the modelling assumption of heterogeneity (having sensor devices of various types). These two features further increase the highly dynamic nature of such networks and adaptation becomes a powerful technique for protocol design. Under these modelling assumptions, we design, implement and evaluate a new power conservation scheme for efficient data propagation. Our scheme is adaptive: it locally monitors the network conditions (density, energy) and accordingly adjusts the sleep-awake schedules of the nodes towards improved operation choices. The scheme is simple, distributed and does not require exchange of control messages between nodes. Implementing our protocol in software we combine it with two well-known data propagation protocols and evaluate the achieved performance through a detailed simulation study using our extended version of the network simulator ns-2. We focus on highly dynamic scenarios with respect to network density, traffic conditions and sensor node resources. We propose a new general and parameterized metric capturing the trade-offs between delivery rate, energy efficiency and latency. The simulation findings demonstrate significant gains (such as more than doubling the success rate of the well-known propagation protocol) and good trade-offs achieved. Furthermore, the redeployment of additional sensors during network evolution and/or the heterogeneous deployment of sensors, drastically improve (when compared to “equal total power” simultaneous deployment of identical sensors at the start) the protocol performance (i.e. the success rate increases up to four times while reducing energy dissipation and, interestingly, keeping latency low). This work has been partially supported by the IST Programme of the European Union under contract number IST-2005-15964 ( ), the Programme under the European Social Fund (ESF) and Operational Program for Educational and Vocational Training II (EPEAEK II) and the Programme of GSRT under contract number 03ED568. A preliminary version of this work has appeared in [13].     

Interacting Explicit Evidence Systems

Logic of proofs , introduced by S. Artemov, originally designed for describing properties of formal proofs, now became a basis for the theory of knowledge with justification (cf. S. Artemov, Evidence-based common knowledge, Technical report TR–2004018, CUNY Ph.D. Program in Computer Science, 2005). So far, in epistemic systems with justification the corresponding “evidence part”, even for multi-agent systems, consisted of a single explicit evidence logic. In this paper we introduce logics describing two interacting explicit evidence systems. We find an appropriate formalization of the intended semantics and prove the completeness of these logics with respect to both symbolic and arithmetical models. Also, we find the forgetful projections for the two-agent justification logics which are extensions of the bimodal logic .     

Planar and Grid Graph Reachability Problems

We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for . In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main results are:

Approximately Fair Cost Allocation in Metric Traveling Salesman Games

A traveling salesman game is a cooperative game . Here N, the set of players, is the set of cities (or the vertices of the complete graph) and c _D is the characteristic function where D is the underlying cost matrix. For all S⊆N, define c _D (S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪{0} where is called as the home city. Define Core as the core of a traveling salesman game . Okamoto (Discrete Appl. Math. 138:349–369, [2004]) conjectured that for the traveling salesman game with D satisfying triangle inequality, the problem of testing whether Core is empty or not is -hard. We prove that this conjecture is true. This result directly implies the -hardness for the general case when D is asymmetric. We also study approximately fair cost allocations for these games. For this, we introduce the cycle cover games and show that the core of a cycle cover game is non-empty by finding a fair cost allocation vector in polynomial time. For a traveling salesman game, let and ∀ S⊆N, x(S)≤ε⋅c _D (S)} be an ε-approximate core, for a given ε>1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of several related cycle cover games, we provide a polynomial time algorithm demonstrating the non-emptiness of the log ₂(|N|−1)-approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We improve it further by finding a -approximate core in polynomial time for some constant c. We also show that there exists an ε ₀>1 such that it is -hard to decide whether ε ₀-Core is empty or not. A preliminary version of the paper appeared in the third Workshop on Approximation and Online Algorithms (WAOA), 2005.     

Strong Completeness and Limited Canonicity for PDL

Propositional dynamic logic () is complete but not compact. As a consequence, strong completeness (the property ) requires an infinitary proof system. In this paper, we present a short proof for strong completeness of relative to an infinitary proof system containing the rule from [α; β ⁿ ]φ for all , conclude . The proof uses a universal canonical model, and it is generalized to other modal logics with infinitary proof rules, such as epistemic knowledge with common knowledge. Also, we show that the universal canonical model of lacks the property of modal harmony, the analogue of the Truth lemma for modal operators.     

On-line graph coloring of {\mathbb{P}_5}-free graphs

Kierstead et al. (SIAM J Discret Math 8:485–498, 1995) have shown 1 that the competitive function of on-line coloring for -free graphs (i.e., graphs without induced path on 5 vertices) is bounded from above by the exponential function . No nontrivial lower bound was known. In this paper we show the quadratic lower bound . More precisely, we prove that is the exact competitive function for ()-free graphs. In this paper we also prove that 2 - 1 is the competitive function of the best clique covering on-line algorithm for ()-free graphs.     

Competitive Analysis of Scheduling Algorithms for Aggregated Links

We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized. We present a deterministic online algorithm with competitive ratio , and show a matching lower bound, even for randomized algorithms. The performance bound for we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), ’s performance is close to the optimum. We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is -hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k. W. Jawor and M. Chrobak supported by NSF grants OISE-0340752 and CCR-0208856. Work of C. Dürr conducted while being affiliated with the Laboratoire de Recherche en Informatique, Université Paris-Sud, 91405 Orsay. Supported by the CNRS/NSF grant 17171 and ANR Alpage.     

Translational lemmas for DLOGTIME-uniform circuits,alternating TMs,and PRAMs

We present translational lemmas for the three standard models of parallel computation, and apply them to obtain tight hierarchy results. It is shown that, for arbitrarily small rational constant , (i) there is a language which can be accepted by a -uniform circuit family of depth and size but not by any -uniform circuit family of depth and size , (ii) there is a language which can be accepted by a -time -space ATM with l worktapes but not by any -time -space ATM with the same l worktapes if the number of tape symbols is fixed, and (iii) there is a language which can be accepted by a -time PRAM with processors but not by any -time PRAM with processors. Here, c > 0, d ≥ 1, r ₁ > 1, and r ₂ ≥ 1 are arbitrary rational constants, and l ≥ 2 is an arbitrary integer. Preliminary versions of different parts of this paper appeared in Proc. MCU 2004 (LNCS 3354) and Proc. FCT 2005 (LNCS 3623).     

Cardinal interpolation with periodic polysplines on strips

Abstract  We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we prove the existence of a unique function in , polyharmonic of order p on each strip , , and periodic in its last n variables, whose restriction to the parallel hyperplanes , , coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in . The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal -splines. Keywords: cardinal -splines, polyharmonic functions, multivariable interpolation Mathematics Subject Classification (2000): 41A05, 41A15, 41A63     

Optimally Adaptive Integration of Univariate Lipschitz Functions

We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an additive error of at most ε using as few samples of f as possible. We use the adaptive framework: on all problem instances an adaptive algorithm should perform almost as well as the best possible algorithm tuned for the particular problem instance. We distinguish between and , the performances of the best possible deterministic and randomized algorithms, respectively. We give a deterministic algorithm that uses samples and show that an asymptotically better algorithm is impossible. However, any deterministic algorithm requires samples on some problem instance. By combining a deterministic adaptive algorithm and Monte Carlo sampling with variance reduction, we give an algorithm that uses at most samples. We also show that any algorithm requires samples in expectation on some problem instance (f,ε), which proves that our algorithm is optimal.