Motivation: The complexes formed by binding of proteins to RNAs play key roles in many biological processes, such as splicing, gene expression regulation, translation and viral replication. Understanding protein-RNA binding may thus provide important insights to the functionality and dynamics of many cellular processes. This has sparked substantial interest in exploring protein-RNA binding experimentally, and predicting it computationally. The key computational challenge is to efficiently and accurately infer protein-RNA binding models that will enable prediction of novel protein-RNA interactions to additional transcripts of interest. Results: We developed DLPRB (Deep Learning for Protein-RNA Binding), a new deep neural network (DNN) approach for learning intrinsic protein-RNA binding preferences and predicting novel interactions. We present two different network architectures: a convolutional neural network (CNN), and a recurrent neural network (RNN). The novelty of our network hinges upon two key aspects: (i) the joint analysis of both RNA sequence and structure, which is represented as a probability vector of different RNA structural contexts; (ii) novel features in the architecture of the networks, such as the application of RNNs to RNA-binding prediction, and the combination of hundreds of variable-length filters in the CNN. Our results in inferring accurate RNA-binding models from high-throughput in vitro data exhibit substantial improvements, compared to all previous approaches for protein-RNA binding prediction (both DNN and non-DNN based). A more modest, yet statistically significant, improvement is achieved for in vivo binding prediction. When incorporating experimentally-measured RNA structure, compared to predicted one, the improvement on in vivo data increases. By visualizing the binding specificities, we can gain biological insights underlying the mechanism of protein RNA-binding. Availability and implementation: The source code is publicly available at https://github.com/ilanbb/dlprb. Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: Complex interactions among alleles often drive differences in inherited properties including disease predisposition. Isolating the effects of these interactions requires phasing information that is difficult to measure or infer. Furthermore, prevalent sequencing technologies used in the essential first step of determining a haplotype limit the range of that step to the span of reads, namely hundreds of bases. With the advent of pseudo-long read technologies, observable partial haplotypes can span several orders of magnitude more. Yet, measuring whole-genome-single-individual haplotypes remains a challenge. A different view of whole genome measurement addresses the 3D structure of the genome-with great development of Hi-C techniques in recent years. A shortcoming of current Hi-C, however, is the difficulty in inferring information that is specific to each of a pair of homologous chromosomes. RESULTS: In this work, we develop a robust algorithmic framework that takes two measurement derived datasets: raw Hi-C and partial short-range haplotypes, and constructs the full-genome haplotype as well as phased diploid Hi-C maps. By analyzing both data sets together we thus bridge important gaps in both technologies-from short to long haplotypes and from un-phased to phased Hi-C. We demonstrate that our method can recover ground truth haplotypes with high accuracy, using measured biological data as well as simulated data. We analyze the impact of noise, Hi-C sequencing depth and measured haplotype lengths on performance. Finally, we use the inferred 3D structure of a human genome to point at transcription factor targets nuclear co-localization. AVAILABILITY AND IMPLEMENTATION: The implementation available at https://github.com/YakhiniGroup/SpectraPh CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: New sequencing technologies generate larger amount of short reads data at decreasing cost. De novo sequence assembly is the problem of combining these reads back to the original genome sequence, without relying on a reference genome. This presents algorithmic and computational challenges, especially for long and repetitive genome sequences. Most existing approaches to the assembly problem operate in the framework of de Bruijn graphs. Yet, a number of recent works use the paradigm of string graph, using a variety of methods for storing and processing suffixes and prefixes, like suffix arrays, the Burrows-Wheeler transform or the FM index. Our work is motivated by a search for new approaches to constructing the string graph, using alternative yet simple data structures and algorithmic concepts. RESULTS: We introduce a novel hash-based method for constructing the string graph. We use incremental hashing, and specifically a modification of the Karp-Rabin fingerprint, and Bloom filters. Using these probabilistic methods might create false-positive and false-negative edges during the algorithm's execution, but these are all detected and corrected. The advantages of the proposed approach over existing methods are its simplicity and the incorporation of established probabilistic techniques in the context of de novo genome sequencing. Our preliminary implementation is favorably comparable with the first string graph construction of Simpson and Durbin (2010) (but not with subsequent improvements). Further research and optimizations will hopefully enable the algorithm to be incorporated, with noticeable performance improvement, in state-of-the-art string graph-based assemblers.

