waashk/dblp huggingface dataset:
martingale families and dimension in p. we introduce a new measure notion on small complexity classes (called f-measure), based on martingale families, that gets rid of some drawbacks of previous measure notions: it can be used to define dimension because martingale families can make money on all strings, and it yields random sequences with an equal frequency of 0's and 1's. on larger complexity classes (e and above), f-measure is equivalent to lutz resource-bounded measure. as applications to f-measure, we answer a question raised in [e. allender, m. strauss, measure on small complexity classes, with application for bpp, in: proc. of the 35th ann. ieee symp. on found. of comp. sci., 1994, pp. 807-818] by improving their result to: for almost every language a decidable in subexponential time, p^a=bpp^a. we show that almost all languages in pspace do not have small non-uniform complexity. we compare f-measure to previous notions and prove that martingale families are strictly stronger than @c-measure [e. allender, m. strauss, measure on small complexity classes, with application for bpp, in: proc. of the 35th ann. ieee symp. on found. of comp. sci., 1994, pp. 807-818], we also discuss the limitations of martingale families concerning finite unions. we observe that all classes closed under polynomial many-one reductions have measure zero in exp iff they have measure zero in subexp. we use martingale families to introduce a natural generalization of lutz resource-bounded dimension [j.h. lutz, dimension in complexity classes, in: proceedings of the 15th annual ieee conference on computational complexity, 2000, pp. 158-169] on p, which meets the intuition behind lutz's notion. we show that p-dimension lies between finite-state dimension and dimension on e. we prove an analogue of a theorem of eggleston in p, i.e. the class of languages whose characteristic sequence contains 1's with frequency @a, has dimension the shannon entropy of @a in p.
approximation algorithms for partially covering with edges. the edge dominating set (eds) and edge-cover (ec) problems are classical graph covering problems in which one seeks a minimum cost collection of edges which covers the edges or vertices, respectively, of a graph. we consider the generalized partial cover version of these problems, in which failing to cover an edge, in the eds case, or vertex, in the ec case, induces a penalty. given a bound on the total amount of penalties that we are permitted to pay, the objective is to find a minimum cost cover with respect to this bound. we give an 8/3-approximation for generalized partial eds. this result matches the best-known guarantee for the {0,1}-eds problem, a specialization in which only a specified set of edges need to be covered. moreover, 8/3 corresponds to the integrality gap of the natural formulation of the {0,1}-eds problem. our techniques can also be used to derive an approximation scheme for the generalized partial edge-cover problem, which is np-complete even though the uniform penalty version of the partial edge-cover problem is in p.
on the structure of graphs in the caucal hierarchy. we investigate the structure of graphs in the caucal hierarchy. we provide criteria concerning the degree of vertices or the length of paths which can be used to show that a given graph does not belong to a certain level of this hierarchy. each graph in the caucal hierarchy corresponds to the configuration graph of some higher-order pushdown automaton. the main part of the paper consists of a study of such configuration graphs. we provide tools to decompose and reassemble their runs, and we prove a pumping lemma for higher-order pushdown automata.
polyomino coloring and complex numbers. usually polyominoes are represented as subsets of the lattice z^2. in this paper we study a representation of polyominoes by gaussian integers. polyomino {(x"1,y"1),(x"2,y"2),...,(x"s,y"s)}@?z^2 is represented by the set {(x"1+iy"1),(x"2+iy"2),...,(x"s+iy"s)}@?z[i]. then we consider functions of type f:p->g from the set p of all polyominoes to an abelian group g, given by f(x,y)=(x+iy)^m(modv), where v is prime in z[i],1@?m
turing machines and bimachines. we associate the iterated block product of a bimachine with a deterministic turing machine. this allows us to introduce new algebraic notions to study the behavior of the turing machine. namely, we introduce double semidirect products through matrix multiplication of upper triangular matrices with coefficients in certain semigroups, which leads in turn to the study of the iterations of bimachines. by passing to the profinite (or projective) limit, we obtain an algebraic profinite description of the limit behavior of the turing machine. finally, we analyze the proof that all languages in np can be reduced to circuit sat from this viewpoint.
heuristic algorithms for two machine re-entrant flow shop. this paper focuses on a two machine re-entrant flow shop scheduling problem with the objective of minimizing makespan. in the re-entrant flow shop considered here, each job has the processing route (m"1, m"2, m"1, m"2, ..., m"1, m"2). we present heuristic algorithms, some are modified from existing algorithms and some are newly developed. extensive computational experiments are performed to evaluate the performance of the heuristics. results of the experiments show that the performance of heuristics is significantly affected by the distribution of workloads on machines and some of them are excellent.
a unified approach to finding good stable matchings in the hospitals/residents setting. the hospitals/residents (hr) problem is a many-to-one generalization of the stable marriage (sm) problem. researchers have been interested in variants of stable matchings that either satisfy a set of additional contraints or are optimal with respect to some cost function. in this paper, we show that broad classes of feasibility and optimization stable matching problems in the hr setting can be solved efficiently provided certain tasks (such as checking the feasibility of a stable matching or computing the cost of a stable matching) can also be done efficiently. to prove our results, we make use of an hr instance's meta-rotation poset to explore its stable matchings. an algorithm that can discover all the meta-rotations of the instance serves as a starting point for all our algorithms.
reconstruction of a word from a multiset of its factors. let d"k(w) be the multiset containing all factors of w of length k including repetitions. one of the main results is that if d"k(w)=d"k(v) for all k@?@?|w|2@?+1, then w=v. the bound @?|w|2@?+1 is optimal; however we will also show that if d"k(w)=d"k(v) for all k@?@?|w|2@?, then w and v are structurally similar.
on stabilizers of infinite words. the stabilizer of an infinite word w over a finite alphabet @s is the monoid of morphisms over @s that fix w. in this paper we study various problems related to stabilizers and their generators. we show that over a binary alphabet, there exist stabilizers with at least n generators for all n. over a ternary alphabet, the monoid of morphisms generating a given infinite word by iteration can be infinitely generated, even when the word is generated by iterating an invertible primitive morphism. stabilizers of strict epistandard words are cyclic when non-trivial, while stabilizers of ultimately strict epistandard words are always non-trivial. for this latter family of words, we give a characterization of stabilizer elements.
matrices of 3-iet preserving morphisms. we study matrices of morphisms preserving the family of words coding 3-interval exchange transformations. it is well known that matrices of morphisms preserving sturmian words (i.e. words coding 2-interval exchange transformations with the maximal possible factor complexity) form the monoid {m@?n^2^x^2|detm=+/-1}={m@?n^2^x^2|mem^t=+/-e}, where e=(01-10). we prove that in the case of exchange of three intervals, the matrices preserving words coding these transformations and having the maximal possible subword complexity belong to the monoid {m@?n^3^x^3|mem^t=+/-e,detm=+/-1}, where e=(011-101-1-10).
extension of brzozowski's derivation calculus of rational expressions to series over the free partially commutative monoids. we introduce an extension of the derivatives of rational expressions to expressions denoting formal power series over partially commuting variables. the expressions are purely noncommutative, however they denote partially commuting power series. the derivations (which are so-called @f-derivations) are shown to satisfy the commutation relations. our main result states that for every so-called rigid rational expression, there exists a stable finitely generated submodule containing it. moreover, this submodule is generated by what we call words, that is by products of letters and of pure stars. consequently this submodule is free and it follows that every rigid rational expression represents a recognizable series in k>. this generalizes the previously known property where the star was restricted to mono-alphabetic and connected series.
on the complexity of minimizing interference in ad-hoc and sensor networks. one of the most critical factors for lifetime and operability of ad-hoc and sensor networks is the limited amount of available energy. to this respect, minimizing the interference in the network (i.e., the overlapping of signals at network nodes) has certainly a positive effect, because it induces a reduction of the number of conflicting transmissions, and then results in an overall saving of energy consumption. along this direction, in this paper we study the computational hardness of several interference minimization problems which arise while supporting some classic network communication patterns such as broadcasting (one-to-all), gossiping (all-to-all), and symmetric gossiping (symmetric all-to-all). in particular, concerning the non-approximability results, we prove that for any of the above communication patterns, the prominent problem of minimizing the maximum interference experienced by any node in the network is hard to approximate within better than a logarithmic factor, unless np admits slightly superpolynomial time algorithms. on a positive side, we show that any approximation algorithm for the problem of minimizing the total transmission power assigned to the nodes in order to guarantee any of the above communication patterns, can be transformed, by maintaining the same performance ratio, into an approximation algorithm for the problem of minimizing the total interference experienced by all the nodes in the network.
determining the equivalence for one-way quantum finite automata. two quantum finite automata are equivalent if for any input string x the two automata accept x with equal probability. in this paper, we first focus on determining the equivalence for one-way quantum finite automata with control language (cl-1qfas) defined by bertoni et al., and then, as an application, we address the equivalence problem for measure-many one-way quantum finite automata (mm-1qfas) introduced by kondacs and watrous. more specifically, we obtain that: (i)two cl-1qfas a"1 and a"2 with control languages (regular languages) l"1 and l"2, respectively, are equivalent if and only if they are (c"1n"1^2+c"2n"2^2-1)-equivalent, where n"1 and n"2 are the numbers of states in a"1 and a"2, respectively, and c"1 and c"2 are the numbers of states in the minimal dfas that recognize l"1 and l"2, respectively. furthermore, if l"1 and l"2 are given in the form of dfas, with m"1 and m"2 states, respectively, then there exists a polynomial-time algorithm running in time o((m"1n"1^2+m"2n"2^2)^4) that takes as input a"1 and a"2 and determines whether they are equivalent. (ii)(as an application of item (i)): two mm-1qfas a"1 and a"2 with n"1 and n"2 states, respectively, are equivalent if and only if they are (3n"1^2+3n"2^2-1)-equivalent. furthermore, there is a polynomial-time algorithm running in time o((3n"1^2+3n"2^2)^4) that takes as input a"1 and a"2 and determines whether a"1 and a"2 are equivalent.
cryptographically-masked flows. cryptographic operations are essential for many security-critical systems. reasoning about information flow in such systems is challenging because typical (noninterference-based) information-flow definitions allow no flow from secret to public data. unfortunately, this implies that programs with encryption are ruled out because encrypted output depends on secret inputs: the plaintext and the key. however, it is desirable to allow flows arising from encryption with secret keys provided that the underlying cryptographic algorithm is strong enough. in this article we conservatively extend the noninterference definition to allow safe encryption, decryption, and key generation. to illustrate the usefulness of this approach, we propose (and implement) a type system that guarantees noninterference for a small imperative language with primitive cryptographic operations. the type system prevents dangerous program behavior (e.g., giving away a secret key or confusing keys and nonkeys), which we exemplify with secure implementations of cryptographic protocols. because the model is based on a standard noninterference property, it allows us to develop some natural extensions. in particular, we consider public-key cryptography and integrity, which accommodate reasoning about primitives that are vulnerable to chosen-ciphertext attacks.
efficient corona training protocols for sensor networks. phenomenal advances in nano-technology and packaging have made it possible to develop miniaturized low-power devices that integrate sensing, special-purpose computing, and wireless communications capabilities. it is expected that these small devices, referred to as sensors, will be mass-produced and deployed, making their production cost negligible. due to their small form factor and modest non-renewable energy budget, individual sensors are not expected to be gps-enabled. moreover, in most applications, exact geographic location is not necessary, and all that the individual sensors need is a coarse-grain location awareness. the task of acquiring such a coarse-grain location awareness is referred to as training. in this paper, two scalable energy-efficient training protocols are proposed for massively-deployed sensor networks, where sensors are initially anonymous and unaware of their location. the training protocols are lightweight and simple to implement; they are based on an intuitive coordinate system imposed onto the deployment area which partitions the anonymous sensors into clusters where data can be gathered from the environment and synthesized under local control.
on fractional dynamic faults with thresholds. unlike localized communication failures that occur on a fixed (although a priori unknown) set of links, dynamic faults can occur on any link. known also as mobile or ubiquitous faults, their presence makes many tasks difficult, if not impossible to solve, even in synchronous systems. in this paper, we introduce a new model for dynamic faults in synchronous distributed systems. this model includes as special cases the existing settings studied in the literature. we focus on the hardest setting of this model, called the simple threshold, where to be guaranteed that at least one message is delivered in a time step, the total number of transmitted messages in that time step must reach a threshold t@?c(g), where c(g) is the edge connectivity of the network. we investigate the problem of broadcasting under this model for the worst threshold t=c(g) in several classes of graphs, as well as in arbitrary networks. we design solution protocols, proving that broadcasting is possible even in this harsh environment. we analyze the time costs, showing that broadcasts can be completed in (low) polynomial time for several networks including rings (with or without knowledge of n), complete graphs (with or without a chordal sense of direction), hypercubes (with or without orientation), and constant-degree networks (with or without full topological knowledge).
solving difference equations whose coefficients are not transcendental. we consider a large class of sequences which are defined by systems of (possibly nonlinear) difference equations. a procedure for recursively enumerating the algebraic dependencies of such sequences is presented. also a procedure for solving linear difference equations with such sequences as coefficients is proposed. the methods are illustrated on some problems arising in the literature on special functions and combinatorial sequences.
complexity and approximation for precedence constrained scheduling problems with large communication delays. we investigate the problem of minimizing the makespan (resp. the sum of completion time) for the multiprocessor scheduling problem. we show that there is no hope of finding a @r-approximation with @r=2.
reversal complexity revisited. we study a generalized version of reversal bounded turing machines where, apart from several tapes on which the number of head reversals is bounded by r(n), there are several further tapes on which head reversals remain unrestricted, but size is bounded by s(n) (where n denotes the input length). recently [m. grohe, c. koch, n. schweikardt, tight lower bounds for query processing on streaming and external memory data, theoretical computer science 380 (1-2) (2007) 199-217; m. grohe, n. schweikardt, lower bounds for sorting with few random accesses to external memory, in: proc. pods'05, acm press, 2005, pp. 238-249], such machines were introduced as a formalization of a computation model that restricts random access to external memory and internal memory space. here, each of the tapes with a restriction on the head reversals corresponds to an external memory device, and the tapes of restricted size model internal memory. we use st(r(n),s(n),o(1)) to denote the class of all problems that can be solved by deterministic turing machines that comply to the above resource bounds. similarly, nst(...) and rst(...), respectively, are used for the corresponding nondeterministic and randomized classes. while previous papers focused on lower bounds for particular problems, including sorting, the set equality problem, and several query evaluation problems, the present paper addresses the relations between the (r,n) st(...)-classes and classical complexity classes and investigates the structural complexity of the (r,n) st(...)-classes. our main results are (1) a trade-off between internal memory space and external memory head reversals, (2) correspondences between the (r,n) st(...) classes and ''classical'' time-bounded, space-bounded, reversal-bounded, and circuit complexity classes, and (3) hierarchies of (r) st(...)-classes in terms of increasing numbers of head reversals on external memory tapes.
the complexity of tarski's fixed point theorem. tarski's fixed point theorem guarantees the existence of a fixed point of an order-preserving function f:l->l defined on a nonempty complete lattice (l,@?) [b. knaster, un theoreme sur les fonctions d'ensembles, annales de la societe polonaise de mathematique 6 (1928) 133-134; a. tarski, a lattice theoretical fixpoint theorem and its applications, pacific journal of mathematics 5 (1955) 285-309]. in this paper, we investigate several algorithmic and complexity-theoretic topics regarding tarski's fixed point theorem. in particular, we design an algorithm that finds a fixed point of f when it is given (l,@?) as input and f as an oracle. our algorithm makes o(log|l|) queries to f when @? is a total order on l. we also prove that when both f and (l,@?) are given as oracles, any deterministic or randomized algorithm for finding a fixed point of f makes an expected @w(|l|) queries for some (l,@?) and f.
complexity of unique list colorability. given a list l(v) for each vertex v, we say that the graph g is l-colorable if there is a proper vertex coloring of g where each vertex v takes its color from l(v). the graph is uniquelyk-list colorable if there is a list assignment l such that |l(v)|=k for every vertex v and the graph has exactly one l-coloring with these lists. mahdian and mahmoodian [m. mahdian, e.s. mahmoodian, a characterization of uniquely 2-list colorable graphs, ars combin. 51 (1999) 295-305] gave a polynomial-time characterization of uniquely 2-list colorable graphs. answering an open question from [m. ghebleh, e.s. mahmoodian, on uniquely list colorable graphs, ars combin. 59 (2001) 307-318; m. mahdian, e.s. mahmoodian, a characterization of uniquely 2-list colorable graphs, ars combin. 51 (1999) 295-305], we show that uniquely 3-list colorable graphs are unlikely to have such a nice characterization, since recognizing these graphs is @s"2^p-complete.
online scheduling of equal-processing-time task systems. we consider the problem of online scheduling a set of equal-processing-time tasks with precedence constraints so as to minimize the makespan. for arbitrary precedence constraints, it is known that any list scheduling algorithm has a competitive ratio of 2-1/m, where m is the number of machines. we show that for intree precedence constraints, hu's algorithm yields an asymptotic competitive ratio of 3/2.
group-strategyproof cost sharing mechanisms for makespan and other scheduling problems. classical results in economics show that no truthful mechanism can achieve budget balance and efficiency simultaneously. roughgarden and sundararajan recently proposed an alternative efficiency measure, which was subsequently used to exhibit that many previously known cost sharing mechanisms approximate both budget balance and efficiency. in this work, we investigate cost sharing mechanisms for combinatorial optimization problems using this novel efficiency measure, with a particular focus on scheduling problems. our contribution is threefold: first, for a large class of optimization problems that satisfy a certain cost-stability property, we prove that no budget balanced moulin mechanism can approximate efficiency better than @w(logn), where n denotes the number of players in the universe. second, we present a group-strategyproof cost sharing mechanism for the minimum makespan scheduling problem that is tight with respect to budget balance and efficiency. finally, we show a general lower bound on the budget balance factor for cost sharing methods, which can be used to prove a lower bound of @w(n) on the budget balance factor for completion and flow time scheduling objectives.
a relation between trinucleotide comma-free codes and trinucleotide circular codes. the comma-free codes and circular codes are two important classes of codes in code theory and in genetics. fifty years ago before the discovery of the genetic code, a trinucleotide (triletter) comma-free code was proposed for associating the codons of genes with the amino acids of proteins. more recently, in the last ten years, trinucleotide circular codes have been identified statistically in different genomes. here, we identify a relation between these two classes of trinucleotide codes by constructing a hierarchy of comma-free and circular codes.