In this paper we study program checking (in the sense of Blum and Kannan) using constant-depth circuits as checkers. Our focus is on the number of queries made by the checker to the program being checked and we term this as the query complexity of the checker for the given ... more >>>

The essential idea in the fast parallel computation of division and related problems is that of Chinese remainder representation (CRR) -- storing a number in the form of its residues modulo many small primes. Integer division provides one of the few natural examples of problems for which all currently-known constructions ... more >>>

Integer division has been known to lie in P-uniform TC^0 since the mid-1980's, and recently this was improved to DLOG-uniform TC^0. At the time that the results in this paper were proved and submitted for conference presentation, it was unknown whether division lay in DLOGTIME-uniform TC^0 (also known as FOM). ... more >>>

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results: ... more >>>

Program checking, program self-correcting and program self-testing were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in the mid eighties as a new way to gain confidence in software, by considering program correctness on an input by input basis rather than full program verification. Work in the field ... more >>>

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>