We join the increasing call to take computational education of life science students a step further, beyond teaching mere programming and employing existing software tools. We describe a new course, focusing on enriching the curriculum of life science students with abstract, algorithmic, and logical thinking, and exposing them to the computational "culture." The design, structure, and content of our course are influenced by recent efforts in this area, collaborations with life scientists, and our own instructional experience. Specifically, we suggest that an effective course of this nature should: (1) devote time to explicitly reflect upon computational thinking processes, resisting the temptation to drift to purely practical instruction, (2) focus on discrete notions, rather than on continuous ones, and (3) have basic programming as a prerequisite, so students need not be preoccupied with elementary programming issues. We strongly recommend that the mere use of existing bioinformatics tools and packages should not replace hands-on programming. Yet, we suggest that programming will mostly serve as a means to practice computational thinking processes. This paper deals with the challenges and considerations of such computational education for life science students. It also describes a concrete implementation of the course and encourages its use by others.

We describe the curriculum, initial experience, and preliminary evaluation of an introductory CS course for students taking CS as their single or double major. The course is taught during the first or second semester of the first year of studies. It is centered around eleven to thirteen topics, offering a wide cover of major CS subjects. Many of these topics are not covered in "traditional" introductory CS courses, and some of them are not even covered through the standard undergraduate curricula. Examples: digital image representation and processing, error correction and detection codes, hashing (including Cuckoo hashing), and text compression.

We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.

We study simple geometric properties of gene expression data sets, where samples are taken from two distinct classes (e.g., two types of cancer). Specifically, the problem of linear separability for pairs of genes is investigated. If a pair of genes exhibits linear separation with respect to the two classes, then the joint expression level of the two genes is strongly correlated to the phenomena of the sample being taken from one class or the other. This may indicate an underlying molecular mechanism relating the two genes and the phenomena(e.g., a specific cancer). We developed and implemented novel efficient algorithmic tools for finding all pairs of genes that induce a linear separation of the two sample classes. These tools are based on computational geometric properties and were applied to 10 publicly available cancer data sets. For each data set, we computed the number of actual separating pairs and compared it to an upper bound on the number expected by chance and to the numbers resulting from shuffling the labels of the data at random empirically. Seven out of these 10 data sets are highly separable. Statistically, this phenomenon is highly significant, very unlikely to occur at random. It is therefore reasonable to expect that it manifests a functional association between separating genes and the underlying phenotypic classes.

MOTIVATION: Cloning of long DNA sequences (40-60 bases) into phage display libraries using polymerase chain reaction (PCR) is a low efficiency process, in which PCR is used to incorporate a DNA insert, coding for a certain peptide, into the amplified sequence. The PCR efficiency in this process is strongly affected by the distribution of G-C bases in the amplified sequence. As any DNA insert coding for the target peptide may be attempted, there is a flexibility in choosing part of the amplified sequence. Since the number of inserts coding for the same peptide is exponential in the peptide length, a computational problem naturally arises--that of efficiently finding an insert, whose parameters are optimal for PCR cloning. RESULTS: The GC distribution requirements are formulated as a search problem. We developed an efficient, linear time 'one pass' algorithm for this problem. Interestingly, our algorithm strongly relies on an interesting symmetry, which we observed in the standard genetic code. Most non-standard genetic codes examined possess this symmetry as well, yet some do not. We generalize the search problem and consider the case of a non-standard, or arbitrary, genetic code where this symmetry does not necessary hold. We solve the generalized problem in polynomial, but nonlinear, time. AVAILABILITY: An implementation of the proposed algorithm is available upon request from the authors.

