6323016
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.
1980209
Basis Collapse in Holographic Algorithms
Abstract.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 problem without modulo 7 is #P-complete, and counting mod 2 is NP-hard.We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a Basis Folding Theorem showing that in a natural setting the support vectors can be simulated by bases of dimension 2.
47553632
On the Theory of Matchgate Computations
Valiant has proposed a new theory of algorithmic computation based on perfect matchings and Pfaffians. We study the properties of matchgates - the basic building blocks in this new theory. We give a set of algebraic identities which completely characterizes these objects for arbitrary numbers of inputs and outputs. These identities are derived from Grassmann-Plucker identities. The 4 by 4 matchgate character matrices are of particular interest. These were used in Valiant's classical simulation of a fragment of quantum computations. For these 4 by 4 matchgates, we use Jacobi's theorem on compound matrices to prove that the invertible matchgate matrices form a multiplicative group. Our results can also be expressed in the theory of holographic algorithms in terms of realizable standard signatures. These results are useful in establishing limitations on the ultimate capabilities of Valiant's theory of matchgate computations and holographic algorithms.
41950213
Holographic algorithms: From art to science
We develop the theory of holographic algorithms initiated by Leslie Valiant. First we define a basis manifold. Then we characterize algebraic varieties of realizable symmetric generators and recognizers on the basis manifold, and give a polynomial time decision algorithm for the simultaneous realizability problem. These results enable one to decide whether suitable signatures for a holographic algorithm are realizable, and if so, to find a suitable linear basis to realize these signatures by an efficient algorithm. Using the general machinery we are able to give unexpected holographic algorithms for some counting problems, modulo certain Mersenne type integers. These counting problems are #P-complete without the moduli. Going beyond symmetric signatures, we define d-admissibility and d-realizability for general signatures, and give a characterization of 2-admissibility and some general constructions of admissible and realizable families.
11342779
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results
We consider the problem of proving circuit lower bounds against the polynomial-time hierarchy. We give both positive and negative results. For the positive side, for any fixed integer k > 0, we give an explicit Σ2p language, acceptable by a Σ2p-machine with running time O(nk2+k), that requires circuit size > nk. For the negative side, we propose a new stringent notion of relativization, and prove under this stringent relativization that every language in the polynomial-time hierarchy has polynomial circuit size. (For technical details, see also [CW03].)
28522023
Essentially Every Unimodular Matrix Defines an Expander 


AbstractAbstract. We generalize the construction of Gabber and Galil to essentially every unimodular matrix in SL2 (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.

44495329
Enumeration on Nonseparable Planar Maps
Abstract This paper provides some functional equations satisfied by the generating functions for nonseparable rooted planar maps with the valency of root-vertex, the number of edges and the valency of root-faces of the maps as three parameters. But the solutions of these equations can only be obtained indirectly by considering some relations between nonseparable and general rooted planar maps. One of them is an answer to the open problem 6.1 in Liu (1983, Comb. Optim. CORR83-26, University of Waterloo).
38019738
Energy‐efficient selective cache invalidation
In a mobile environment, users of portable computers can query databases over the wireless communication channels. To reduce contention on the limited bandwidth of the wireless channels, frequently accessed data are cached at the mobile clients. However, maintenance of the cache consistency is complicated by the mobile clients' frequent disconnection to conserve energy. One promising approach in the literature is for the server to periodically broadcast invalidation reports from which clients can salvage their cache content that are still valid. This mechanism is, however, not energy efficient as clients are expected to examine the entire invalidation report. In this paper, we reexamine the cache coherency problem and propose three novel cache coherency schemes. While these schemes are based on periodic broadcast of invalidation reports, they allow clients to selectively tune to the portions of the invalidation report that are of interest to them. This allows the clients to minimize the power consumption when invalidating their cache content. We conducted extensive studies based on a simulation model. Our study shows that the proposed schemes are not only effective in salvaging the cache content that are still valid (and hence result in lower access time), but are also efficient in energy utilization. While none of the proposed algorithms is superior in both the access time and energy efficiency, one of the schemes, Selective Cache Invalidation, provides the best overall performance.
5733190
Automating the drug scheduling of cancer chemotherapy via evolutionary computation
This paper presents the optimal control of drug scheduling in cancer chemotherapy using a distributed evolutionary computing software. Unlike conventional methods that often require gradient information or hybridization of different approaches in drug scheduling, the proposed evolutionary optimization methodology is simple and capable of automatically finding the near-optimal solutions for complex cancer chemotherapy problems. It is shown that different number of variable pairs in evolutionary representation for drug scheduling can be easily implemented via the software, since the computational workload is shared and distributed among multiple computers over the Internet. Simulation results show that the proposed evolutionary approach produces excellent control of drug scheduling in cancer chemotherapy, which are competitive or equivalent to the best solutions published in literature.
12735579
The enumeration of rooted nonseparable nearly cubic maps
Abstract This paper provides the functional equations satisfied by the generating functions for enumerating rooted nonseparable near-cubic planar maps with the size and the valency of root-vertex and/or root-face of the maps as parameters. Moreover, explicit expressions of these functions are also derived. Two of them are summation-free.
38252080
A New Transference Theorem in the Geometry of Numbers
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. The theorem is motivated by our efforts to improve Ajtai's connection factors in the connection of average-case to worst-case complexity of the shortest lattice vector problem. Our proofs are non-constructive, based on methods from harmonic analysis.