A fundamental fact about bounded-degree graph expanders is that three notions of expansion---vertex expansion, edge expansion, and spectral expansion---are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion.

There are two well-studied notions of linear-algebraic expansion, namely dimension expansion ... more >>>

For a Boolean function f, let D(f) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper,
Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ... more >>>

In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if ... more >>>

The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>>

We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix M whose entries are homogeneous linear polynomials over the integers. Given a linear subspace \mathcal{B} of the n \times n matrices over some field \mathbb{F}, we consider ... more >>>

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial f computed by an unknown/hidden arithmetic formula \phi reconstructs, on the average, an equivalent or smaller formula \hat{\phi} in time polynomial in the size of its output \hat{\phi}.

Specifically, we consider arithmetic formulas wherein the ... more >>>

An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices s and t, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from s to t, where the weight of ... more >>>

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation \pi of n variables, for a \pi-ordered ABP (\pi-OABP), for any directed path p from source to sink, a variable can appear at ... more >>>