We study the epigenetic consensus problem, in which simple processors move across and modify a shared memory, seeking to achieve consensus across the cells of the memory. The memory topology is a ring with the cells initialised to 0 or 1. The ring is traversed by multiple processors moving clockwise in synchronous steps. Each processor belongs to one of four types: There are two types of erasers that erase either memory cells holding a 0 adjacent to a 1 or those holding a 1 adjacent to a 0. There are also two types of writers; those writing 1 or those writing 0 into empty cells.We are interested whether and how fast the above process converges to a consensus state where all memory cells have the same value. The origin of this process lies in biology, in the modelling of the activation and deactivation of DNA sequences. A variant of this process has been introduced and studied by Rashid, Taubenfeld, and Bar-Joseph.The convergence properties of the process depend on the initialisation of the shared memory, as well as on the number and types of processors and their initial locations. We show that, with adversarial initial processor positions, consensus cannot be reached.Having observed that a deterministic or adversarial model can be very powerful with regards to reaching consensus, we focus our attention on randomised initialisations. As our main contribution, we show the following two results that depend on a measure of processor bias describing whether the processors are biased towards increasing 0s or 1s in the cells: (a) With randomised initialisation of the memory cells and random processor placement, eventually consensus is reached with high probability, even with sublinear processor bias. (b) With high probability, consensus is reached quickly whenever there is an arbitrarily small constant factor processor bias. These two results hold even if the memory cell initialisation has a bias that is in the opposite direction compared to the bias in the processors.

MOTIVATION: Recent advances in single-cell sequencing (SCS) offer an unprecedented insight into tumor emergence and evolution. Principled approaches to tumor phylogeny reconstruction via SCS data are typically based on general computational methods for solving an integer linear program, or a constraint satisfaction program, which, although guaranteeing convergence to the most likely solution, are very slow. Others based on Monte Carlo Markov Chain or alternative heuristics not only offer no such guarantee, but also are not faster in practice. As a result, novel methods that can scale up to handle the size and noise characteristics of emerging SCS data are highly desirable to fully utilize this technology. RESULTS: We introduce PhISCS-BnB (phylogeny inference using SCS via branch and bound), a branch and bound algorithm to compute the most likely perfect phylogeny on an input genotype matrix extracted from an SCS dataset. PhISCS-BnB not only offers an optimality guarantee, but is also 10-100 times faster than the best available methods on simulated tumor SCS data. We also applied PhISCS-BnB on a recently published large melanoma dataset derived from the sublineages of a cell line involving 20 clones with 2367 mutations, which returned the optimal tumor phylogeny in <4 h. The resulting phylogeny agrees with and extends the published results by providing a more detailed picture on the clonal evolution of the tumor. AVAILABILITY AND IMPLEMENTATION: https://github.com/algo-cancer/PhISCS-BnB. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

A palindrome is a string that reads the same as its reverse, such as "aibohphobia" (fear of palindromes). Given an integer $d>0$, a $d$-near-palindrome is a string of Hamming distance at most $d$ from its reverse. We study the natural problem of identifying a longest $d$-near-palindrome in data streams. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON. We present an algorithm that returns a $d$-near-palindrome whose length is within a multiplicative $(1+ε)$-factor of the longest $d$-near-palindrome. Our algorithm also returns the set of mismatched indices of the $d$-near-palindrome, using $\mathcal{O}\left(\frac{d\log^7 n}{ε\log(1+ε)}\right)$ bits of space, and $\mathcal{O}\left(\frac{d\log^6 n}{ε\log(1+ε)}\right)$ update time per arriving symbol. We show that $Ω(d\log n)$ space is necessary for estimating the length of longest $d$-near-palindromes with high probability. We further obtain an additive-error approximation algorithm and a comparable lower bound, as well as an exact two-pass algorithm that solves the longest $d$-near-palindrome problem using $\mathcal{O}\left(d^2\sqrt{n}\log^6 n\right)$ bits of space.