Maximum likelihood (ML) is an increasingly popular optimality criterion for selecting evolutionary trees [Felsenstein 1981]. Finding optimal ML trees appears to be a very hard computational task, but for tractable cases, ML is the method of choice. In particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for the second major character based criterion, maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years [Foulds and Graham, 1982; Day et al. 1986], such a hardness result for ML has so far eluded researchers in the field.An important work by Tuffley and Steel [1997] proves quantitative relations between the parsimony values of given sequences and the corresponding log likelihood values. However, a direct application of their work would only give an exponential time reduction from MP to ML. Another step in this direction has recently been made by Addario-Berry et al. [2004], who proved that ancestral maximum likelihood (AML) is NP-complete. AML “lies in between” the two problems, having some properties of MP and some properties of ML. Still, the AML proof is not directly applicable to the ML problem.We resolve the question, showing that “regular” ML on phylogenetic trees is indeed intractable. Our reduction follows the vertex cover reductions for MP [Day et al. 1986] and AML [Addario-Berry et al. 2004], but its starting point is an approximation version of vertex cover, known as gap vc. The crux of our work is not the reduction, but its correctness proof. The proof goes through a series of tree modifications, while controlling the likelihood losses at each step, using the bounds of Tuffley and Steel [1997]. The proof can be viewed as correlating the value of any ML solution to an arbitrarily close approximation to vertex cover.

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n/sup o(k)/poly(m), where n is the circuit input length, m is the circuit size, and k is the parameter, unless the (t - l)-st level W[t $1] of the W-hierarchy collapses to FPT. By refining this technique, we prove that a group of parameterized NP-hard problems, including weighted SAT, dominating set, hitting set, set cover, and feature set, cannot be solved in time n/sup o(k)/poly(m), where n is the size of the universal set from which the k elements are to be selected and m is the instance size, unless the first level W[l] of the W-hierarchy collapses to FPT. We also prove that another group of parameterized problems which includes weighted q-SAT (for any fixed q /spl ges/ 2), clique, and independent set, cannot be solved in time n/sup o(k)/ unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yannakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n/sup k/ poly(m) or O(n/sup k/).

Maximum likelihood (ML) is increasingly used as an optimality criterion for selecting evolutionary trees (Felsenstein, 1981), but finding the global optimum is a hard computational task. Because no general analytic solution is known, numeric techniques such as hill climbing or expectation maximization (EM), are used in order to find optimal parameters for a given tree. So far, analytic solutions were derived only for the simplest model - three taxa, two state characters, under a molecular clock (MC). Quoting Ziheng Yang (2000), who initiated the analytic approach, "this seems to be the simplest case, but has many of the conceptual and statistical complexities involved in phylogenetic estimation".In this work, we give analytic solutions for four taxa, two state characters under a molecular clock. The change from three to four taxa incurs a major increase in the complexity of the underlying algebraic system, and requires novel techniques and approaches. We start by presenting the general maximum likelihood problem on phylogenetic trees as a constrained optimization problem, and the resulting system of polynomial equations. In full generality, it is infeasible to solve this system, therefore specialized tools for the MC case are developed.Four taxa rooted trees have two topologies -- the fork (two subtrees with two leaves each) and the comb (one subtree with three leaves, the other with a single leaf). We combine the ultrametric properties of MC trees with the Hadamard conjugation (Hendy and Penny, 1993) to derive a number of topology dependent identities. Employing these identities, we substantially simplify the system of polynomial equations. We finally use tools from algebraic geometry (e.g. Grobner bases, ideal saturation, resultants) and employ symbolic algebra software to obtain closed form analytic solutions (expressed parametrically in the input data) for the fork topology, and analytic solutions for the comb. We show that in contrast to the fork, the comb has no closed form solutions (expressed by radicals in the input data). In general, four taxa trees can have multiple ML points (Steel, 1994, Chor et. al., 2001). In contrast, we can now prove that under the MC assumption, both the fork and the comb topologies have a unique (local and global) ML point.

This paper concerns the discovery of patterns in gene expression matrices, in which each element gives the expression level of a given gene in a given experiment. Most existing methods for pattern discovery in such matrices are based on clustering genes by comparing their expression levels in all experiments, or clustering experiments by comparing their expression levels for all genes. Our work goes beyond such global approaches by looking for local patterns that manifest themselves when we focus simultaneously on a subset G of the genes and a subset T of the experiments. Specifically, we look for order-preserving submatrices (OPSMs), in which the expression levels of all genes induce the same linear ordering of the experiments (we show that the OPSM search problem is NP-hard in the worst case). Such a pattern might arise, for example, if the experiments in T represent distinct stages in the progress of a disease or in a cellular process, and the expression levels of all genes in G vary across the stages in the same way.We define a probabilistic model in which an OPSM is hidden within an otherwise random matrix. Guided by this model we develop an efficient algorithm for finding the hidden OPSM in the random matrix. In data generated according to the model the algorithm recovers the hidden OPSM with very high success rate. Application of the methods to breast cancer data seems to reveal significant local patterns.Our algorithm can be used to discover more than one OPSM within the same data set, even when these OPSMs overlap. It can also be adapted to handle relaxations and extensions of the OPSM condition. For example, we may allow the different rows of G x T to induce similar but not identical orderings of the columns, or we may allow the set T to include more than one representative of each stage of a biological process.

