Search

This is an extended abstract of my talk on generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are still undecidable on every strongly generic (i.e., "very very large") subset of inputs. For instance, the classical Halting Problem for Turing machines is strongly undecidable. Moreover, we prove an analog of the Rice's theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. On the other hand, it has been shown recently that many of these classical undecidable problems are easily decidable on some generic (i.e., "very large") subsets of inputs. Altogether, these results lead to an interesting hierarchy of undecidable problems with respect to the size of subsets of inputs where the problems are still undecidable - a frequency analysis of hardness. We construct here some natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). [ABSTRACT FROM AUTHOR]

D. Krieger and J. Shallit have proved that every real number greater than 1 is a critical exponent of some sequence [1]. We show how this result can be derived from some general statements about sequences whose subsequences have (almost) maximal Kolmogorov complexity. In this way one can also construct a sequence that has no "approximate" fractional powers with exponent that exceeds a given value. [ABSTRACT FROM AUTHOR]

We will show how padding techniques can be applied on one-dimensional cellular automata by proving a transfer theorem on complexity classes (how one inclusion of classes implies others). Then we will discuss the consequences of this result, in particular when considering that all languages recognized in linear space can be recognized in linear time (whether or not this is true is still an open question), and see the implications on one-tape Turing machines. [ABSTRACT FROM AUTHOR]

We present a polynomial time algorithm for the following problem: to check whether a lacunary polynomial f(x) vanishes at a given primitive nth root of unity ζn. A priori f(ζn) may be nonzero and doubly exponentially small in the input size. Only exponential algorithms were known for this problem. The existence of an efficient procedure in the case of factored n was conjectured by D. Plaisted in 1984. As a consequence we show that the problem of the divisibility testing of a lacunary polynomial by some cyclotomic polynomial belongs to the complexity class $\mathcal{NP}$. [ABSTRACT FROM AUTHOR]

We study the empirical meaning of randomness with respect to a family of probability distributions Pθ, where θ is a real parameter, using algorithmic randomness theory. In the case when for a computable probability distribution Pθ an effectively strongly consistent estimate exists, we show that the Levin's a priory semicomputable semimeasure of the set of all Pθ-random sequences is positive if and only if the parameter θ is a computable real number. The different methods for generating "meaningful" Pθ-random sequences with noncomputable θ are discussed. [ABSTRACT FROM AUTHOR]

Fischer and Rabin proved in [4] that Presburger Arithmetic has at least double exponential worse-case complexity. In [6] a theory of generic-case complexity was developed, where algorithmic problems are studied on "most" inputs instead of all set of inputs. An interesting question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic on some "large" set of closed formulas. We prove, however, that there is no even exponential generic algorithm working correctly on arbitrary "very large" sets of inputs (so-called strongly generic sets). [ABSTRACT FROM AUTHOR]

This paper presents an approach to the analysis of real-time properties of security protocols, based on the Strand Space formalism for describing the behaviour of the participants in the protocol. The approach is compared with a trace-based analysis introduced by Pilegaard et al. [14]. Interval Logic with durations is used to express and reason about temporal phenomena. Strand Spaces were chosen as the starting point for our approach, since the causalities between important events in protocols are revealed in an illustrative manner by this formalism. The advantage of the trace-based approach is that it supports inductive reasoning in connection with the analysis of untimed properties. Interval Logic is chosen as the real-time formalism, as timing requirements and timing properties of security protocols are often expressible as interval properties. As an example, the Kerberos authentication protocol, which is based on concepts like timestamps and lifetimes, and which requires freshness of certain messages, is analysed. [ABSTRACT FROM AUTHOR]

Local constraints on an infinite sequence that imply global regularity are of general interest in combinatorics on words. We consider this topic by studying everywhere α-repetitive sequences, sequences in which every position has an occurrence of a repetition of order α ≥ 1 of bounded length. The number of minimal such repetitions, called minimal α-powers, is then finite. A natural question regarding global regularity is to determine the least number of minimal α-powers such that an α-repetitive sequence is not necessarily ultimately periodic. We solve this question for 1 ≤ α ≤ 17/8. We also show that Sturmian words are among the optimal 2 - and 2 + -repetitive sequences. [ABSTRACT FROM AUTHOR]