MapReduce has emerged as a powerful tool for distributed and scalable processing of voluminous data. For skewed data input, load balancing is necessary among the MapReduce worker nodes to minimize the overall finishing time, which however can incur massive data movement in a data center network. In this paper, we for the first time examine this problem of data center-network-aware load balancing in the shuffle sub phase in MapReduce. Different from earlier studies that generally assume the network inside a data center has negligible delay and infinite capacity, we consider the traffic and bottlenecks in real data center networks by introducing the constraints on available network bandwidth, and demonstrate that the corresponding problem can be decomposed into two sub problems for network flow and load balancing, respectively. We show effective solutions to both of them, which together yield a complete solution towards near optimal data center-network-aware load balancing. A much simpler yet performance-wise comparable greedy algorithm is also developed for fast implementation in practice. The effectiveness of our solution has been demonstrated on synthetic and real public datasets.

MapReduce has emerged as a powerful tool for distributed and scalable processing of voluminous data. In this paper, we, for the first time, examine the problem of accommodating data skew in MapReduce with online operations. Different from earlier heuristics in the very late reduce stage or after seeing all the data, we address the skew from the beginning of data input, and make no assumption about a priori knowledge of the data distribution nor require synchronized operations. We examine the input in a continuous fashion and adaptively assign tasks with a load-balanced strategy. We show that the optimal strategy is a constrained version of online minimum makespan and, in the MapReduce context where pairs with identical keys must be scheduled to the same machine, there is an online algorithm with a provable 2-competitive ratio. We further suggest a sample-based enhancement, which, probabilistically, achieves a 3/2-competitive ratio with a bounded error.

A palindrome is defined as a string which reads forwards the same as backwards, like, for example, the string "racecar". In the Palindrome Problem, one tries to find all palindromes in a given string. In contrast, in the case of the Longest Palindromic Substring Problem, the goal is to find an arbitrary one of the longest palindromes in the string. In this paper we present three algorithms in the streaming model for the the above problems, where at any point in time we are only allowed to use sublinear space. We first present a one-pass randomized algorithm that solves the Palindrome Problem. It has an additive error and uses square root of n space. We also give two variants of the algorithm which solve related and practical problems. The second algorithm determines the exact locations of all longest palindromes using two passes and square root of n space. The third algorithm is a one-pass randomized algorithm, which solves the Longest Palindromic Substring Problem. It has a multiplicative error using only O(log(n)) space.

In this work, we are interested in periodic trends in long data streams in the presence of computational constraints. To this end; we present algorithms for discovering periodic trends in the combinatorial property testing model in a data stream S of length n using o ( n ) samples and space. In accordance with the property testing model, we first explore the notion of being “close” to periodic by defining three different notions of self-distance through relaxing different notions of exact periodicity. An input S is then called approximately periodic if it exhibits a small self-distance (with respect to any one self-distance defined). We show that even though the different definitions of exact periodicity are equivalent, the resulting definitions of self-distance and approximate periodicity are not; we also show that these self-distances are constant approximations of each other. Afterwards, we present algorithms which distinguish between the two cases where S is exactly periodic and S is far from periodic with only a constant probability of error. Our algorithms sample only O (√ n log 2 n ) (or O (√ n log 4 n ), depending on the self-distance) positions and use as much space. They can also find, using o ( n ) samples and space, the largest/smallest period, and/or all of the approximate periods of S . These algorithms can also be viewed as working on streaming inputs where each data item is seen once and in order, storing only a sublinear ( O (√ n log 2 n ) or O (√ n log 4 n )) size sample from which periodicities are identified.

Current approaches to providing robust network connections which are tolerant to failures involve restoration schemes which mainly focus on reserving backup paths. In this paper we propose a technique for which avoids the extra cost for reserving, by pre-identifying (but not reserving) the backup paths. We present and analyze an algorithm to solve this problem and study a practical special case in detail. Through simulations we show that our model is significantly more cost-efficient than backup path reservation. We also show how this model can fit into the MPLS architecture

Sensor networks are powerful tools for performing monitoring and surveillance tasks over large areas. A sensor is a cheap, simple device with low power and limited capabilities. In a sensor network a large number of sensors are deployed to span the whole area to be monitored. Due to the simplicity and the large quantity of the sensors involved, collecting data from a sensor network can be time and energy inefficient. In this paper, we investigate making the data gathering task from a sensor network more efficient by using a randomized, layered architecture. The layers in our architecture are constructed in a distributed fashion, with each sensor deciding locally on what layers it will exist. The key property of our technique is that the information is collected from one layer of the architecture containing a small subset of the sensors, resulting in fewer hops and thus smaller data in data aggregation. We provide provably correct results for the delay incurred and the accuracy of the results. In the context of our new techniques, we also explore ways to speed up the data gathering process even further, such as using history information. In addition, we consider how to optimize the structure of our system so that the energy consumption will be evenly distributed among each sensor, thus extending the overall lifetime of the entire network.

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns "CLOSE" if their edit distance is O(nΑ), and "FAR" if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(nmax(Α/2, 2Α - 1\)) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(nΑ/2) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most nΑ from those with edit distance at least n/6.