Maximum likelihood (ML) is a widely used criterion for selecting optimal evolutionary trees. However, little is known on the nature of the likelihood surface for trees, especially as to the frequency of multiple optima. We initiate an analytic study for identifying sequences that generate multiple optima. We report a new approach to calculating ML directly, which we have used to find large families of sequences that have multiple optima, including sequences with a continuum of optimal points. Such datasets are best supported by different (two or more) phylogenies that vary significantly in their timings of evolutionary events Some standard biological processes can lead to data with multiple optima and consequently the field needs further investigation. Our results imply that hill climbing techniques, as currently implemented in various software packages, cannot guarantee to find the global ML point, even if it is unique.

We give cryptographic schemes that help trace the source of leaks when sensitive or proprietary data is made available to a large set of parties. A very relevant application is in the context of pay television, where only paying customers should be able to view certain programs. In this application, the programs are normally encrypted, and then the sensitive data is the decryption keys that are given to paying customers. If a pirate decoder is found, it is desirable to reveal the source of its decryption keys. We describe fully resilient schemes which can be used against any decoder which decrypts with nonnegligible probability. Since there is typically little demand for decoders which decrypt only a small fraction of the transmissions (even if it is nonnegligible), we further introduce threshold tracing schemes which can only be used against decoders which succeed in decryption with probability greater than some threshold. Threshold schemes are considerably more efficient than fully resilient schemes.

Identifying what problems can be solved in a given distributed system is a central question in distributed computing. In this series of works, we study this question in the context of asynchronous fault tolerant systems that can execute consensus. These systems can be those executing deterministic protocols with access to a consensus routine or those running randomized error-free protocols. A previous work handled the class of distributed decision tasks. In these tasks, each processor receives one local input and has to respond with one local output. In an interactive distributed task each of n processors receives a sequence of local inputs and has to respond on line with an output for every new input (before getting its next input). Different processors can be at different stages concurrently, so that additional inputs are received by fast processors while slow processors are still working on early inputs. An interactive task is called finite if the number of local inputs (and outputs) is finite. Interactive tasks can neither be described as a single huge decision task nor be decomposed into distinct, independent decision tasks. The main result of this work is an exact characterization of the finite interactive tasks which can be solved by t-resilient protocols in either of the above two models. The major tool we use in the characterization is a directed acyclic graph that is associated with an interactive task. Properties of this graph are used to determine the resiliency of the task and to devise a "generic" resilient algorithm which solves such tasks. This generic algorithm can be viewed as a repeated, deterministic reduction to a consensus subroutine. This implies that any finite interactive task is solvable by randomized error-free protocols iff it is solvable by deterministic protocols with access to consensus.

No abstract available.

Publicly accessible databases are an indispensable resource for retrieving up-to-date information. But they also pose a significant risk to the privacy of the user, since a curious database operator can follow the user's queries and infer what the user is after. Indeed, in cases where the users' intentions are to be kept secret, users are often cautious about accessing the database. It can be shown that when accessing a single database, to completely guarantee the privacy of the user, the whole database should be down-loaded; namely n bits should be communicated (where n is the number of bits in the database). In this work, we investigate whether by replicating the database, more efficient solutions to the private retrieval problem can be obtained. We describe schemes that enable a user to access k replicated copies of a database ( k ≥2) and privately retrieve information stored in the database. This means that each individual server (holding a replicated copy of the database) gets no information on the identity of the item retrieved by the user. Our schemes use the replication to gain substantial saving. In particular, we present a two-server scheme with communication complexity O(n 1/3 ).

An input to the betweenness problem contains m constraints over n real variables (points). Each constraint consists of three points, where one of the points is specified to lie inside the interval defined by the other two. The order of the other two points (i.e., which one is the largest and which one is the smallest) is not specified. This problem comes up in questions related to physical mapping in molecular biology. In 1979, Opatrny showed that the problem of deciding whether the n points can be totally ordered while satisfying the m betweenness constraints is NP-complete [SIAM J. Comput., 8 (1979), pp. 111--114]. Furthermore, the problem is MAX SNP complete, and for every $\alpha> 47/48$ finding a total order that satisfies at least $\alpha$ of the m constraints is NP-hard (even if all the constraints are satisfiable). It is easy to find an ordering of the points that satisfies 1/3 of the m constraints (e.g., by choosing the ordering at random). This paper presents a polynomial time algorithm that either determines that there is no feasible solution or finds a total order that satisfies at least 1/2 of the m constraints. The algorithm translates the problem into a set of quadratic inequalities and solves a semidefinite relaxation of them in ${\cal R}^ n . The n solution points are then projected on a random line through the origin. The claimed performance guarantee is shown using simple geometric properties of the semidefinite programming (SDP) solution.