A threshold gate is a sum of input variables with integer coefficients (weights). It outputs 1 if the sum is positive. The maximal absolute value of coefficients of a threshold gate is called its weight. A perceptron of order d is a circuit of depth 2 having a threshold gate on the top level and any Boolean gates of fan-in at most d on the remaining level. For every constant d ≥ 2 independent of the number of inputs n we exhibit a perceptron of order d that requires weights at least $n^{\Omega(n^d)}$, that is, the weight of any perceptron of order d computing the same Boolean function is at least $n^{\Omega(n^d)}$. This bound is tight: every perceptron of order d is equivalent to a perceptron of order d and weight $n^{O(n^d)}$. In the case of threshold gates (i.e. d = 1) the result was established by Håstad in [1]; we use Håstad's techniques. [ABSTRACT FROM AUTHOR]

In the first part we provide an elementary proof of the result of Homer and Mocas [3] that for all constant c, the class EXP is not included in . The proof is based on a simple diagonalization, whereas it uses resource-bounded Kolmogorov complexity in [3]. In the second part, we investigate links between resource-bounded Kolmogorov complexity and nonuniform classes in computational complexity. Assuming a weak version of polynomial-time symmetry of information, we show that exponential-time problems do not have polynomial-size circuits (in symbols, ${\mathsf {EXP}} \not\subset {\rm P/poly}$). [ABSTRACT FROM AUTHOR]

In order to simplify simulation and verification of SDL specified communication protocols, we introduce modified coloured Petri nets called hierarchical timed typed nets (HTT-nets). A method for translation from SDL into HTT-nets is presented. A tool SPV (SDL protocol verifier) including a translator from SDL into HTT-nets, as well as means for editing, simulating, visualizing and verifying the net models, is described. For verification, the tool SPV uses a model-checking method. As case studies, we apply the tool SPV to RE-protocol [4], ATMR protocol [10] and i-protocol [5]. [ABSTRACT FROM AUTHOR]

Traffic pattern is a point of concern in today's modeling approach of network-based computing systems including NoC's and Clusters. Hypermesh is a promising network topology suitable for a range of networks. Although there are few models reported for hypermeshes with uniform traffic pattern, no analytical model has been reported yet that deal with hotspot traffic load. Since uniform traffic assumption is not always justifiable in practice as there are many parallel applications that exhibit non-uniform traffic patterns, which can produce hotspots in the network, in this study we propose a novel analytical model to analyze the mean message latency in wormhole-switched hypermesh in the presence of hot-spot traffic. [ABSTRACT FROM AUTHOR]

We study the compressed word problem: a variant of the word problem for finitely generated groups where the input word is given by a context-free grammar that generates exactly one string. We show that finite extensions and free products preserve the complexity of the compressed word problem. Also, the compressed word problem for a graph group can be solved in polynomial time. These results allow us to obtain new upper complexity bounds for the word problem for certain automorphism groups and group extensions. [ABSTRACT FROM AUTHOR]

Given a program with two arguments p(x,y). Let the first argument x0 be fixed. The aim of program specialization with respect to the known x0 is to construct an optimized program Px0(y) such that Px0(y) = P(x0,y). Specialization of interpreters with respect to programs is well known problem. In this paper we argue that specialization of interpreters with respect to data may be seen as program verification. [ABSTRACT FROM AUTHOR]

We revisit a well studied linear algebraic problem, computing the rank and determinant of matrices, in order to obtain completeness results for small complexity classes. In particular, we prove that computing the rank of a class of diagonally dominant matrices is complete for L. We show that computing the permanent and determinant of tridiagonal matrices over ℤ is in GapNC1 and is hard for NC1. We also initiate the study of computing the rigidity of a matrix: the number of entries that needs to be changed in order to bring the rank of a matrix below a given value. It is NP-hard over $\mathbb{F}_2$ and we prove that some restricted versions characterize small complexity classes. We also look at a variant of rigidity where there is a bound on the amount of change allowed. Using ideas from the linear interval equations literature, we show that this problem is NP-hard over ℚ and that a certain restricted version is NP-complete. Restricting the problem further, we obtain variations which can be computed in PL and are hard for C=L. [ABSTRACT FROM AUTHOR]

