All reports by Author Victor Chen:

__
TR10-156
| 24th October 2010
__

Victor Chen, Madhu Sudan, Ning Xie#### Property Testing via Set-Theoretic Operations

__
TR10-116
| 21st July 2010
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing linear-invariant non-linear properties: A short report

__
TR09-079
| 21st September 2009
__

Victor Chen, Elena Grigorescu, Ronald de Wolf#### Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Revisions: 1

__
TR08-098
| 12th November 2008
__

Victor Chen#### A Hypergraph Dictatorship Test with Perfect Completeness

Revisions: 1

__
TR08-088
| 13th September 2008
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing Linear-Invariant Non-Linear Properties

Revisions: 1

Victor Chen, Madhu Sudan, Ning Xie

Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference

of these two properties also testable?

We initiate a systematic study of these basic set-theoretic operations in the context of property

testing. As an application, we give a conceptually different proof that linearity is ...
more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

Victor Chen, Elena Grigorescu, Ronald de Wolf

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the

decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no ...
more >>>

Victor Chen

A hypergraph dictatorship test is first introduced by Samorodnitsky

and Trevisan and serves as a key component in

their unique games based $\PCP$ construction. Such a test has oracle

access to a collection of functions and determines whether all the

functions are the same dictatorship, or all their low degree ...
more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

We consider the task of testing properties of Boolean functions that

are invariant under linear transformations of the Boolean cube. Previous

work in property testing, including the linearity test and the test

for Reed-Muller codes, has mostly focused on such tasks for linear

properties. The one exception is a test ...
more >>>