Wiretapping a hidden network (2009)
Aziz, Haris, Lachish, Oded, Paterson, Mike, Savani, Rahul
We consider the problem of maximizing the probability of hitting a strategically chosen hidden virtual network by placing a wiretap on a single link of a communication network. This can be seen as a...
Testing Properties of Constraint-Graphs Extended Abstract + Appendix (2009)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
We study a model of graph related formulae that we call the Constraint-Graph model. A constraintgraph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge e...
Spanning connectivity games (2009)
Aziz, Haris, Lachish, Oded, Paterson, Mike, Savani, Rahul
The Banzhaf index, Shapley-Shubik index and other voting power indices measure the importance of a player in a coalitional game. We consider a simple coalitional game called the spanning connectivity...
Space Complexity vs. Query Complexity ∗ (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far”...
Lower Bounds for Testing Euclidean Minimum Spanning Trees (2008)
Oren Ben-zwi, Oded Lachish, Ilan Newman
Abstract The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G = ( P, E) on a set of points in the two dimensional plane is a minimum spanning tree with respectto the...
Lower Bounds for Testing Euclidean Minimum Spanning Trees (2008)
Oren Ben-zwi, Oded Lachish, Ilan Newman
The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G = (P, E) on a set of points in the two dimensional plane is a minimum spanning tree with respect to the Euclidean...
Testing Properties of Constraint-Graphs (2008)
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
We study a model of graph related formulae that we call the Constraint-Graph model. A constraintgraph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge e...
Space Complexity vs. Query Complexity (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Abstract. Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is...
Abstract. A string α ∈ Σ n is called p-periodic, if for every i, j ∈ {1,..., n}, such that i ≡ j mod p, αi = αj, where αi is the i-th place of α. A string α ∈ Σ n is said to be...
Oded Lachish, Ilan Newman, Asaf Shapira
Abstract. Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is...
Space Complexity vs. Query Complexity ∗ (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far”...
Overcoming data sparsity (2008)
Apple, Rosemary, Cawthorn, Chris, Yee Chan, Kwan, Lachish, Oded, Nonnenmacker, Achim, Porter, Mason A., ...
Unilever is currently designing and testing recommendation algorithms that would make recommendations about products to online customers given the customer ID and the current content of their basket....
Testing and Debugging—Testing tools (2007)
One of the main goals of coverage tools is to provide the user with informative presentation of coverage information. Specifically, information on large, cohesive sets of uncovered tasks with common...
Object-Oriented High-Level Modeling of an InfiniBand to PCI-X (2007)
The rapid increase in the complexity of modern ASICs raises the need for an increase in the abstraction level used to design these chips. While there exist many offerings of tools and languages...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be tested...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
Abstract. We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be...
Sound 3-query PCPPs are long (2007)
Eli Ben-sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah, Shalom Foundations
We initiate the study of the tradeoff between the length of a probabilistically checkable proof of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be tested...
Sound 3-query PCPPs are long (2007)
Eli Ben-sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah, Shalom Foundations
We initiate the study of the tradeoff between the length of a probabilistically checkable proof of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle...
Sound 3-query PCPPs are long (2007)
Eli Ben-sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah, Shalom Foundations
We initiate the study of the tradeoff between the length of a probabilistically checkable proof of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle...
An Explicit Lower Bound of 5n − o(n) for Boolean Circuits (2002)
Kazuo Iwama, Oded Lachish, Hiroki Morizumi, Ran Raz
Abstract. We prove a lower bound of 5n − o(n) for the circuit complexity of an explicit (constructible in deterministic polynomial time) Boolean function, over the basis U2. That is, we obtain a...
Explicit Lower Bound of 4.5n − o(n) for Boolean Circuits (2001)
We prove a lower bound of 4:5n o(n) for the circuit complexity of an explicit Boolean function (that is, a function constructible in deterministic polynomial time), over the basis U2. That is, we...