Retrieval of images based on the content is a process that requires the comparison of the multidimensional representation of the contents of a given example with all of those images in the database. To speed up this process, several indexing techniques have been proposed. All of them do efficiently the work up to 30 dimensions [8]. Above that, their performance is affected by the properties of the multidimensional space. Facing this problem, one alternative is to reduce the dimensions of the image representation which however conveys an additional loss of precision. Another approach that has been studied and seems to exhibit good performance is the clustering of the database. On this article we analyze this option from a computational complexity approach and devise a proposal for the number of clusters to obtain from the database, which can lead to sublinear algorithms. [ABSTRACT FROM AUTHOR]

Consider a family of sets and a single set, called query set. How can one quickly find a member of the family which has a maximal intersection with the query set? Strict time constraints on the query and on a possible preprocessing of the set family make this problem challenging. Such maximal intersection queries arise in a wide range of applications, including web search, recommendation systems, and distributing on-line advertisements. In general, maximal intersection queries are computationally expensive. Therefore, one needs to add some assumptions about the input in order to get an efficient solution. We investigate two well-motivated distributions over all families of sets and propose an algorithm for each of them. We show that with very high probability an almost optimal solution is found in time logarithmic in the size of the family. In particular, we point out a threshold phenomenon on the probabilities of intersecting sets in each of our two input models which leads to the efficient algorithms mentioned above. [ABSTRACT FROM AUTHOR]

Digital watermarking, named after paper watermarking, was proposed to protect copyrights of perceptual content owners. A Watermark, or an author's signature, is hidden in a signal by small modifications of the signal. This signature, particularly, can be used as the evidence of authorship/ownership in a court. Performing attacks, a Malefactor is finding ways to destroy the embedded watermark so that it will not be found by a detection algorithm. Frequently a watermark becomes undetectable after an attack due to the loss of synchronization problem. One of the ways to handle this problem is to build a reference system which would be robust to a certain range of attacks. A novel algorithm of building such a system has been proposed by Delannay in [1]. Starting from ideas of Delannay we propose new approach to constructing a secret binary partition of an image. [ABSTRACT FROM AUTHOR]

In the paper, new modified agglomerative algorithms for hierarchical clustering are suggested. The clustering process is targeted to generating a cluster hierarchy which can contain the same items in different clusters. The algorithms are based on the following additional operations: (i) building an ordinal item pair proximity ('distance') including the usage of multicriteria approaches; (ii) integration of several item pair at each stage of the algorithms; and (iii) inclusion of the same items into different integrated item pairs/clusters. The suggested modifications above are significant from the viewpoints of practice, e.g., design of systems architecture for engineering and computer systems. [ABSTRACT FROM AUTHOR]

How could one estimate the total number of clicks a new advertisement could potentially receive in the current market? This question, called the click volume estimation problem is investigated in this paper. This constitutes a new research direction for advertising engines. We propose a model of computing an estimation of the click volume. A key component of our solution is the application of linear regression to a large (but sparse) data set. We propose an iterative method in order to achieve a fast approximation of the solution. We prove that our algorithm always converges to optimal parameters of linear regression. To the best of our knowledge, it is the first time when linear regression is considered in such a large scale context. [ABSTRACT FROM AUTHOR]

To solve a problem on a given CNF formula F a splitting algorithm recursively calls for F[v] and F[¬v] for a variable v. Obviously, after the first call an algorithm obtains some information on the structure of the formula that can be used in the second call. We use this idea to design new surprisingly simple algorithms for the MAX-SAT problem. Namely, we show that MAX-SAT for formulas with constant clause density can be solved in time cn, where c < 2 is a constant and n is the number of variables, and within polynomial space (the only known such algorithm by Dantsin and Wolpert uses exponential space). We also prove that MAX-2-SAT can be solved in time 2m/5.88, where m is the number of clauses (this improves the bound 2m/5.769 proved independently by Kneis et al. and by Scott and Sorkin). [ABSTRACT FROM AUTHOR]