Article Free Access Share on On constructing radiation hybrid maps (extended abstract) Authors: Amir Ben-Dor Dept. of Computer Science, Technion, Haifa 32000, Israel Dept. of Computer Science, Technion, Haifa 32000, IsraelView Profile , Benny Chor Dept. of Computer Science, Technion, Haifa 32000, Israel Dept. of Computer Science, Technion, Haifa 32000, IsraelView Profile Authors Info & Claims RECOMB '97: Proceedings of the first annual international conference on Computational molecular biologyJanuary 1997 Pages 17–26https://doi.org/10.1145/267521.267525Online:19 January 1997Publication History 4citation228DownloadsMetricsTotal Citations4Total Downloads228Last 12 Months3Last 6 weeks1 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

Gilboat show that the computational approach leads to substantial savings.For every ~> 0, we present a two database computational PIR scheme whose communication complexity is O(n').This improved efficiency is achieved by a combination of a novel balancing technique, together with careful application of pseudo random generators.Our schemes preserve some desired properties of previous solutions.In particular, all our schemes use only one round of communication, they are fairly simple, they are memoryless, and the database contents is stored in its plain form, without any encoding.is possible to protect the user's privacy.The solutions to this private information retrieval (PIR) problem enable the user to retrieve a desired data item, while giving each individual database no partial information on the query.The quality of a solution is measured primarily ' Details on related models and techniques can also be found in [3].random generators [2, 10].(This is equivalent to the existence of one way functions [6, 5]. ) Under this assumption, we develop a family of computational PIR schemes.All these schemes

A (g, b) key distribution scheme allows conferences of g users to generate secret keys, such that disjoint coalitions of b users cannot gain any information on the generated key (in the information-theoretic sense). We study the relationships between communication and space efficiency of key distribution schemes. We prove that communication does not help in the context of unrestricted schemes. On the other hand, we show that for restricted schemes, which are secure only when used by a limited number of conferences, communication can substantially improve the space efficiency. We also present lower bounds on the space efficiency of restricted schemes.

We describe schemes that enable a user to access k replicated copies of a database (k/spl ges/2) and privately retrieve information stored in the database. This means that each individual database gets no information on the identity of the item retrieved by the user. For a single database, achieving this type of privacy requires communicating the whole database, or n bits (where n is the number of bits in the database). Our schemes use the replication to gain substantial saving. In particular, we have: A two database scheme with communication complexity of O(n/sup 1/3/). A scheme for a constant number, k, of databases with communication complexity O(n/sup 1/k/). A scheme for 1/3 log/sub 2/ n databases with polylogarithmic (in n) communication complexity.

The subject of this work is the possibility of private distributed computations of n-argument functions defined over the integers. A function f is t-private if there exists a protocol for computing f, so that no coalition of at most t participants can infer any additional information from the execution of the protocol. It is known that over finite domains every function can be computed $\lfloor (n - 1)/2 \rfloor $-privately. Some functions, like addition, are even n-private. We prove that this result cannot be extended to infinite domains. The possibility of privately computing f is shown to be closely related to the communication complexity of f. By using this relation, we show, for example, that n-argument addition is $\lfloor (n - 1)/2 \rfloor $-private over the nonnegative integers, but not even 1-private over all the integers. Finally, a complete characterization of t-private Boolean functions over countable domains is given. A Boolean function is 1-private if and only if its communication complexity is bounded. This characterization enables us to prove that every Boolean function falls into one of the following three categories: It is either n-private, $\lfloor (n - 1)/2 \rfloor $-private but not $\lceil n/2 \rceil$-private, or not 1-private.

Article Free Access Share on Resilience of general interactive tasks Authors: Benny Chor Dept. of Computer Science, Technion, Haifa 32000, Israel Dept. of Computer Science, Technion, Haifa 32000, IsraelView Profile , Lee-Bath Nelson Graduate School of Business, Stanford University, CA Graduate School of Business, Stanford University, CAView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 173–182https://doi.org/10.1145/197917.198085Published:14 August 1994Publication History 0citation162DownloadsMetricsTotal Citations0Total Downloads162Last 12 Months5Last 6 weeks1 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

The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the unrelativized case. Although this paper is not the first to provide a counterexample to the Random Oracle Hypothesis, it does provide a most compelling counterexample by showing that for almost all oracles A, IPA ≠ PSPACEA. If the Random Oracle Hypothesis were true, it would contradict Shamir's result that IP = PSPACE. In fact, it is shown that for almost all oracles A, co-NPA ⫋ IPA. These results extend to the multiprover proof systems of Ben-Or, Goldwasser, Killian, and Wigderson. In addition, this paper shows that the Random Oracle Hypothesis is sensitive to small changes in the definition. A class IPP, similar to IP, is defined. Surprisingly, the IPP = PSPACE result holds for all oracle worlds.

This paper studies the wait-free consensus problem in the asynchronous shared memory model. In this model, processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set). It is known that the wait-free consensus problem cannot be solved by deterministic protocols. A randomized solution is presented. This protocol is simple, constructive, tolerates up to $n - 1$ processors crashes (where n is the number of processors), and its expected run-time is $O(n^2 )$.

