Optimal Testing of Reed-Muller Codes (2009)
Bhattacharyya, Arnab, Kopparty, Swastik, Schoenebeck, Grant, Sudan, Madhu, Zuckerman, David
We consider the problem of testing if a given function $f : \F_2^n \to \F_2$ is close to any degree $d$ polynomial in $n$ variables, also known as the Reed-Muller testing problem. Alon et al....
Robust Regulatory Networks (2009)
Bhattacharyya, Arnab, Haeupler, Bernhard
One of the characteristic features of genetic networks is their inherent robustness, that is, their ability to retain functionality in spite of the introduction of random errors. In this paper, we...
Testing Linear-Invariant Non-Linear Properties (2009)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Testing Linear-Invariant Non-Linear Properties (2009)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Testing Linear-Invariant Non-Linear Properties (2009)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Testing Linear-Invariant Non-Linear Properties (2008)
Bhattacharyya, Arnab, Chen, Victor, Sudan, Madhu, Xie, Ning
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...
Transitive-Closure Spanners (2008)
Bhattacharyya, Arnab, Grigorescu, Elena, Jung, Kyomin, Raskhodnikova, Sofya, Woodruff, David P.
Given a directed graph G = (V,E) and an integer k>=1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, E_H) that has (1) the same transitive-closure as G and (2)...
A Note on the Distance to Monotonicity of Boolean Functions (2008)
Given a function f: {0, 1} n →{0, 1}, let ɛM (f) denote the smallest distance between f and a monotone function on {0, 1} n. Let δM (f) denote the fraction of hypercube edges where f violates...
ABSTRACT Morphogenesis as an Amorphous Computation (2008)
In this paper, we present a programming language viewpoint for morphogenesis, the process of shape formation during embryological development. Specifically, we model morphogenesis as a...
Modelling morphogenesis as an amorphous computation (2006)
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
Modelling morphogenesis as an amorphous computation / (2006)
This thesis presents a programming-language viewpoint for morphogenesis, the process of shape formation during embryological development. We model morphogenesis as a self-organizing, self-repairing...
Modelling morphogenesis as an amorphous computation (2006)
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
Implementing Probabilistically Checkable Proofs of Proximity (2005)
Abstract: In this paper, we describe a proof-of-concept implementation of the probabilistically checkable proof of proximity (PCPP) system described by Ben-Sasson and Sudan in \\cite{bs05}. In...
Implementing Probabilistically Checkable Proofs of Proximity (2005)
Abstract: In this paper, we describe a proof-of-concept implementation of the probabilistically checkable proof of proximity (PCPP) system described by Ben-Sasson and Sudan in \\cite{bs05}. In...