Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Victor Chen:

TR10-156 | 24th October 2010
Victor Chen, Madhu Sudan, Ning Xie

Property Testing via Set-Theoretic Operations

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 >>>

TR10-116 | 21st July 2010
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing linear-invariant non-linear properties: A short report

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 >>>

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

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 >>>

TR08-098 | 12th November 2008
Victor Chen

A Hypergraph Dictatorship Test with Perfect Completeness

Revisions: 1

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 >>>

TR08-088 | 13th September 2008
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing Linear-Invariant Non-Linear Properties

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint