Computational complexity began with the natural physical notions of time and space. Given
a property, S, an important issue is the computational complexity of checking whether or not …

Abstract Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an n-
variate boolean function has circuit complexity less than a given parameter s. We prove that …

For a monoid G, the iterated multiplication problem is the computation of the product of n
elements from G. By refining known completeness arguments, we show that as G varies over …

Recently we developed a new method in graph theory based on the regularity lemma. The
method is applied to find certain spanning subgraphs in dense graphs. The other main …

We study a basic algorithmic problem in algebraic geometry, which we call NNL, of
constructing a normalizing map as per Noether's Normalization Lemma. For general explicit …

The matching problem is central to graph theory and the theory of algorithms. This book
provides a comprehensive and straightforward introduction to the basic methods for …

Given a black box which will produce the value of a k-sparse multivariate polynomial for any
given specific argument, one may ask for optimal strategies (1) to distinguish such a …

It is shown that Stable Matching problems are the same as problems about stable
configurations of X-networks. Consequences include easy proofs of old theorems, a new …

Abstract The Massively Parallel Computation (MPC) model serves as a common abstraction
of many modern large-scale data processing frameworks, and has been receiving …

We present new lower bounds that show that a polynomial number of passes are necessary
for solving some fundamental graph problems in the streaming model of computation. For …