The problem of fast address lookup is crucial to routing and thus has received considerable attention. Most of the work in this field has focused on improving the speed of individual accesses-independent from the underlying access pattern. Gupta et al. (2000) proposed an efficient data structure to exploit the bias in access pattern. This technique achieves faster lookups for more frequently accessed keys while bounding the worst case lookup time; in fact it is (near) optimal under constraints on worst case performance. However,it needs to be rebuilt periodically to reflect the changes in access patterns, which can be inefficient for bursty environments. In this paper we introduce a new dynamic data structure to exploit biases in the access pattern, which tend to change dynamically. Previous work shows that there are many circumstances under which access patterns change quickly. Our data structure, which we call the biased skip list (BSL), has a self-update mechanism which reflects the changes in the access patterns efficiently and immediately, without any need for rebuilding. It improves throughput while keeping the worst case access time bounded by that of the fastest (unbiased) schemes. We demonstrate the practicality of BSL by experiments on data with varying degrees of burstiness.

A dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. Red-black trees, 2-3 trees, AVL trees, skip lists and other classic data structures facilitate O(logn) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. If access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as D-trees, biased search trees, splay trees and treaps which can achieve optimality.

A majority of the results on self-testing and correcting deal with programs which purport to compute the correct results precisely. We relax this notion of correctness and show how to check programs that compute only a numerical approximation to the correct answer. The types of programs that we deal with are those computing polynomials and functions defined by certain types of functional equations. We present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the affirmative a question raised by [P. Gemmell et al., Proceedings of the 23rd ACM Symposium on Theory of Computing, 1991, pp. 32--42; R. Rubinfeld and M. Sudan, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, FL, 1992, pp. 23--43; R. Rubinfeld and M. Sudan, SIAM J. Comput., 25 (1996), pp. 252--271]. We obtain this by first building approximate self-testers for linear and multilinear functions. We then show how to perform approximate checking, self-testing, and self-correcting for those functions that satisfy addition theorems, settling a question raised by [R. Rubinfeld, SIAM J. Comput., 28 (1999), pp. 1972--1997]. In both cases, we show that the properties used to test programs for these functions are both robust (in the approximate sense) and stable. Finally, we explore the use of reductions between functional equations in the context of approximate self-testing. Our results have implications for the stability theory of functional equations.

We study a network model in which each network link is associated with a set of delays and costs. These costs are a function of the delays and reflect the prices paid in return for delay guarantees. Such a cost structure can model a setting in which the service provider provides multiple service classes with a different price and delay guarantee for each class. We are given a source node s, a sink node t, and an end-to-end delay constraint D. Our aim is to choose an s-t path and determine a set of per link delay guarantees along this path so as to satisfy the constraint D while minimizing the total cost incurred. In the case where the s-t path is known, we aim to optimally partition the end-to-end delay constraint into link constraints along the path. We present approximation algorithms for both problems, since they are known to be NP-hard. Our algorithms guarantee to produce solutions that are within a factor 1+/spl epsiv/ of the optimal, where /spl epsiv/ is a parameter of our choice. The run times are polynomial in the input size and 1//spl epsiv/. We also provide a number of heuristics for the second problem and present simulation results. Previous work on related problems either focused on optimal solutions for special cost functions or on heuristics that have no performance guarantees. In contrast, we present provably good approximation algorithms and heuristics which apply to general cost functions.

Suppose P is a program designed to compute a function f defined on a group G. The task of self-testing P, that is, testing if P computes f correctly on most inputs, usually involves testing explicitly if P computes f correctly on every generator of G. In the case of multivariate functions, the number of generators, and hence the number of such tests, becomes prohibitively large. We refer to this problem as the generator bottleneck. We develop a technique that can be used to overcome the generator bottleneck for functions that have a certain nice structure, specifically if the relationship between the values of the function on the set of generators is easily checkable. Using our technique, we build the first efficient self-testers for many linear, multilinear, and some nonlinear functions. This includes the FFT, and various polynomial functions. All of the self-testers we present make only O(1) calls to the program that is being tested. As a consequence of our techniques, we also obtain efficient program result-checkers for all these problems.

