Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jin-Yi Cai:

TR13-048 | 27th March 2013
Jin-Yi Cai, Aaron Gorenstein

Matchgates Revisited

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. ... more >>>

TR07-020 | 11th March 2007
Jin-Yi Cai, Pinyan Lu

Holographic Algorithms: The Power of Dimensionality Resolved

Valiant's theory of holographic algorithms is a novel methodology
to achieve exponential speed-ups in computation. A fundamental
parameter in holographic algorithms is the dimension of the linear basis
We completely resolve the problem of the power of higher dimensional
bases. We prove that 2-dimensional bases are universal for
holographic ... more >>>

TR07-019 | 10th March 2007
Jin-Yi Cai, Pinyan Lu

On Block-wise Symmetric Signatures for Matchgates

We give a classification of block-wise symmetric signatures
in the theory of matchgate computations. The main proof technique
is matchgate identities, a.k.a. useful Grassmann-Pl\"{u}cker

more >>>

TR07-003 | 5th January 2007
Jin-Yi Cai, Pinyan Lu

Bases Collapse in Holographic Algorithms

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This ... more >>>

TR06-145 | 1st December 2006
Jin-Yi Cai, Pinyan Lu

Holographic Algorithms: From Art to Science

We develop the theory of holographic algorithms. We give
characterizations of algebraic varieties of realizable
symmetric generators and recognizers on the basis manifold,
and a polynomial time decision algorithm for the
simultaneous realizability problem.
Using the general machinery we are able to give
unexpected holographic algorithms for
some counting problems, ... more >>>

TR06-135 | 22nd October 2006
Jin-Yi Cai, Pinyan Lu

On Symmetric Signatures in Holographic Algorithms

The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ ... more >>>

TR06-048 | 9th April 2006
Jin-Yi Cai, Vinay Choudhary

Some Results on Matchgates and Holographic Algorithms

We establish a 1-1 correspondence between Valiant's
character theory of matchgate/matchcircuit
and his signature theory of planar-matchgate/matchgrid,
thus unifying the two theories in expressibility.
Previously we had established a complete characterization
of general matchgates, in terms of a set of
useful Grassmann-Pl{\"u}cker identities.
With this correspondence,
we give a corresponding ... more >>>

TR06-018 | 8th February 2006
Jin-Yi Cai, Vinay Choudhary

On the Theory of Matchgate Computations

Valiant has proposed a new theory of algorithmic
computation based on perfect matchings and the Pfaffian.
We study the properties of {\it matchgates}---the basic
building blocks in this new theory. We give a set of
algebraic identities
which completely characterize these objects in terms of
the ... more >>>

TR05-118 | 16th October 2005
Jin-Yi Cai, Vinay Choudhary

Valiant's Holant Theorem and Matchgate Tensors

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.

more >>>

TR01-030 | 25th April 2001
Jin-Yi Cai

S_2^p \subseteq ZPP^{NP}

We show that the class ${\rm S}_2^p$ is a subclass of
${{\rm ZPP}^{\rm NP}}$. The proof uses universal hashing, approximate counting
and witness sampling. As a consequence, a collapse first noticed by
Samik Sengupta that the assumption NP has small circuits collapses
PH to ${\rm S}_2^p$
becomes the strongest version ... more >>>

TR01-001 | 31st December 2000
Jin-Yi Cai

Essentially every unimodular matrix defines an expander

We generalize the construction of Gabber and Galil
to essentially every unimodular matrix in $SL_2(\Z)$. It is shown that
every parabolic
or hyperbolic fractional linear transformation explicitly
defines an expander of bounded degree
and constant expansion. Thus all but a vanishingly small fraction
of unimodular matrices define expanders.

more >>>

TR99-045 | 16th November 1999
Valentine Kabanets, Jin-Yi Cai

Circuit Minimization Problem

We study the complexity of the circuit minimization problem:
given the truth table of a Boolean function f and a parameter s, decide
whether f can be realized by a Boolean circuit of size at most s. We argue
why this problem is unlikely to be in P (or ... more >>>

TR99-006 | 10th March 1999
Jin-Yi Cai

Some Recent Progress on the Complexity of Lattice Problems

We survey some recent developments in the study of
the complexity of lattice problems. After a discussion of some
problems on lattices which can be algorithmically solved
efficiently, our main focus is the recent progress on complexity
results of intractability. We will discuss Ajtai's worst-case/
average-case connections, NP-hardness and non-NP-hardness,
more >>>

TR98-005 | 27th January 1998
Jin-Yi Cai

A new transference theorem and applications to Ajtai's connection factor

We prove a new transference theorem in the geometry of numbers,
giving optimal bounds relating the successive minima of a lattice
with the minimal length of generating vectors of its dual.
It generalizes the transference theorem due to Banaszczyk.
We also prove a stronger bound for the special class of ... more >>>

TR97-059 | 22nd December 1997
Jin-Yi Cai, Ajay Nerurkar

Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

Recently Ajtai showed that
to approximate the shortest lattice vector in the $l_2$-norm within a
factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large
constant $k$, is NP-hard under randomized reductions.
We improve this result to show that
to approximate a shortest lattice vector within a
factor $(1+ \mbox{dim}^{-\epsilon})$, for any
$\epsilon>0$, ... more >>>

TR95-019 | 14th April 1995
Jin-Yi Cai, Alan L. Selman

Average time complexity classes

TR95-006 | 1st January 1995
Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

Pseudorandom Generators, Measure Theory, and Natural Proofs

This paper proves that if strong pseudorandom number generators or
one-way functions exist, then the class of languages that have
polynomial-sized circuits is not small within exponential
time, in terms of the resource-bounded measure theory of Lutz.
More precisely, if for some \epsilon > 0 there exist nonuniformly
2^{n^{\epsilon}}-hard ... more >>>

TR94-016 | 12th December 1994
Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu

Efficient Average-Case Algorithms for the Modular Group

The modular group occupies a central position in many branches of
mathematical sciences. In this paper we give average polynomial-time
algorithms for the unbounded and bounded membership problems for
finitely generated subgroups of the modular group. The latter result
affirms a conjecture of Gurevich.

more >>>

ISSN 1433-8092 | Imprint