All reports by Author Jin-Yi Cai:

__
TR13-048
| 27th March 2013
__

Jin-Yi Cai, Aaron Gorenstein#### Matchgates Revisited

__
TR07-020
| 11th March 2007
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: The Power of Dimensionality Resolved

__
TR07-019
| 10th March 2007
__

Jin-Yi Cai, Pinyan Lu#### On Block-wise Symmetric Signatures for Matchgates

__
TR07-003
| 5th January 2007
__

Jin-Yi Cai, Pinyan Lu#### Bases Collapse in Holographic Algorithms

__
TR06-145
| 1st December 2006
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: From Art to Science

__
TR06-135
| 22nd October 2006
__

Jin-Yi Cai, Pinyan Lu#### On Symmetric Signatures in Holographic Algorithms

__
TR06-048
| 9th April 2006
__

Jin-Yi Cai, Vinay Choudhary#### Some Results on Matchgates and Holographic Algorithms

__
TR06-018
| 8th February 2006
__

Jin-Yi Cai, Vinay Choudhary#### On the Theory of Matchgate Computations

__
TR05-118
| 16th October 2005
__

Jin-Yi Cai, Vinay Choudhary#### Valiant's Holant Theorem and Matchgate Tensors

__
TR01-030
| 25th April 2001
__

Jin-Yi Cai#### S_2^p \subseteq ZPP^{NP}

__
TR01-001
| 31st December 2000
__

Jin-Yi Cai#### Essentially every unimodular matrix defines an expander

__
TR99-045
| 16th November 1999
__

Valentine Kabanets, Jin-Yi Cai#### Circuit Minimization Problem

__
TR99-006
| 10th March 1999
__

Jin-Yi Cai#### Some Recent Progress on the Complexity of Lattice Problems

__
TR98-005
| 27th January 1998
__

Jin-Yi Cai#### A new transference theorem and applications to Ajtai's connection factor

__
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

__
TR95-006
| 1st January 1995
__

Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai#### Pseudorandom Generators, Measure Theory, and Natural Proofs

__
TR94-016
| 12th December 1994
__

Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu#### Efficient Average-Case Algorithms for the Modular Group

Jin-Yi Cai, Aaron Gorenstein

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 >>>

Jin-Yi Cai, Pinyan Lu

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

vectors.

We completely resolve the problem of the power of higher dimensional

bases. We prove that 2-dimensional bases are universal for

holographic ...
more >>>

Jin-Yi Cai, Pinyan Lu

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

identities.

Jin-Yi Cai, Pinyan Lu

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 >>>

Jin-Yi Cai, Pinyan Lu

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 >>>

Jin-Yi Cai, Pinyan Lu

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 >>>

Jin-Yi Cai, Vinay Choudhary

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 >>>

Jin-Yi Cai, Vinay Choudhary

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 >>>

Jin-Yi Cai, Vinay Choudhary

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.

Jin-Yi Cai

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 >>>

Jin-Yi Cai

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.

Valentine Kabanets, Jin-Yi Cai

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 >>>

Jin-Yi Cai

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 >>>

Jin-Yi Cai

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 >>>

Jin-Yi Cai, Ajay Nerurkar

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 >>>

Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

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 >>>

Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu

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.