We investigate the problem of when a prover can aid a verifier to reliably compute a functionfaster than if the verifier were to compute the function on its own.We focus on the case when it is enough for the verifier to know that the answer is close to correct.We use a model of proof systems which is based on interactive proof systems, probabilistically checkable proof systems, program checkers, and CS proofs.We develop protocols for several optimization problems, in which the running time of the verifier is significantly less than the size of the input.For example, we give polylogarithmic time protocols for showing the existence of a large Cut, a large matching and a small bin packing.In contrast, the protocolsused to show that IP = PSPACE, MIP = NEXP and NP = PCP(lg n, 1) [Sha90, BFL91, ALM+98, BFLS90J require a verifier that runs in sl(n) time.In the process, we develop a set of tools for use in constructing these proof systems.

Article Free Access Share on Spot-checkers Authors: Funda Ergün Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PAView Profile , Sampath Kannan Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PAView Profile , S. Ravi Kumar IBM Almaden Research Center, San Jose, CA IBM Almaden Research Center, San Jose, CAView Profile , Ronitt Rubinfeld Department of Computer Science, Cornell University, Ithaca, NY Department of Computer Science, Cornell University, Ithaca, NYView Profile , Mahesh Viswanathan Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998Pages 259–268https://doi.org/10.1145/276698.276757Published:23 May 1998Publication History 41citation512DownloadsMetricsTotal Citations41Total Downloads512Last 12 Months78Last 6 weeks10 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We introduce a new model of distributions generated by random walks on graphs.This model suggests a variety of learning problems, using the definitions and models of distribution learning defined in [6].Our framework is general enough to model previously studied distribution learning problems, as well as to suggest new applications.We describe special cases of the general problem, and investigate their relative difficulty.We present algorithms to solve the learning problem under various conditions.

The authors show how to check programs that compute polynomials and functions defined by addition theorems-in the realistic setting where the output of the program is approximate instead of exact. They present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the affirmative a question raised by Gemmell et al. (1991), and Rubinfeld and Sudan (1992, 1996). They then show how to perform approximate checking, self-testing, and self-correcting for those functions that satisfy addition theorems, settling a question raised by Rubinfeld (1994]) In both cases, they show that the properties used to test programs for these functions are both robust (in the approximate sense) and stable. Finally, they explore the use of reductions between functional equations in the context of approximate self-testing. Their results have implications to the stability theory of functional equations.

In this paper, we study PAC-leaming algorithms for specialized classes of deterministic finite automata (DFA).Inpartictdar, we study branchingprogrsms, and we investigate the intluence of the width of the branching program on the difficulty of the learning problem.We first present a distribution-free algorithm for learning width-2 branching programs.We also give an algorithm for the proper learning of width-2 branching programs under uniform distribution on labeled samples.We then show that the existence of an efficient algorithm for learning width-3 branching programs would imply the existence of an efficient algorithm for learning DNF, which is not known to be the case.Fimlly, we show that the existence of an algorithm for learning width-3 branching programs would also yield an algorithm for learning a very restricted version of parity with noise.*This is more restrictive than the definition in [6], where the i-tb column depends on an arbitrary Zj and more than one column may depend on any particuk z,.

Self-testing programs are an approach to the problem of program correctness [BLR90].One can construct selftesters by exploiting the set of properties that uniquely define the function and test that they hold at random inputs.The existing methods become more costly in the case of multivariate functions, since the number of such properties grows infeasibly large.In this paper we develop techniques for finding a much smaller set of such properties.These lead to more efficient testers for multivariate linear functions.We present efficient self-testers for the following functions that did not have self-testers before: Fast Fourier Transform (both directions), evaluation of polynomials, dot product (and therefore vector 2-norm), and pointwise evaluation of linear functions on vectors (and some non-linear ones as well).We present a tester for polynomial multiplication that makes O(1) calls to the program, in contrast to O(log n) of the existing tester, and present a new tester for matrix multiplication.All of the testers presented make O(1) calls to the program that is being tested.