Optimization problems and the polynomial hierarchy

It is demonstrated that such problems as the symmetric Travelling Salesman Problem, Chromatic Number Problem, Maximal Clique Problem and a Knapsack Packing Problem are in the Δ^P₂ level of PH and no lower if ∑^P₁ ≠ Π^P₁, or NP≠co-NP. This shows that these problems cannot be solved by polynomial reductions that use only positive information from an NP oracle, if NP≠co-NP. It is then shown how to extend these results to prove that interesting problems are properly in Δ^P,X_i+1 for all X,k where ∑^P,X_k≠Π^P,X_k in PH^X.     

Fine structure of a one-dimensional discrete point system

We consider a system of N points x ₁ < ... < x _N on a segment of the real line. An ideal system (crystal) is a system where all distances between neighbors are the same. Deviation from idealness is characterized by a system of finite differences ? _i ¹ = x _x+1 ? x _i , ? _i ^k+1 = ? _i+1 ^k ? ? _i ^k , for all possible i and k. We find asymptotic estimates as N ?? ??, k????, for a system of points minimizing the potential energy of a Coulomb system in an external field.     

On the (Non-)Existence of Polynomial Kernels for P l -Free Edge Modification Problems

Given a graph G=(V,E) and a positive integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph $H=(V,E\vartriangle F)$ satisfies the property Π. In the Π edge-completion problem, the set F is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171–176, 1996; Fellows et al. in FCT, pp. 312–321, 2007; Heggernes et al. in STOC, pp. 374–381, 2007). When parameterized by the size k of the set F, it has been proved that if Π is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three Π edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171–176, 1996). It was then natural to ask (Bodlaender et al. in IWPEC, 2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (G′,k′) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively (Kratsch and Wahlström in IWPEC, pp. 264–275, 2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P ₄-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the P _l -free edge-deletion and the C _l -free edge-deletion problems for l?7 and l≥4 respectively. Indeed, if they exist, then NP?coNP/poly.     

Truncations of infinite matrices and algebraic series associated with some of grammars

We consider an algebraic system over $\text{R}$[x] of the form X = a₀(x)X^k+ a_k1(x)X+a_k(x), where a₀(x) and a_k(x) are in x$\text{R}$[x] and a_k?1(x) is in x$\text{R}$. Let A be the infinite incidence matrix associated with the algebraic system. Then we prove that the eigenvalues of northwest corner truncations of A are dense in some algebraic curves.Using this we get a result on positive algebraic series. We consider the case that the coefficients of a₁(x)(i = 0,…,k?1, k) are positive. The algebraic series generated by the algebraic system may be viewed as a function in the complex variable x. Then by the above fact we prove that the radius of convergence of the function equals the least positive zero of the modified discriminant of the system.As an application to context free languages we show a procedure for calculating the entropy of some one counter languages. Other applications to Dyck languages and the Lukasiewicz language are also described.     

Uncountable automatic classes and learning

In this paper we consider uncountable classes recognizable by ω-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language L from the class plus an ω-index α and outputs a sequence of ω-automata such that all but finitely many of these ω-automata accept the index α if and only if α is an index for L.It is shown that any class is behaviourally correct learnable if and only if it satisfies Angluin’s tell-tale condition. For explanatory learning, such a result needs that a suitable indexing of the class is chosen. On the one hand, every class satisfying Angluin’s tell-tale condition is vacillatorily learnable in every indexing; on the other hand, there is a fixed class such that the level of the class in the hierarchy of vacillatory learning depends on the indexing of the class chosen.We also consider a notion of blind learning. On the one hand, a class is blind explanatorily (vacillatorily) learnable if and only if it satisfies Angluin’s tell-tale condition and is countable; on the other hand, for behaviourally correct learning, there is no difference between the blind and non-blind version.This work establishes a bridge between the theory of ω-automata and inductive inference (learning theory).     

Learning large-alphabet and analog circuits with value injection queries

We consider the problem of learning an acyclic discrete circuit with n wires, fan-in bounded by k and alphabet size s using value injection queries. For the class of transitively reduced circuits, we develop the Distinguishing Paths Algorithm, that learns such a circuit using (ns) ^O(k) value injection queries and time polynomial in the number of queries. We describe a generalization of the algorithm to the class of circuits with shortcut width bounded by b that uses (ns) ^O(k+b) value injection queries. Both algorithms use value injection queries that fix only O(kd) wires, where d is the depth of the target circuit. We give a reduction showing that without such restrictions on the topology of the circuit, the learning problem may be computationally intractable when s=n ^Θ(1), even for circuits of depth O(log?n). We then apply our large-alphabet learning algorithms to the problem of approximate learning of analog circuits whose gate functions satisfy a Lipschitz condition. Finally, we consider models in which behavioral equivalence queries are also available, and extend and improve the learning algorithms of (Angluin in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 584–593, 2006) to handle general classes of gate functions that are polynomial time learnable from counterexamples.     

Learning a subclass of k-quasi-Horn formulas with membership queries

Boolean formulas have been widely studied in the field of learning theory. We focus on the model of learning with queries, and study a restriction of the class of k-quasi-Horn formulas, that is, conjunctive normal form formulas where the number of unnegated literals per clause is at most k. This class is known to be as hard to learn as the general class CNF of conjunctive normal form formulas. By imposing some constraints, we define a fragment of this logic that can be learned using only membership queries. Also we prove that none of these constraints makes by itself the class learnable.     

Zur Konvergenz der Ableitungen von Interpolationspolynomen

Letp _n denote the polynomial of degreen or less that interpolates a given smooth functionf at the ?eby?ev nodest _j ⁿ =cos(jπ/n), 0≤j≤n, and let ‖·‖ be the maximum norm inC[?1, 1]. It is proved that fork-th derivatives (2≤k≤n) estimates of the following type hold $$\parallel f^{(k)} - p_n^{(k)} \parallel \leqslant c_k n^{k - 1} \inf \{ \parallel f^{(k)} - q\parallel :q \in \Pi _{n - k} \} .$$ In this relationc _k only depends onk andΠ _n?k denotes the space of polynomials up to degreen?k.     

Learning from natural instructions

Machine learning is traditionally formalized and investigated as the study of learning concepts and decision functions from labeled examples, requiring a representation that encodes information about the domain of the decision function to be learned. We are interested in providing a way for a human teacher to interact with an automated learner using natural instructions, thus allowing the teacher to communicate the relevant domain expertise to the learner without necessarily knowing anything about the internal representations used in the learning process. In this paper we suggest to view the process of learning a decision function as a natural language lesson interpretation problem, as opposed to learning from labeled examples. This view of machine learning is motivated by human learning processes, in which the learner is given a lesson describing the target concept directly and a few instances exemplifying it. We introduce a learning algorithm for the lesson interpretation problem that receives feedback from its performance on the final task, while learning jointly (1) how to interpret the lesson and (2) how to use this interpretation to do well on the final task. traditional machine learning by focusing on supplying the learner only with information that can be provided by a task expert. We evaluate our approach by applying it to the rules of the solitaire card game. We show that our learning approach can eventually use natural language instructions to learn the target concept and play the game legally. Furthermore, we show that the learned semantic interpreter also generalizes to previously unseen instructions.     

The Representation of Numbers in Quantum Mechanics

Abstract. Earlier work on modular arithmetic of k-ary representations of length L of the natural numbers in quantum mechanics is extended here to k-ary representations of all natural numbers, and to integers and rational numbers. Since the length L is indeterminate, representations of states and operators using creation and annihilation operators for bosons and fermions are defined. Emphasis is on definitions and properties of operators corresponding to the basic operations whose properties are given by the axioms for each type of number. The importance of the requirement of efficient implementability for physical models of the axioms is emphasized. Based on this, successor operations for each value of j corresponding to +k ^j-1 are defined. It follows from the efficient implementability of these successors, which is the case for all computers, that implementation of the addition and multiplication operators, which are defined in terms of polynomially many iterations of the successors, should be efficient. This is not the case for definitions based on just the successor for j=1 . This is the only successor defined in the usual axioms of arithmetic.     

Near-optimal bounded-degree spanning trees

Random costsC(i, j) are assigned to the arcs of a complete directed graph onn labeled vertices. Given the cost matrixC _n =(C(i, j)), letT* _k =T* _k (C _n ) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal tok. Since it is NP-hard to findT* _k , we instead consider an efficient algorithm that finds a near-optimal spanning treeT _k ^a . If the edge costs are independent, with a common exponential(I) distribution, then, asn → ∞, $$E(Cost(T_k^a {\text{)) = }}E(Cost(T_k^* {\text{)) + }}o\left( 1 \right).$$ Upper and lower bounds forE(Cost(T* _k )) are also obtained fork≥2.     

Cops and Robbers from a distance

Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance k Cops and Robbers, where the cops win if at least one of them is of distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written c_k(G), equals the minimum number of cops needed to win at a given distance k. We study the parameter c_k from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded c_k(G) values and develop an O(n^2s+3) algorithm for determining if c_k(G)≤s for s fixed. We prove that if s is not fixed, then computing c_k(G) is NP-hard. Upper and lower bounds are found for c_k(G) in terms of the order of G. We prove that

     

Complexity of certain decision problems about congruential languages

Given an arbitrary finite Church-Rosser Thue system S, it is shown that the question of whether a given congruence class is finite is undecidable, and the question of whether every congruence class is finite is not even semidecidable (in fact, Π₂-complete). It is shown that the question of whether a given (resp. every) congruence class is a context-free language is at least as hard. Also, given a finite rewriting system over a commutative monoid, the question of whether every congruence class is finite is shown to be tractable. This contrasts with the known result that the question of whether a given congruence class is finite requires space at least exponential in the square root of the input length.     

Conjunctions of Unate DNF Formulas: Learning and Structure

A central topic in query learning is to determine which classes of Boolean formulas are efficiently learnable with membership and equivalence queries. We consider the class ^kconsisting of conjunctions ofkunate DNF formulas. This class generalizes the class ofk-clause CNF formulas and the class of unate DNF formulas, both of which are known to be learnable in polynomial time with membership and equivalence queries. We prove that ²can be properly learned with a polynomial number of polynomial-size membership and equivalence queries, but can be properly learned in polynomial time with such queries if and only if P=NP. Thus the barrier to properly learning ²with membership and equivalence queries is computational rather than informational. Few results of this type are known. In our proofs, we use recent results of Hellersteinet al.(1997,J. Assoc. Comput. Mach.43(5), 840–862), characterizing the classes that are polynomial-query learnable, together with work of Bshouty on the monotone dimension of Boolean functions. We extend some of our results to ^kand pose open questions on learning DNF formulas of small monotone dimension. We also prove structural results for ^k. We construct, for any fixedk2, a class of functionsfthat cannot be represented by any formula in ^k, but which cannot be “easily” shown to have this property. More precisely, for any functionfonnvariables in the class, the value offon any polynomial-size set of points in its domain is not a witness thatfcannot be represented by a formula in ^k. Our construction is based on BCH codes.     

Erzeugende Funktionen bei Spline-Interpolation mit äquidistanten Knoten

Using generating functions we obtain in the case ofn+1 equidistant data points a method for the calculation of the interpolating spline functions(x) of degree 2k+1 with boundary conditionss ^(κ) (x₀)=y ₀ ^(κ) ,s ^(κ) (x _n )=y _n ^(κ) , κ=1(1)k, which only needs the inversion of a matrix of orderk. The applicability of our method in the case of general boundary conditions is also mentioned.     

A Mixed DG Method for Linearized Incompressible Magnetohydrodynamics

We introduce and analyze a discontinuous Galerkin method for the numerical discretization of a stationary incompressible magnetohydrodynamics model problem. The fluid unknowns are discretized with inf-sup stable discontinuous ? _k ³ ?? _k?1 elements whereas the magnetic part of the equations is approximated by discontinuous ? _k ³ ?? _k+1 elements. We carry out a complete a-priori error analysis of the method and prove that the energy norm error is convergent of order k in the mesh size. These results are verified in a series of numerical experiments.     

Simulated annealing type algorithms for multivariate optimization

We study the convergence of a class of discrete-time continuous-state simulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the formX _k +1 =X _k ?a _k (▽U(X _k ) + ξ_k) +b _k W _k . HereU(·) is a smooth function on a compact subset of ? ^d , {ξ_k} is a sequence of ? ^d -valued random variables, {W _k } is a sequence of independent standardd-dimensional Gaussian random variables, and {a _k }, {b _k } are sequences of positive numbers which tend to zero. These algorithms arise by adding decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show under suitable conditions onU(·), {ξ _k }, {a _k }, and {b _k } thatX _k converges in probability to the set of global minima ofU(·). A careful treatment of howX _k is restricted to a compact set and its effect on convergence is given.     

Balancing Bounded Treewidth Circuits

We use algorithmic tools for graphs of small treewidth to address questions in complexity theory. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in arithmetic formulas of depth O(k ²logn). From this we derive an analogous statement for syntactically multilinear arithmetic circuits, which strengthens the central theorem of M. Mahajan and B.V.R. Rao (Proc. 33rd International Symposium on Mathematical Foundations of Computer Science, vol. 5162, pp. 455–466, 2008). We show our main construction has the following three applications:

• Bounded width arithmetic circuits of size n ^O(1) can be balanced to depth O(logn), provided chains of iterated multiplication in the circuit are of length O(1).
• Boolean bounded fan-in circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in formulas of depth O(k ²logn). This strengthens in the non-uniform setting the known inclusion that SC⁰?NC¹.
• We demonstrate treewidth restricted cases of Directed-Reachability and Circuit Value Problem that can be solved in LogDCFL.

We also give a construction showing, for both arithmetic and Boolean circuits, that any circuit of size n ^O(1) and treewidth O(log ⁱ n) can be simulated by a circuit of width O(log ⁱ⁺¹ n) and size n ^c , where c=O(1), if i=0, and c=O(loglogn) otherwise.     

Elastic net regularized dictionary learning for image classification

Dictionary learning plays a key role in image representation for classification. A multi-modal dictionary is usually learned from feature samples across different classes and shared in the feature encoding process. Ideally each atom in dictionary corresponds to a single class of images, while each class of images corresponds to a certain group of atoms. Image features are encoded as linear combinations of selected atoms in a given dictionary. We propose to use elastic net as regularizer to select atoms in feature coding and related dictionary learning process, which not only benefits from the sparsity similar as ?₁ penalty but also encourages a grouping effect that helps improve image representation. Experimental results of image classification on benchmark datasets show that with dictionary learned in the proposed way outperforms state-of-the-art dictionary learning algorithms.