We propose matchgate tensors as a natural and proper language
to develop Valiant's new theory of Holographic Algorithms.
We give a treatment of the central theorem in this theory---the Holant
Theorem---in terms of matchgate tensors.
Some generalizations are presented.

Let $\tau(k)$ be the minimum number of arithmetic operations
required to build the integer $k \in \N$ from the constant 1.
A sequence $x_k$ is said to be ``easy to compute'' if
there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$
for all $k \geq ... more >>>

We show analogues of a theorem due to Valiant and Vazirani
for intractable parameterized complexity classes such as W[P], W[SAT]
and the classes of the W-hierarchy as well as those of the A-hierarchy.
We do so by proving a general ``logical'' version of it which may be of
independent interest

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>>

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>

The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call $StackDet_n(X)$ and $CountDet_n(X)$ and show that they are VP and VNP complete respectively under $p$-projections. The definitions of the polynomials are inspired by a ... more >>>

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},\epsilon)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $\epsilon$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ ... more >>>

The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the ... more >>>

We introduce a new method for proving explicit upper bounds
on the VC Dimension of general functional basis networks,
and prove as an application, for the first time, that the
VC Dimension of analog neural networks with the sigmoidal
activation function $\sigma(y)=1/1+e^{-y}$ ... more >>>

We observe that if we allow for the use of
division and the floor function
besides multiplication, addition and
subtraction then we can
compute the arithmetic convolution
of two n-dimensional integer vectors in O(n) steps and
perform the arithmetic matrix multiplication
of two integer n times n matrices ... more >>>

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value $y$ at any point $x$, can also generate a non-interactive proof $\pi$ that $y$ is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with ... more >>>

In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling ... more >>>

Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a ... more >>>

How can we trust results computed by a third party, or the integrity of data stored by such a party? This is a classic question in systems security, and it is particularly relevant in the context of cloud computing.

Various solutions have been proposed that make assumptions about the class ... more >>>

We consider the following problem: Given an $n \times n$ multiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time of $O(n^2 \log n)$. ... more >>>

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Given i.i.d. samples from an unknown distribution over a large domain $[N]$, approximating several basic quantities, including the distribution's support size, its entropy, and its distance from the uniform distribution, requires $\Theta(N / \log N)$ samples [Valiant and Valiant, STOC 2011].

Suppose, however, that we can interact with a powerful ... more >>>

We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$?

Assuming a fixed tape and input alphabet, we show that ... more >>>

We prove that Minimum vertex cover on 4-regular hyper-graphs (or
in other words, hitting set where all sets have size exactly 4),
is hard to approximate within 2 - \epsilon.
We also prove that the maximization version, in which we
are allowed to pick ... more >>>

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is
to find a minimum subset of vertices that ``hits'' every edge. We
show that for every integer $k \geq 5$, E$k$-Vertex-Cover is
NP-hard to approximate within a factor of $(k-3-\epsilon)$, for
an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>

We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call "visible rank." The locality constraints of a linear code are stipulated by a matrix $H$ of $\star$'s and $0$'s (which we ... more >>>

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].

A visual cryptography scheme for a
set $\cal P $ of $n$ participants is a method to encode a secret
image $SI$ into $n$ shadow images called shares, where each participant in
$\cal P$ receives one share. Certain qualified subsets of participants
can ``visually'' recover the secret image, but
other, ... more >>>