waashk/dblp huggingface dataset:
the complexity of clique graph recognition. a complete set of a graph g is a subset of vertices inducing a complete subgraph. a clique is a maximal complete set. denote by c(g) the clique family of g. the clique graph of g, denoted by k(g), is the intersection graph of c(g). say that g is a clique graph if there exists a graph h such that g=k(h). the clique graph recognition problem asks whether a given graph is a clique graph. a sufficient condition was given by hamelink in 1968, and a characterization was proposed by roberts and spencer in 1971. however, the time complexity of the problem of recognizing clique graphs is a long-standing open question. we prove that the clique graph recognition problem is np-complete.
fast neighbor joining. reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. neighbor joining (nj) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. it takes the distances between n taxa and produces in @q(n^3) time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. in addition to performing well in practice, the nj algorithm has optimal reconstruction radius. the contribution of this paper is twofold: (1) we present an algorithm called fast neighbor joining (fnj) with optimal reconstruction radius and optimal run time complexity o(n^2) and (2) we present a greatly simplified proof for the correctness of nj. initial experiments show that fnj in practice has almost the same accuracy as nj, indicating that the property of optimal reconstruction radius has great importance to their good performance. moreover, we show how improved running time can be achieved for computing the so-called correction formulas.
deterministic bottom-up tree transducers and ground term rewrite systems. we show that it is decidable for any deterministic bottom-up tree transducer a and ground term rewrite system r, which one of the following conditions holds: (i) @t(a)@?@?"r^*, (ii) @?"r^*@?@t(a), (iii) @t(a)=@?"r^*, (iv) @t(a) and @?"r^* are incomparable. here @t(a) is the tree transformation induced by a, and @?"r^* is the congruence generated by r.
matrix columns allocation problems. orthogonal frequency division multiple access (ofdma) transmission technique is gaining popularity as a preferred technique in the emerging broadband wireless access standards. motivated by the ofdma transmission technique we define the following problem: let m be a matrix (over r) of size axb. given a vector of non-negative integers c->= such that @?c"j=a, we would like to allocate a cells in m such that (i) in each row of m there is a single allocation, and (ii) for each element c"i@?c-> there is a unique column in m which contains exactly c"i allocations. our goal is to find an allocation with minimal value, that is, the sum of all the a cells of m which were allocated is minimal. the nature of the suggested new problem is investigated in this paper. efficient algorithms are suggested for some interesting cases. for other cases of the problem, np-hardness proofs are given followed by inapproximability results.
exploration-exploitation tradeoff using variance estimates in multi-armed bandits. algorithms based on upper confidence bounds for balancing exploration and exploitation are gaining popularity since they are easy to implement, efficient and effective. this paper considers a variant of the basic algorithm for the stochastic, multi-armed bandit problem that takes into account the empirical variance of the different arms. in earlier experimental works, such algorithms were found to outperform the competing algorithms. we provide the first analysis of the expected regret for such algorithms. as expected, our results show that the algorithm that uses the variance estimates has a major advantage over its alternatives that do not use such estimates provided that the variances of the payoffs of the suboptimal arms are low. we also prove that the regret concentrates only at a polynomial rate. this holds for all the upper confidence bound based algorithms and for all bandit problems except those special ones where with probability one the payoff obtained by pulling the optimal arm is larger than the expected payoff for the second best arm. hence, although upper confidence bound bandit algorithms achieve logarithmic expected regret rates, they might not be suitable for a risk-averse decision maker. we illustrate some of the results by computer simulations.
covering graphs with few complete bipartite subgraphs. we consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the biclique partition problem is defined similarly with the additional condition that the bicliques are required to be mutually edge-disjoint. the biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques, the biclique vertex-partition problem is defined similarly with the additional condition that the bicliques are required to be mutually vertex-disjoint. all these four problems are known to be np-complete even if the given graph is bipartite. in this paper, we investigate them in the framework of parameterized complexity: do the problems become easier if k is assumed to be small? we show that, considering k as the parameter, the first two problems are fixed-parameter tractable, while the latter two problems are not fixed-parameter tractable unless p=np.
truthful mechanisms for two-range-values variant of unrelated scheduling. in this paper, we consider a restricted variant of the scheduling problem, where the machines are the strategic players. for this multi-parameter mechanism design problem, the only known truthful mechanisms use task independent allocation algorithms and only have approximation ratio o(m) [n. nisan, a. ronen. algorithmic mechanism design (extended abstract), in: stoc'99: proceedings of the thirty-first annual acm symposium on theory of computing, acm, new york, ny, usa, 1999. pp. 129-140; a. mu'alem, m. schapira, setting lower bounds on truthfulness: extended abstract, in: soda'07: proceedings of the eighteenth annual acm-siam symposium on discrete algorithms, society for industrial and applied mathematics, philadelphia, pa, usa, 2007, pp. 1143-1152; p. lu, c. yu, an improved randomized truthful mechanism for scheduling unrelated machines, in: 25th international symposium on theoretical aspects of computer science, stacs, 2008, pp. 527-538; p. lu, c. yu, randomized truthful mechanisms for scheduling unrelated machines, in: c.h. papadimitriou, s. zhang (eds.), proceedings of wine, in: lecture notes in computer science, vol. 5385, springer, 2008, pp. 402-413]. lavi and swamy first use the cycle monotone condition and design a 3-approximation truthful mechanism for a two value variant in [r. lavi, c. swamy, truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, in: ec'07: proceedings of the 8th acm conference on electronic commerce, acm, new york, ny, usa, 2007, pp. 252-261], where the processing time of task j on machine i, say t"i"j, can only be either a lower value l"j or a higher value h"j. we consider a generalized variant, where t"i"j lies in [l"j,l"j(1+@e)]@?[h"j,h"j(1+@e)] and @e is a parameter satisfying some condition. we consider two special cases, case a when h"j/l"j>2,@?j and case b when h"j/l"j@?2,@?j, and give randomized truthful mechanisms with approximation ratio 4(1+@e) for both cases. based on these two cases' results, we are also able to deal with the general case of our two-range-values scheduling problem. we use a combination of two mechanisms, which is also a novel method in mechanism design for scheduling problems, and finally we give a randomized truthful mechanism with approximation ratio 7(1+@e). although the generalization seems a little incremental, we actually use a very novel technique in the key step of proving truthfulness for case a, as well as a new mechanism scheme for case b. besides, the results in this paper are the first truthful mechanisms with constant approximation ratios when a machine (player) can report infinitely possible values, which is quite different from the two value variant, in which only finite values are available. furthermore, together with lavi and swamy's work, our results suggest that such a task-dependent approach can really do much better for the scheduling unrelated machines problem.
improved constructions of mixed state quantum automata. quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. it was proved earlier by a. ambainis and r. freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. there was an unpublished ''folk theorem'' proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. it was not known whether the super-exponential advantage of quantum automata is really achievable. we prove that there is an infinite sequence of distinct integers n, languages l"n, and quantum finite automata with mixed states with 5n states recognizing language l"n with probability 34, while any deterministic finite automaton recognizing l"n needs at least e^o^(^n^l^n^n^) states. unfortunately, the alphabet for these languages grows with n. in order to prove a similar result for languages in a fixed alphabet we consider a counterpart of hamming codes for permutations of finite sets, i.e. sets of permutations such that any two distinct permutations in the set have hamming distance at least d. the difficulty arises from the fact that in the traditional hamming codes for binary strings, positions in the string are independent while positions in a permutation are not independent. for instance, any two permutations of the same set either coincide or their hamming distance is at least 2. the main combinatorial problem still remains open.
on a class of languages recognizable by probabilistic reversible decide-and-halt automata. we analyze the properties of probabilistic reversible decide-and-halt automata (dh-pra) and show that there is a strong relationship between dh-pra and 1-way quantum automata. we show that a general class of regular languages is not recognizable by dh-pra by proving that two ''forbidden'' constructions in minimal deterministic automata correspond to languages not recognizable by dh-pra. the shown class is identical to a class known to be not recognizable by 1-way quantum automata. we also prove that the class of languages recognizable by dh-pra is not closed under union and other non-trivial boolean operations.
a note on approximate nash equilibria. in view of the intractability of finding a nash equilibrium, it is important to understand the limits of approximation in this context. a subexponential approximation scheme is known [richard j. lipton, evangelos markakis, aranyak mehta, playing large games using simple strategies, in: ec, 2003], and no approximation better than 14 is possible by any algorithm that examines equilibria involving fewer than logn strategies [ingo althofer, on sparse approximations to randomized strategies and convex combinations, linear algebra and its applications (1994) 199]. we give a simple, linear-time algorithm examining just two strategies per player and resulting in a 12-approximate nash equilibrium in any 2-player game. for the more demanding notion of approximately well supported nash equilibrium due to [constantinos daskalakis, paul w. goldberg, christos h. papadimitriou, the complexity of computing a nash equilibrium, siam journal on computing (in press) preliminary version appeared in stoc (2006)] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0 or 1), and that an approximation of 56 is possible, contingent upon a graph-theoretic conjecture. subsequent work extends the 14 impossibility result of ingo althofer's paper, as mentioned above, to 12 [tomas feder, hamid nazerzadeh, amin saberi, approximating nash equilibria using small-support strategies, in: ec, 2007], making our 12-approximate nash equilibrium algorithm optimal among the algorithms that only consider mixed strategies of sublogarithmic size support. moreover, techniques similar to our techniques for approximately well supported nash equilibria are used in [spyros kontogiannis, paul g. spirakis, efficient algorithms for constant well supported approximate equilibria in bimatrix games, in: icalp, 2007] for obtaining an efficient algorithm for 0.658-approximately well supported nash equilibria, unconditionally.
inapproximability of survivable networks. in the survivable network design problem (sndp) one seeks to find a minimum cost subgraph that satisfies prescribed node-connectivity requirements. we give a novel approximation ratio preserving reduction from directed sndp to undirected sndp. our reduction extends and widely generalizes as well as significantly simplifies the main results of [g. kortsarz, r. krauthgamer, j.r. lee, hardness of approximation for vertex-connectivity network design problems, siam journal on computing 33 (3) (2004) 704-720]. using it, we derive some new hardness of approximation results, as follows. we show that directed and undirected variants of sndp and of k-connected subgraph are equivalent w.r.t. approximation, and that a @r-approximation for undirected rooted sndp implies a @r-approximation for directed steiner tree.
classifying rendezvous tasks of arbitrary dimension. the rendezvous is a type of distributed decision tasks including many well-known tasks such as set agreement, simplex agreement, and approximation agreement. an n-dimensional rendezvous task, n>=1, allows n+2 distinct input values, and each execution produces at most n+2 distinct output values. a rendezvous task is said to implement another if an instance of its solution, followed by a protocol based on shared read/write registers, solves the other. the notion of implementation induces a classification of rendezvous tasks of every dimension: two tasks belong to the same class if they implement each other. previous work on classifying rendezvous tasks only focused on 1-dimensional ones. this paper solves an open problem by presenting the classification of nice rendezvous of arbitrary dimension. an n-dimensional rendezvous task is said to be nice if the qth reduced homology group of its decision space is trivial for q
separating models of learning with faulty teachers. we study the power of two models of faulty teachers in valiant's pac learning model and angluin's exact learning model. the first model we consider is learning from an incomplete membership oracle introduced by angluin and slonim [d. angluin, d.k. slonim, randomly fallible teachers: learning monotone dnf with an incomplete membership oracle, machine learning 14 (1) (1994) 7-26]. in this model, the answers to a random subset of the learner's membership queries may be missing. the second model we consider is random persistent classification noise in membership queries introduced by goldman, kearns and schapire [s. goldman, m. kearns, r. schapire, exact identification of read-once formulas using fixed points of amplification functions, siam journal on computing 22 (4) (1993) 705-726]. in this model, the answers to a random subset of the learner's membership queries are flipped. we show that in both the pac and the exact learning models the incomplete membership oracle is strictly stronger than the noisy membership oracle under the assumption that the problem of pac learning parities with random classification noise is intractable. we also show that under the standard cryptographic assumptions the incomplete membership oracle is strictly weaker than the perfect membership oracle. this generalizes the result of simon [h. simon, how many missing answers can be tolerated by query learners? theory of computing systems 37 (1) (2004) 77-94] and resolves an open question of bshouty and eiron [n. bshouty, n. eiron, learning monotone dnf from a teacher that almost does not answer membership queries, journal of machine learning research 3 (2002) 49-57].
tight rank lower bounds for the sherali-adams proof system. we consider a proof (more accurately, refutation) system based on the sherali-adams (sa) operator associated with integer linear programming. if f is a cnf contradiction that admits a resolution refutation of width k and size s, then we prove that the sa rank of f is @?k and the sa size of f is @?(k+1)s+1. we establish that the sa rank of both the pigeonhole principle php"n"-"1^n and the least number principle lnp"n is n-2. since the sa refutation system rank-simulates the refutation system of lovasz-schrijver without semidefinite cuts (ls), we obtain as a corollary linear rank lower bounds for both of these principles in ls.
collapsing words, permutation conditions and coherent colorings of trees. given a word w over a finite alphabet @s and a finite deterministic automaton a=, the inequality |@d(q,w)|@?|q|-n means that under the natural action of the word w the image of the state set q is reduced by at least n states. a word w is n-collapsing if this inequality holds for any deterministic finite automaton that satisfies such an inequality for at least one word. in this paper we prove that the problem of recognizing n-collapsing words is generally co-np-complete, while restricted to 2-collapsing words over 2-element alphabet it belongs to p. this is connected with introducing a new approach to collapsing words, which is shown to be much more effective in solving various problems in the area. it leads to interesting connections with combinatorial problems concerning solving systems of permutation conditions on one hand, and coloring trees with distinguished nodes on the other hand.
on parameterized complexity of the multi-mcs problem. we introduce the maximum common subgraph problem for multiple graphs (multi-mcs) inspired by various biological applications such as multiple alignments of gene sequences, protein structures, metabolic pathways, or protein-protein interaction networks. multi-mcs is a generalization of the two-graph maximum common subgraph problem (mcs). on the basis of the framework of parameterized complexity theory, we derive the parameterized complexity of multi-mcs for various parameters for different classes of graphs. for example, for directed graphs with labeled vertices, we prove that the parameterized m-multi-mcs problem is w[2]-hard, while the parameterized k-multi-mcs problem is w[t]-hard (@?t>=1), where m and k are the size of the maximum common subgraph and the number of multiple graphs, respectively. we show similar results for other parameterized versions of the multi-mcs problem for directed graphs with vertex labels and undirected graphs with vertex and edge labels by giving linear fpt reductions of the problems from parameterized versions of the longest common subsequence problem. likewise, for unlabeled undirected graphs, we show that a parameterized version of the multi-mcs problem with a fixed number of input graphs is w[1]-complete by showing a linear fpt reduction to and from a parameterized version of the maximum clique problem.
deterministic and unambiguous two-dimensional languages over one-letter alphabet. the paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-letter alphabet. the family drec(1) of deterministic languages over a one-letter alphabet is characterized as both l(dota)(1), the class of languages accepted by deterministic on-line tessellation acceptors, and l(2afa)(1), the class of languages recognized by 2-way alternating finite automata. we show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-letter alphabet. in particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-letter alphabet. finally we show that drec(1) is complex enough not to be characterized in terms of classical operations.
mathematical logic and quantum finite state automata. this paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. as is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. after a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.
paths, cycles and circular colorings in digraphs. in this paper, we consider the paths, cycles and circular colorings of digraphs. let d be a digraph. we show that if the complement of d contains no directed hamiltonian cycle, then @g"c(d)=@g(d). also, we give two results which concern directed paths meeting all colors in digraphs with proper colorings.
efficient probability amplification in two-way quantum finite automata. in classical computation, one only needs to sequence o(log1@e) identical copies of a given probabilistic automaton with one-sided error p0}, kondacs and watrous use a different probability amplification method, which yields machines with o((1@e)^2) states, and with runtime o(1@e|w|), where w is the input string. in this paper, we examine significantly more efficient techniques of probability amplification. one of our methods produces machines which decide l in o(|w|) time (i.e. the running time does not depend on the error bound) and which have o((1@e)^2^c) states for any given constant c>1. other methods, yielding machines whose state complexities are polylogarithmic in 1@e, including one which halts in o(log(1@e)|w|) time, are also presented.
holographic algorithms: the power of dimensionality resolved. valiant's theory of holographic algorithms is a novel methodology to achieve exponential speed-ups in computation. a fundamental parameter in holographic algorithms is the dimension of the linear basis vectors. we completely resolve the problem of the power of higher dimensional bases. we prove that 2-dimensional bases are universal for holographic algorithms.
coloring artemis graphs. we consider the class of graphs that contain no odd hole, no antihole, and no ''prism'' (a graph consisting of two disjoint triangles with three disjoint paths between them). we give an algorithm that can optimally color the vertices of these graphs in time o(n^2m).
universal algebra and hardness results for constraint satisfaction problems. we present algebraic conditions on constraint languages @c that ensure the hardness of the constraint satisfaction problem csp(@c) for complexity classes l, nl, p, np and mod"pl. these criteria also give non-expressibility results for various restrictions of datalog. furthermore, we show that if csp(@c) is not first-order definable then it is l-hard. our proofs rely on tame congruence theory and on a fine-grain analysis of the complexity of reductions used in the algebraic study of csp. the results pave the way for a refinement of the dichotomy conjecture stating that each csp(@c) lies in p or is np-complete and they match the recent classification of [e. allender, m. bauland, n. immerman, h. schnoor, h. vollmer, the complexity of satisfiability problems: refining schaefer's theorem, in: proc. 30 th math. found. of comp. sci., mfcs'05, 2005, pp. 71-82] for boolean csp. we also infer a partial classification theorem for the complexity of csp(@c) when the associated algebra of @c is the full idempotent reduct of a preprimal algebra.