It has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some nonregular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as nonexistence of an r.e. bound on the growth rate of generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations. [ABSTRACT FROM AUTHOR]

The maximum constraint satisfaction problem (Max CSP) is the following computational problem: an instance is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many well-known problems (such as Max k-SAT and Max Cut) and so is NP-hard in general. It is natural to study how restrictions on the allowed constraint types (or constraint language) affect the complexity and approximability of Max CSP. All constraint languages, for which the CSP problem (i.e., the problem of deciding whether all constraints in an instance can be simultaneously satisfied) is currently known to be NP-hard, have a certain algebraic property, and it has been conjectured that CSP problems are tractable for all other constraint languages. We prove that any constraint language with this algebraic property makes Max CSP hard at gap location 1, thus ruling out the existence of a polynomial-time approximation scheme for such problems. We then apply this result to Max CSP restricted to a single constraint type. We show that, unless P = NP, such problems either are trivial or else do not admit polynomial-time approximation schemes. All our hardness results hold even if the number of occurrences of each variable is bounded by a constant. [ABSTRACT FROM AUTHOR]

We investigate the complexity of equivalence problems for { ∪ , ∩ , −, + ,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C=L, P,${\rm \Pi^P_{2}}$, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of { ∪ , ∩ , −, + ,×}-circuits. [ABSTRACT FROM AUTHOR]

Starting off with Moss and Parikh's view of knowledge we develop a kind of dynamic logic of knowledge acquisition. Corresponding procedures are basically modelled by functions changing the knowledge states of the agent under discussion, and the machinery of deterministic PDL is then utilized for knowledge-based programming. The main issues of the paper are the fundamental meta-theorems on the arising logic, KAL. We prove, in particular, the soundness and completeness with respect to the intended class of structures as well as the decidability of KAL. [ABSTRACT FROM AUTHOR]

The Bouillon project implements the vision termed a "Social Web". It is an extremely open collaboration environment employing social links for creation, filtering and dissemination of information. It is also an attempt to boost the wiki effect of knowledge crystallization. Currently, the project is in stage of public testing, available at http:// oc-co.org. [ABSTRACT FROM AUTHOR]

In this paper, using the chromatic properties of power graphs we propose a new approach for placing resources in symmetric networks. Our novel placement scheme guarantees a perfect placement when such a solution is feasible in the topology. [ABSTRACT FROM AUTHOR]

In this paper, we consider the decidability of two problems related to information flow in a system with respect to some property. A flow occurs in a system if the conditional probability of the property under some partial observation differs from the a priori probability of that property. For systems modelled as finite Markov chains we prove that the two following problems are decidable: does a system has information flow for a given regular property? is it true that the system has no information flow for any (sequential) property? [ABSTRACT FROM AUTHOR]

Let G = (VG, EG) be an undirected graph, $\mathcal{T} = \{T_1, \ldots, T_k\}$ be a collection of disjoint subsets of nodes. Nodes in T1 ∪ ... ∪ Tk are called terminals, other nodes are called inner. By a $\mathcal{T}$-path P we mean an undirected path such that P connects terminals from distinct sets in $\mathcal{T}$ and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection $\mathcal{P}$ of $\mathcal{T}$-paths such that at most two paths in $\mathcal{P}$ pass through any node v ∈ VG. Our algorithm is purely combinatorial and achieves the time bound of O(mn2), where n : = VG, m : = EG. [ABSTRACT FROM AUTHOR]

The class , 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 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 that function on that input.) We give a relativized negative answer to this question by exhibiting an oracle under which functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, and functions are not computable in polynomial-time with an oracle. [ABSTRACT FROM AUTHOR]

We explore the restrictiveness of planarity on the complexity of computing the determinant and the permanent, and show that both problems remain as hard as in the general case, i.e. GapL and #P complete. On the other hand, both bipartite planarity and bimodal planarity bring the complexity of permanents down (but no further) to that of determinants. The permanent or the determinant modulo 2 is complete for ⊕L, and we show that parity of paths in a layered grid graph (which is bimodal planar) is also complete for this class. We also relate the complexity of grid graph reachability to that of testing existence/uniqueness of a perfect matching in a planar bipartite graph. [ABSTRACT FROM AUTHOR]