Given a set of parties {1, /spl middot//spl middot//spl middot/, n}, an access structure is a monotone collection of subsets of the parties. For a certain domain of secrets, a secret-sharing scheme for an access structure is a method for a dealer to distribute shares to the parties. These shares enable subsets in the access structure to reconstruct the secret, while subsets not in the access structure get no information about the secret. A secret-sharing scheme is ideal if the domains of the shares are the same as the domain of the secrets. An access structure is universally ideal if there exists an ideal secret-sharing scheme for it over every finite domain of secrets. An obvious necessary condition for an access structure to be universally ideal is to be ideal over the binary and ternary domains of secrets. The authors prove that this condition is also sufficient. They also show that being ideal over just one of the two domains does not suffice for universally ideal access structures. Finally, they give an exact characterization for each of these two conditions.>

Two parties, each holding one input of a two-variable function, communicate in order to determine the value of the function. Each party wants to expose as little of its input as possible to the other party. The authors prove tight bounds on the minimum amount of information about the individual inputs that must be revealed in the computation of most functions and of some specific ones. They also show that a computation that reveals little information about the individual inputs may require many more message exchanges than a more revealing computation.>

A Boolean function $f:A_1 \times A_2 \times \cdots \times A_n \to \{ 0,1 \}$ is t-private if there exists a protocol for computing f so that no coalition of size $\leqq t$ can infer any additional information from the execution, other than the value of the function. It is shown that f is $\lceil n/2 \rceil $-private if and only if it can be represented as \[ f ( x_1 ,x_2 , \cdots ,x_n ) = f_1 ( x_1 ) \oplus f_2 ( x_2 ) \oplus \cdots \oplus f_n ( x_n ), \] where the $f_i $ are arbitrary Boolean functions. It follows that if f is $\lceil n/2 \rceil $-private, then it is also n-private. Combining this with a result of Ben-Or, Goldwasser, and Wigderson, and of Chaum, Crepeau, and Damgard, [Proc. 20th Symposium on Theory of Computing, 1988, pp. 1–10 and pp. 11–19] an interesting “zero-one” law for private distributed computation of Boolean functions is derived: every Boolean function defined over a finite domain is either n-private, or it is $\lfloor ( n - 1 )/2 \rfloor $-private but not $\lceil n/2 \rceil $-private. A weaker notion of privacy is also investigated, where (a) coalitions are allowed to infer a limited amount of additional information, and (b) there is a probability of error in the final output of the protocol. It is shown that the same characterization of $\lceil n/2 \rceil $-private Boolean functions holds, even under these weaker requirements.In particular, this implies that for Boolean functions, the strong and the weak notions of privacy are equivalent.

The possibility of private distributed computations of n-argument functions defined over the integers is considered. A function f is t-private if there exists a protocol for computing f so that no coalition of>

The authors present necessary and sufficient combinatorial conditions that determine membership in SM/sub t/ (respectively, MP/sub t/), the class of distributed decision tasks that are solvable in the shared memory (resp. message passing) model by a t-resilient randomized protocol, which never errs and works in the presence of a strong adversary. The sufficiency of the conditions is proved by designing protocols that are applicable to all tasks in the appropriate class. The computational complexity of the membership characterization is studied.>

This paper takes the next step in developing the theory of average case complexity initiated by Leonid A Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include: the equivalence of search and decision problems in the context of average case complexity; an initial analysis of the structure of distributional-NP (i.e. NP problems coupled with \\simple distributions") under reductions which preserve average polynomial-time; a proof that if all of distributional-NP is in average polynomial-time then non-deterministic exponential-time equals deterministic exponential time (i.e., a collapse in the worst case hierarchy); denitions and basic theorems regarding other complexity classes such as average log-space. An exposition of the basic denitions suggested by Levin and suggestions for some alternative de nitions are provided as well.

A Boolean function ƒ: A1 X A2 X … X An → {0,1} is t - private if there exists a protocol for computing ƒ so that no coalition of size ≤ t can infer any additional information from the execution, other than the value of the function. We show that ƒ is ⌈n/2⌉ - private if and only if it can be represented as ƒ (x1, x2, …, xn) = ƒ (x1) ⊕ ƒ2(x2) ⊕ … ⊕ ƒn (xn, where the ƒi are arbitrary Boolean functions. It follows that if ƒ is ⌈n/2⌉ - private, then it is also n - private. Combining this with a result of Ben-Or, Goldwasser, and Wigderson, we derive an interesting “zero-one” law for private distributed computation of Boolean functions: Every Boolean function defined over a finite domain is either n - private, or it is ⌈n-1/2⌉ - private but not ⌈n/2⌉ - private.

Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.

The RSA and Rabin encryption functions $E_N ( \cdot )$ are respectively defined by raising $x \in Z_N $ to the power e (where e is relatively prime to $\varphi (N)$) and squaring modulo N (i.e., $E_N (x) = x^e (\bmod N)$, $E_N (x) = x^2 (\bmod N)$, respectively). We prove that for both functions, the following problems are computationally equivalent (each is probabilistic polynomial-time reducible to the other): (1) Given $E_N (x)$, find x. (2) Given $E_N (x)$, guess the least-significant bit of x with success probability $\tfrac{1}{2} + {1 {{\operatorname{poly}}(n)}}$ (where n is the length of the modulus N). This equivalence implies that an adversary, given the RSA/Rabin ciphertext, cannot have a non-negligible advantage (over a random coin flip) in guessing the least-significant bit of the plaintext, unless he can invert RSA/factor N. The proof techniques also yield the simultaneous security of the $\log n$ least-significant bits. Our results improve the efficiency of pseudorandom number generation and probabilistic encryption schemes based on the intractability of factoring.

A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g., the Santha and Vazirani model [27]). The sources considered output strings according to probability distributions in which no single string is too probable. The new model provides a fruitful viewpoint on problems studied previously such as: • Extracting almost-perfect bits from sources of weak randomness. The question of possibility as well as the question of efficiency of such extraction schemes are addressed. • Probabilistic communication complexity. It is shown that most functions have linear communication complexity in a very strong probabilistic sense. • Robustness of BPP with respect to sources of weak randomness (generalizing a result of Vazirani and Vazirani [32], [33]).

This paper proves that in a one-round fair coin flipping scheme with n participants, either the average influence of all participants is at least $3/n - o( 1/n )$, or there is at least one participant whose influence is $\Omega ( n^{ - 5 /6} )$.

A knapsack-type public key cryptosystem is introduced that is the system is based on a novel application of arithmetic in finite fields. By appropriately choosing the parameters, one can control the density of the resulting knapsack, which is the ratio between the number of elements in the knapsack and their size in bits. In particular, the density can be made high enough to foil so-called low-density attacks against the system. At the moment, no attacks capable of breaking the system in a reasonable amount of time are known.>

We investigate an asynchronous model of concurrent computations, where processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set).For this model, we define a general notion of processor coordination, and study the possibility and complexity of achieving coordination.Our definition includes, as special cases, mutual exclusion and asynchronous agreement.It is shown that the coordination problem cannot be solved by means of a deterministic protocol even if the system consists of only two processors.This impossibility result holds for the most powerful type of shared atomic registers and does not assume symmetric protocols.The impossibility result is contrasted by a variety of eficient randomized protocols, that achieve fast coordination for systems of arbitrary number of processors n.These protocols are all fairly simple, constructive, and their ezpectedrun-time is polynomial in n, even in the presence of an adaptive

Simultaneous broadcast [CGMAJ is a fundamental tool in designing secure protocols for fault tolerant distributed computing.A system that supports it enables n processes to globally commit to independently chosen values (a significantly harder task than mere agreement).It is also a basic building block in a recent %ompleteness" theorem of [GMWZ].In this paper we present a new protocol for simultaneous broadcast.Building upon past work, we introduce a novel method of concurrently alternating and interleaving n executions of verifiable secret sharing protocols.This approach greatly improves the time complexity (number of communication rounds) of simultaneous broadcast.Previous protocols (combination of [CGMA] and [GMW]) q re uired the complete serialization of the ra verifiable secret sharings, resulting in n(n) communication rounds.Our protocol is constructive, and requires only log n + log log n serial executions of verifiable secret sharings.It preserves maximum fault tolerance (t < n/2 faults), and polynomial resource bounds (internal computation and communication bits).The same improvement appiies to the general simulation in [GMWX].In light of its improved performance, it is significant that our our protocol has a fairly simple correctness proof.In the slippery business of distributed cryptographic protocols, simpler proofs are important.

A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to M memory chips according to a “Fibonacci” lattice. The memory organization guarantees that, if a rectilinearly oriented rectangle contains fewer than M / @@@@5 pixels, then all pixels will reside in different memory chips and thus can be accessed simultaneously. Moreover, any M consecutive pixels, arranged either horizontally or vertically, can be accessed simultaneously. We also define a continuous analog of the problem, which can be posed as: “What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of unit area?” We show the existence of such a set with density 1/ @@@@5, and prove this is optimal by giving a matching upper bound.

We introduce a general model for physical sources or weak randomness. Loosely speaking, we view physical sources as devices which output strings according to probability distributions in which no single string is too probable. The main question addressed is whether it is possible to extract alrnost unbiased random bits from such "probability bounded" sources. We show that most or the functions can be used to extract almost unbiased and independent bits from the output of any two independent "probability-bounded" sources. The number of extractable bits is within a constant factor of the information theoretic bound. We conclude this paper by establishing further connections between communication complexity and the problem discussed above. This allows us to show that most Boolean functions have linear communication complexity in a very strong sense.

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f : {0, 1}n → {0, 1}m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in {0, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f : {0,1}n → {0, 1}m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.

Article Simple constant-time consensus protocols in realistic failure models (extended abstract) Share on Authors: Benny Chor MIT Cambridge, MA MIT Cambridge, MAView Profile , Michael Merritt AT&T Bell Labs, Murray Hill, NJ and MIT, Cambridge, MA AT&T Bell Labs, Murray Hill, NJ and MIT, Cambridge, MAView Profile , David B. Shmoys Harvard University, Cambridge, MA Harvard University, Cambridge, MAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 152–162https://doi.org/10.1145/323596.323610Online:01 August 1985Publication History 10citation211DownloadsMetricsTotal Citations10Total Downloads211Last 12 Months4Last 6 weeks2 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 SiteGet Access

A new randomized Byzantine agreement algorithm is presented. This algorithm operates in a synchronous system of n processors, at most t of which can fail. The algorithm reaches agreement in 0(t/log n) expected rounds and O(n2tf/log n) expected message bits independent of the distribution of processor failures. This performance is further improved to a constant expected number of rounds and O(n2) message bits if the distribution of processor failures is assumed to be uniform. In either event, the algorithm improves on the known lower bound on rounds for deterministic algorithms. Some other advantages of the algorithm are that it requires no cryptographic techniques, that the amount of local computation is small, and that the expected number of random bits used per processor is only one. It is argued that in many practical applications of Byzantine agreement, the randomized algorithm of this paper achieves superior performance.

We prove that RSA least significant bit is 1/2 + (1/[logcN]) secure, for any constant c (where N is the RSA modulus). This means that an adversary, given the ciphertext, cannot guess the least sigiiilicatnt bit of the plaintext with probability better than 1/2 + (1/[logcN]), unless he can break RSA.

The ability to “hide” one bit in trapdoor functions has recently gained much interest in cryptography research, and is of great importance in many transactions protocols. In this paper we study the cryptographic security of RSA bits. In particular, we show that unless the cryptanalyst can completely break the RSA encryption, any heuristic he uses to determine the least significant bit of the cleartext must have an error probability greater than 1/4—e A similar result is shown for Rabin's encryption scheme.

A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to M memory chips according to a "Fibonacci" lattice. The memory organization guarantees that if a rectilinearly oriented rectangle contains fewer than M/√5 pixels, then all pixels will reside in different memory chips, and thus can be accessed simultaneously. We also define a continuous amdogue of the problem which can be posed as, "What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of area N." We give a lower bound of 1/2N on the density of such a set, and show that 1/√5N can be achieved.