Submitted to the Senate of Tel-Aviv University (2009)
under the supervision of prof. Shmuel Safra
This work was supervised by Dr. Amnon Ta-Shma In probabilistic computations, random bits are viewed as a resource. An important goal is to consume as little of it as possible. We study functions,...
Beverly Sackler, Oded Schwartz
2007 To all my parents, sisters and brothers. Thank you thank you thank you... Expanders are graphs that are sparse, yet highly connected. In this thesis, we consider an elementary algorithm for...
Diffractive parton distributions from the HERA data (2008)
Michael Groysa, Aharon Levya, Er Proskuryakovb Araymond, Beverly Sackler, Faculty Exact Sciences, School Of Physics, ...
Improving the Alphabet Size in Expander Based Code Constructions (2008)
Beverly Sackler, Eran Rom, Dr. Amnon Ta-shma
The research work has been conducted under the supervision of
N. Alon, M. Tarsi, Beverly Sackler
Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: If G is a directed graph with...
Identification of Conserved Protein Complexes Based on a Model of Protein Network Evolution (2008)
The Raymond, Beverly Sackler, Faculty Exact Sciences, Eitan Hirsh
by
under the supervision of (2008)
Beverly Sackler, Dr. Amnon Ta-shma
Many electronic voting protocols assume the voter votes with some computing device. This raises the question whether a voter can trust the device he is using. Three years ago, Chaum, and...
Access Graph Based Heuristics for On-line Paging Algorithms (2007)
Beverly Sackler, Faculty Exact Science, Ziv Rosen, Ziv Rosen
under the supervision of Dr. Amos Fiat
Faculty of Exact Sciences (2007)
This thesis is submitted in partial fulllment of the requirements towards the M.Sc. degree by
This work was carried out under the supervision of Prof. Noga Alon
Michael Krivelevich, Beverly Sackler, Faculty Exact Sciences
Almost perfect matchings in random uniform
WHAT REASONABLE FIRST-ORDER QUERIES ARE PERMITTED BY TRAKHTENBROT'S THEOREM? (2007)
Arnon Avron, Joram Hirschfeld, Beverly Sackler
Around 1950, B.A. Trakhtenbrot proved an important undecidability result (known, by a pure accident, as "Trakhtenbrot's theorem"): there is no algorithm to decide, given a...
Beverly Sackler, Prof Michael Krivelevich
First and foremost I wish to express my deepest gratitude to my advisor Prof. Michael Krivelevich for his guidance and help during the work on this thesis; for always having the time to see me; for...
Thesis Prepared Under the Supervision of (2006)
The Raymond, Beverly Sackler, Faculty Exact Sciences, Asaf Shapira, Prof Noga Alon
ii
Beverly Sackler, Faculty Exact Sciences, Alon Keinan, Prof Isaac Meilijson
This thesis summarizes a wonderful period I spent in Tel Aviv University. First and foremost, I had the pleasure of being supervised by Isaac Meilijson and Eytan Ruppin, whose brilliance can only be...
The Raymond, Beverly Sackler, Faculty Exact Sciences, Tali Kaufman, Under Professors, Noga Alon, ...
Property Testing is nowadays one of the central fields in Theoretical Computer Science. This concept played a major role in the proof of the celebrated PCP theorem. A typical task in Property Testing...
Under the supervision of (2003)
Beverly Sackler, Doron Friedman, Dr. Yishai Feldman, Prof Amiram Yehudai
ii The thesis is dedicated to my favorite autonomous agent Dana, and her mother Dorit. iii iv Acknowledgments I would like to express my deepest gratitude to my supervisors Yishai Feldman and Amiram...
The Degenerate Primer Design Problem (2002)
Ron Shamir, Beverly Sackler, Prof Ron Shamir
A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the...
The Raymond, Beverly Sackler, Pazi Boxer
Bounds in the shared memory requirements for Long-Lived & Adaptive ob jects
A Robust Algorithm for Constructing Physical Maps From Noisy Non-Unique Probes Fingerprints (1998)
Guy Mayraz, The Raymond, Beverly Sackler, Faculty Exact Sciences, Prof Ron Shamir
A practical algorithm for construction of physical maps based on hybridization fingerprint data of short (non-unique) oligonucleotide probes has been developed and extensively tested. Extensive...
Computational Aspects of Synaptic Elimination (1997)
The Raymond, Beverly Sackler, Gal Chechik, Prof Isaco Meilijson, Jonathan Cohen, Eyal Cohen (zoro
Research in humans and primates shows that the developmental course of the brain involves synaptic over-growth followed by marked selective pruning which eliminates about half of the synapses of the...
Independent Transversals and Independent Coverings in Sparse Partite Graphs (1997)
Raphael Yuster, Beverly Sackler
An [n; k; r]-partite graph is a graph whose vertex set, V , can be partitioned into n pairwisedisjoint independent sets, V 1 ; . . . ; Vn , each containing exactly k vertices, and the subgraph...
Schema Based Data Translation (1997)
The Raymond, Beverly Sackler, Sagit Zohar, Prepared Dr, Tova Milo
This paper considers translations from SGML structured documents to OO databases, and suggests a general framework of both. Such translations are useful where there is a need to query the data, since...
The Chromatic Numbers of Random Hypergraphs (1997)
Michael Krivelevich, Beverly Sackler, Faculty Exact Sciences, Benny Sudakov
For a pair of integers 1 fl ! r, the fl-chromatic number of an r-uniform hypergraph H = (V; E) is the minimal k, for which there exists a partition of V into subsets T 1 ; : : : ; T k such that je...
Abstract. A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a complete multipartite...
Interval Graphs with Side Constraints (1995)
Itsik Pe'er, The Raymond, Beverly Sackler, Prepared Dr, Ron Shamir
We study problems of determining whether a given interval graph has a realization which satisfies additional given constraints. Such problems occur frequently in applications where entities are...
Characterizations Of Vertex Pancyclic And Pancyclic Ordinary Complete Multipartite Digraphs (1995)
G. Gutin, Raymond And Beverly Sackler, Beverly Sackler
. A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a complete multipartite digraph. Such a...
Some properties of linear logic proved by semantic methods (1994)
We construct several simple algebraic models of the multiplicative and multiplicative-additive fragments of linear logic and demonstrate the value of such models by proving some unexpected...
The Method of Hypersequents in the Proof Theory of Propositional Non-Classical Logics (1994)
Arnon Avron, Beverly Sackler, I. An Introduction
This paper is devoted to a description, with many examples, of one particular framework of this sort: that of hypersequents. We shall show that this framework is indeed stronger than that of ordinary...
Finding a longest path in a complete multipartite digraph (1993)
Abstract. A digraph obtained by replacing each edge of a complete mpartite graph with an arc or a pair of mutually opposite arcs with the same end vertices is called a complete m-partite digraph. We...
Gentzen-Type Systems, Resolution and Tableaux (1993)
In advanced books and courses on logic (e.g. [Sm], [BM]) Gentzen-type systems or their dual, tableaux, are described as techniques for showing validity of formulae which are more practical than the...
Oscillatory Model of Short Term Memory (1992)
David Horn, Beverly Sackler, Marius Usher
We investigate a model in which excitatory neurons have dynamical thresholds which display both fatigue and potentiation. The fatigue property leads to oscillatory behavior. It is responsible for the...
Improved complexity bounds for location problems on the real line (1991)
R. Hassin, A. Tamir, Beverly Sackler
Abstract. In this note we apply recent results in dynamic programming to improve the complexity bounds of several median and coverage location models on the real line.
Given a multivariate compactly supported distribution OE, we derive here a necessary and sufficient condition for the global linear independence of its integer translates. This condition is based on...