Overview. The development of structured programs is carried out either using bottomup techniques, or top-down techniques; we show how refinement and proof can be used to help in the top-down development of structured imperative programs. When a problem is stated, the incremental proof-based methodology of event B [9] starts by stating a very abstract model and further refinements lead to finer-grain event-based models which are used to derive an algorithm. The main idea is to consider each procedure call as an abstract event of a model corresponding to the development of the procedure; generally, a procedure is specified by a pre/post specification and then the refinement process leads to a set of events, which are finally combined to obtain the body of the procedure. It means that the abstraction corresponds to the procedure call and the body is derived using the refinement process. The refinement process may also use recursive procedures and supports the top-down refinement. The procedure call simulates the abstract event and the refinement guarantees the correctness of the resulting algorithm. [ABSTRACT FROM AUTHOR]

We propose a simple modification of a well-known Random Walk algorithm for solving the Satisfiability problem and analyze its performance on random CNFs with a planted solution. We rigorously prove that the new algorithm solves the Full CNF with high probability, and for random CNFs with a planted solution of high density finds an assignment that differs from the planted in only ε-fraction of variables. In the experiments the algorithm solves random CNFs with a planted solution of any density. [ABSTRACT FROM AUTHOR]

A reversible abstract machine architecture and its reversible machine code are presented and formalized. For machine code to be reversible, both the underlying control logic and each instruction must be reversible. A general class of machine instruction sets was proven to be reversible, building on our concept of reversible updates. The presentation is abstract and can serve as a guideline for a family of reversible processor designs. By example, we illustrate programming principles for the abstract machine architecture formalized in this paper. [ABSTRACT FROM AUTHOR]

Sequences of numbers (either natural integers, or integers or rational) of level have been defined in [FS06] as the sequences which can be computed by deterministic pushdown automata of level k. We extend this definition to sequences of words indexed by words. We give characterisations of these sequences in terms of "higher-order" L-systems. In particular sequences of rational numbers of level 3 are characterised by polynomial recurrences (which generalize the P-recurrent sequences studied in [Sta80]). The equality problem for sequences of rational numbers of level 3 is shown decidable. [ABSTRACT FROM AUTHOR]

In this paper we extend mobile ambients with timers and proximities, and so we get a clear notion of location and mobility. Timers define timeouts for various resources, making them available only for a determined period of time; we add timers to ambients and capabilities. We present an example how the new model is working. The coordination of the ambients in time and space is given by assigning specific values to timers, and by a set of coordination rules. [ABSTRACT FROM AUTHOR]

This paper gives an overview of activities and products that stem from the Thousands of Problems for Theorem Provers (TPTP) problem library for Automated Theorem Proving (ATP) systems. These include the TPTP itself, the Thousands of Solutions from Theorem Provers (TSTP) solution library, the CADE ATP System Competition (CASC), tools such as my semantic Derivation Verifier (GDV) and the Interactive Derivation Viewer (IDV), meta-ATP systems such as the Smart Selective Competition Parallelism (SSCPA) system and the Semantic Relevance Axiom Selection System (SRASS), and applications in various domains. [ABSTRACT FROM AUTHOR]

We present a new class of automata which strictly contains the class of aperiodic automata and shares with the latter certain synchronization properties. In particular, every strongly connected automaton in this new class is synchronizing and has a reset word of length $\left\lfloor\frac{n(n+1)}6\right\rfloor$ where n is the number of states of the automaton. [ABSTRACT FROM AUTHOR]

A word w over a finite alphabet Σ is n-collapsing if for an arbitrary DFA ${\mathcal A}=\langle Q,\Sigma,\delta\rangle$, the inequality $\delta(Q,w)\leQ-n$ holds provided that $\delta(Q,u)\leQ-n$ for some word u∈Σ+ (depending on ${\mathcal A}$). We overview some recent results related to this notion. One of these results implies that the property of being n-collapsing is algorithmically recognizable for any given positive integer n. [ABSTRACT FROM AUTHOR]

The talk reflects recent joint work with Nachum Dershowitz [4]. [ABSTRACT FROM AUTHOR]