Results for query **matsliah**:

__
TR12-154
| 31st October 2012
__

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah#### On the Power of Conditional Samples in Distribution Testing

Revisions: 1

__
TR12-154
| 31st October 2012
__

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah#### On the Power of Conditional Samples in Distribution Testing

Revisions: 1
In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... more >>>

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR10-067
| 14th April 2010
__

Sourav Chakraborty, Eldar Fischer, Arie Matsliah#### Query Complexity Lower Bounds for Reconstruction of Codes

__
TR10-067
| 14th April 2010
__

Sourav Chakraborty, Eldar Fischer, Arie Matsliah#### Query Complexity Lower Bounds for Reconstruction of Codes

__
TR10-067
| 14th April 2010
__

Sourav Chakraborty, Eldar Fischer, Arie Matsliah#### Query Complexity Lower Bounds for Reconstruction of Codes

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... more >>>

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

Sourav Chakraborty, David García Soriano, Arie Matsliah

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

Sourav Chakraborty, David García Soriano, Arie Matsliah

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

Sourav Chakraborty, David García Soriano, Arie Matsliah

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

Sourav Chakraborty, David García Soriano, Arie Matsliah

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

Sourav Chakraborty, Eldar Fischer, Arie Matsliah

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>

Sourav Chakraborty, Eldar Fischer, Arie Matsliah

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>

Sourav Chakraborty, Eldar Fischer, Arie Matsliah

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

We study the problem of monotonicity testing over the hypercube. As

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

Harry Buhrman, David García Soriano, Arie Matsliah

We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model.

We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ...
more >>>

Harry Buhrman, David García Soriano, Arie Matsliah

We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ...
more >>>

Harry Buhrman, David García Soriano, Arie Matsliah

We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ...
more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

We initiate the study of the tradeoff between the {\em length} of a

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>