waashk/dblp huggingface dataset:
applications of regularized least squares to pattern classification. we survey a number of recent results concerning the behaviour of algorithms for learning classifiers based on the solution of a regularized least-squares problem.
on coding labeled trees. we consider the problem of coding labeled trees by means of strings of node labels. different codes have been introduced in the literature by pr&uuml;fer, neville, and deo and micikevičius. for all of them, we show that both coding and decoding can be reduced to integer (radix) sorting, closing several open problems within a unified framework that can be applied both in a sequential and in a parallel setting. our sequential coding and decoding schemes require optimal o(n) time when applied to n-node trees, yielding the first linear time decoding algorithm for a code presented by neville. these schemes can be parallelized on the erew pram model, so as to work in o(logn) time with cost o(n), , or o(nlogn), depending on the code and on the operation: in all cases, they either match or improve the performances of the best ad hoc approaches known so far.
a unified access bound on comparison-based dynamic dictionaries. we present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. the unified bound specifies that it is quick to access an element that is near a recently accessed element. more precisely, if w(y) distinct elements have been accessed since the last access to element y, and d(x,y) denotes the rank distance between x and y among the current set of elements, then the amortized cost to access element x is o(minylog[w(y)+d(x,y)+2]). this property generalizes the working-set and dynamic-finger properties of splay trees.
complementation of rational sets on scattered linear orderings of finite rank. in a preceding paper [v. bruy&egrave;re, o. carton, automata on linear orderings, in: j. sgall, a. pultr, p. kolman (eds.), mfcs'2001, in: lect. notes in comput. sci., vol. 2136, 2001, pp. 236-247. igm report 2001-12], automata have been introduced for words indexed by linear orderings. these automata are a generalization of automata for finite, infinite, bi-infinite, and even transfinite words studied by b&uuml;chi. kleene's theorem has been generalized to these words. we show that deterministic automata do not have the same expressive power. despite this negative result, we prove that rational sets of words of finite ranks are closed under complementation.
centralized asynchronous broadcast in radio networks. we study asynchronous broadcasting in packet radio networks. a radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. an asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. the correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. a protocol specifies how many times the source message is to be retransmitted by each node. the total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. we study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. the amount of work necessary to make a protocol correct may have to be exponential in the size of network. there is a polynomial-time algorithm to find a broadcast protocol for a given network. we show that certain problems about broadcasting protocols for given networks are complete in np and co-np complexity classes.
ockham's razor, empirical complexity, and truth-finding efficiency. the nature of empirical simplicity and its relationship to scientific truth are long-standing puzzles. in this paper, empirical simplicity is explicated in terms of empirical effects, which are defined in terms of the structure of the inference problem addressed. problem instances are classified according to the number of empirical effects they present. simple answers are satisfied by simple worlds. an efficient solution achieves the optimum worst-case cost over each complexity class with respect to such costs as the number of retractions or errors prior to convergence and elapsed time to convergence. it is shown that always choosing the simplest theory compatible with experience and hanging on to it while it remains the simplest is both necessary and sufficient for efficiency.
feedback vertex sets in mesh-based networks. in this paper, we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. the problem is np-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. in this paper, the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes, and pyramid networks. for the two-dimensional meshes of trees the results are optimal; for the higher-dimensional meshes of trees and the tree of meshes the results are asymptotically optimal. for the pyramid networks, there remains a small factor between the upper and the lower bounds.
a comparison of simulated annealing with a simple evolutionary algorithm on pseudo-boolean functions of unitation. the development in the area of randomized search heuristics has shown the importance of a rigorous theoretical analysis of the performance of these heuristics. unfortunately, the analysis of the expected optimization time of a specific algorithm has in general no implications on the behaviour of other algorithms - even if they differ only in some aspects. indeed, small differences may imply large differences in the optimization time. hence, it is an important issue to compare fundamental heuristics and to find out for which problems they behave in such a similar way that results on one heuristic can be transferred to the other one and to describe problems where they behave quite differently. such an approach is performed here to the simple and well-known (1+1) ea, which is based on elitist selection and a global search operator, and simulated annealing, which is based on nonelitist selection and a local search operator.
swapping a failing edge of a shortest paths tree by minimizing the average stretch factor. we consider a two-edge connected, undirected graph g=(v,e), with n nodes and m non-negatively real weighted edges, and a single source shortest paths tree (spt) t of g rooted at an arbitrary node r. if an edge in t is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge, instead of rebuilding a new optimal spt from scratch. in the past, several optimality criteria have been considered to select a best possible swap edge. in this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. to this respect, we present an o(mlog2n) time and o(m) space algorithm to find a best swap edge for every edge of t, thus improving for m=o(n2/log2n) the previously known o(n2) time and space complexity algorithm.
a lower bound on complexity of optimization on the wiener space. this paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. the complexity is studied in the average case under a conditioned wiener measure. we show that to obtain an error of at most &epsilon;, on the order of loglog(1/&epsilon;)log(1/&epsilon;) function evaluations are required.
autopoietic automata: complexity issues in offspring-producing evolving processes. we introduce a new formal computational model designed for studying the information transfer among the generations of offspring-producing evolving machines - so-called autopoietic automata. these can be seen as nondeterministic finite state transducers whose ''program'' can become a subject of their own processing. an autopoietic automaton can algorithmically generate an offspring controlled by a program which is a modification of its parent's program. autopoietic automata offer a neat framework for investigating computational and complexity issues in the evolutionary self-reproducing processes. we show that the computational power of lineages of autopoietic automata is equal to that of an interactive nondeterministic turing machine. we also prove that there exists an autopoietic automaton giving rise to an unlimited evolution, provided that suitable inputs are delivered to individual automata. however, the problem of sustainable evolution, asking whether for an arbitrary autopoietic automaton and arbitrary inputs there is an infinite lineage of its offspring, is undecidable.
state complexity of combined operations. we study the state complexity of combined operations. two particular combined operations are studied: star of union and star of intersection. it is shown that the state complexity of a combined operation is not necessarily similar to the combination of the individual state complexities of the participating operations.
approximation algorithm for hotlink assignment in the greedy model. link-based information structures such as the web can be enhanced through the addition of hotlinks. assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. in order to access a particular node, the user must follow a path leading to it from the root. by adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. the hotlink assignment problem involves finding a set of hotlinks (with at most k=o(1) hotlinks emanating from every node) maximizing the gain in the expected cost. the paper addresses this problem in two user models, namely, the traditional clairvoyant user model employed in [p. bose, j. czyzowicz, l. gasieniec, e. kranakis, d. krizanc, a. pelc, m.v. martin, strategies for hotlink assignments, in: proc. 11th symp. on algorithms and computation, 2000, pp. 23-34; e. kranakis, d. krizanc, s. shende, approximating hotlink assignments, in: proc. 12th symp. on algorithms and computation, 2001, pp. 756-767; p. bose, d. krizanc, s. langerman, p. morin, asymmetrical communication protocols via hotlink assignments, in: proc. 9th colloq. on structural information and communication complexity, 2002, pp. 33-39; r. matichin, d. peleg, approximation algorithm for hotlink assignments in web directories, in: proc. workshop on algorithms and data structures, 2003, pp. 271-280] and the more realistic greedy user model recently introduced in [o. gerstel, s. kutten, r. matichin, d. peleg, hotlink enhancement algorithms for web directories, in: proc. 14th symp. on algorithms and computation, 2003, pp. 68-77], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on rooted directed trees.
long-lived rambo: trading knowledge for communication. shareable data services providing consistency guarantees, such as atomicity (linearizability), make building distributed systems easier. however, combining linearizability with efficiency in practical algorithms is difficult. a reconfigurable linearizable data service, called rambo, was developed by lynch and shvartsman. this service guarantees consistency under dynamic conditions involving asynchrony, message loss, node crashes, and new node arrivals. the specification of the original algorithm is given at an abstract level aimed at concise presentation and formal reasoning about correctness. the algorithm propagates information by means of gossip messages. if the service is in use for a long time, the size and the number of gossip messages may grow without bound. this paper presents a consistent data service for long-lived objects that improves on rambo in two ways: it includes an incremental communication protocol and a leave service. the new protocol takes advantage of the local knowledge, and carefully manages the size of messages by removing redundant information, while the leave service allows the nodes to leave the system gracefully. the new algorithm is formally proved correct by forward simulation using levels of abstraction. an experimental implementation of the system was developed for networks-of-workstations. the paper also includes selected analytical and preliminary empirical results that illustrate the advantages of the new algorithm.
spanners for bounded tree-length graphs. this paper concerns construction of additive stretched spanners with few edges for n-vertex graphs having a tree-decomposition into bags of diameter at most @d, i.e., the tree-length @d graphs. for such graphs we construct additive 2@d-spanners with o(@dn+nlogn) edges, and additive 4@d-spanners with o(@dn) edges. this provides new upper bounds for chordal graphs for which @d=1. we also show a lower bound, and prove that there are graphs of tree-length @d for which every multiplicative @d-spanner (and thus every additive (@d-1)-spanner) requires @w(n^1^+^1^/^@q^(^@d^)) edges.
circuit principles and weak pigeonhole variants. this paper considers the relational versions of the surjective, partial surjective, and multifunction weak pigeonhole principles for pv, @?"1^b, @?"1^b, and b(@?"1^b) formulas as well as relativizations of these formulas to higher levels of the bounded arithmetic hierarchy. we show that the partial surjective weak pigeonhole principle for @?"1^b formulas implies that for each k there is a string of length 2^2^n^^^k which is hard to block-recognize by circuits of size n^k. these principles in turn imply the partial surjective principle for @?"1^b formulas. we show that the surjective weak pigeonhole principle for b(@?"1^b) formulas in s"2^1 implies our hard-string principle which in turn implies the surjective weak pigeonhole principle for @?"1^b formulas. we introduce a class of predicates corresponding to poly-log length iterates of polynomial time computable predicates and show that over s"2^1, the multifunction weak pigeonhole principle for such predicates is equivalent to an ''iterative'' circuit block-recognition principle. a consequence of this is that if s"2^1 proves this principle then rsa is vulnerable to polynomial time attacks.
query-monotonic turing reductions. we study reductions that limit the extreme adaptivity of turing reductions. in particular, we study reductions that make a rapid, structured progression through the set to which they are reducing: each query is strictly longer (shorter) than the previous one. we call these reductions query-increasing (query-decreasing) turing reductions. we also study query-nonincreasing (query-nondecreasing) turing reductions. these are turing reductions in which the sequence of query lengths is nonincreasing (nondecreasing). we ask whether these restrictions in fact limit the power of reductions. we prove that query-increasing and query-decreasing turing reductions are incomparable with (that is, are neither strictly stronger than nor strictly weaker than) truth-table reductions and are strictly weaker than turing reductions. in addition, we prove that query-nonincreasing and query-nondecreasing turing reductions are strictly stronger than truth-table reductions and strictly weaker than turing reductions. despite the fact that we prove query-increasing and query-decreasing turing reductions to in the general case be strictly weaker than turing reductions, we identify a broad class of sets a for which any set that turing reduces to a will also reduce to a via both query-increasing and query-decreasing turing reductions. in particular, this holds for all tight paddable sets, where a set is said to be tight paddable exactly if it is paddable via a function whose output length is bounded tightly both from above and from below in the length of the input. we prove that many natural np-complete problems such as satisfiability, clique, and vertex cover are tight paddable.
the kolmogorov complexity of infinite words. we present a brief survey of results on relations between the kolmogorov complexity of infinite strings and several measures of information content (dimensions) known from dimension theory, information theory or fractal geometry. special emphasis is placed on bounds on the complexity of strings in constructively given subsets of the cantor space. finally, we compare the kolmogorov complexity to the subword complexity of infinite strings.
the $-calculus process algebra for problem solving: a paradigmatic shift in handling hard computational problems. the $-calculus is the extension of the &pi;-calculus, built around the central notion of cost and allowing infinity in its operators. we propose the $-calculus as a more complete model for problem solving to provide a support to handle intractability and undecidability. it goes beyond the turing machine model. we define the semantics of the $-calculus using a novel optimization method (the k&omega;-optimization), which approximates a nonexisting universal search algorithm and allows the simulation of many other search methods. in particular, the notion of total optimality has been utilized to provide an automatic way to deal with intractability of problem solving by optimizing together the quality of solutions and search costs. the sufficient conditions needed for completeness, optimality and total optimality of problem solving search are defined. a very flexible classification scheme of problem solving methods into easy, hard and solvable in the limit classes has been proposed. in particular, the third class deals with non-recursive solutions of undecidable problems. the approach is illustrated by solutions of some intractable and undecidable problems. we also briefly overview two possible implementations of the $-calculus.
time efficient centralized gossiping in radio networks. in this paper we study the gossiping problem (all-to-all communication) in radio networks where all nodes are aware of the network topology. we start our presentation with a deterministic gossiping algorithm that works in at most n units of time in any radio network of size n. this algorithm is optimal in the worst case scenario since there exist radio network topologies, such as lines, stars and complete graphs in which radio gossiping cannot be completed in less than n communication rounds. furthermore, we show that there does not exist any radio network topology in which the gossiping task can be solved in less than @?log(n-1)@?+2 rounds. we also show that this lower bound can be matched from above for a fraction of all possible integer values of n, and for all other values of n we propose a solution which accomplishes gossiping in @?log(n-1)@?+2 rounds. then we show an almost optimal radio gossiping algorithm in trees, which misses the optimal time complexity by a single round. finally, we study asymptotically optimal o(d)-time gossiping (where d is the diameter of the network) in graphs with the maximum degree @d=o(d^1^-^1^/^(^i^+^1^)log^in), for any integer constant i>=0 and d large enough.
algorithmic complexity as a criterion of unsolvability. there is a dependency between computability of algorithmic complexity and decidability of different algorithmic problems. it is known that computability of the algorithmic complexity c(x) is equivalent to decidability of the halting problem for turing machines. here we extend this result to the realm of superrecursive algorithms, considering algorithmic complexity for inductive turing machines. we study two types of algorithmic complexity: recursive (classical) and inductive algorithmic complexities. relations between these types of algorithmic complexity and decidability of algorithmic problems for turing machines and inductive turing machines are considered. in particular, it is demonsrated that computability of algorithmic complexity is equivalent not only to decidability of the halting problem, but also to decidability by inductive turing machines of the first order of many other problems for turing machines, such as: if a turing machine computes a recursive (total) function; if a turing machine gives no result only for n inputs; if a turing machine gives results only for n inputs.
a simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms. the main focus of this paper is the analysis of a simple randomized scheme for constructing low-weight k-connected spanning subgraphs. in this paper, we focus on the metric graph. we use the term metric graph for a complete graph with metric weights. we first show that our scheme gives a simple approximation algorithm to construct a minimum-weight k-connected spanning subgraph in a metric graph, an np-hard problem. we show that our algorithm gives an approximation ratio of o(klogn) for a metric graph, o(k) for a random graph with nodes uniformly randomly distributed in [0,1]2 and for a complete graph with random edge weights u(0,1). we show that our scheme is optimal with respect to the amount of "local information" needed to compute any connected spanning subgraph. we then show that our scheme can be applied to design an efficient distributed algorithm for constructing such an approximate k-connected spanning subgraph (for any k≥1) in a point-to-point distributed model, where the processors form a complete network. our algorithm takes time and an expected number of messages. our result in conjunction with a result of korach et al. [e. korach, s. moran, s. zaks, the optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors, siam journal on computing 16 (2) (1987) 231-236] implies that the expected message complexity of our algorithm is significantly better than the best distributed algorithm that finds an optimal k-connected subgraph. we also show that for geometric instances, our randomized scheme constructs low-degree k-connected spanning subgraphs which have o(klogn) maximum degree, with high probability.
alphabet-independent linear-time construction of compressed suffix arrays using o(nlogn)-bit working space. the suffix array is a fundamental index data structure in string algorithms and bioinformatics, and the compressed suffix array (csa) and the fm-index are its compressed versions. many algorithms for constructing these index data structures have been developed. recently, hon et al. [w.k. hon, k. sadakane, w.k. sung, breaking a time-and-space barrier in constructing full-text indices, in: proceedings of the 44th annual ieee symposium on foundations of computer science, 2003, pp. 251-260] proposed a construction algorithm using o(nloglog|σ|) time and o(nlog|σ|)-bit working space, which is the fastest algorithm using o(nlog|σ|)-bit working space. in this paper we give an efficient algorithm to construct the index data structures. our algorithm constructs the suffix array, the csa, the fm-index, and burrows-wheeler transform using alphabet-independent o(n) time and -bit working space, where &alpha;=log32. our algorithm takes less time and more space than hon et al.'s algorithm. our algorithm uses least working space among alphabet-independent linear-time algorithms.