Arrow Research search

Author name cluster

Jin-Yi Cai

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

57 papers
2 author rows

Possible papers

57

AAAI Conference 2023 Conference Paper

Properties of Position Matrices and Their Elections

  • Niclas Boehmer
  • Jin-Yi Cai
  • Piotr Faliszewski
  • Austen Z. Fan
  • Łukasz Janeczko
  • Andrzej Kaczmarczyk
  • Tomasz Wąs

We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix). We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random seems challenging and we propose a simpler algorithm, without hard guarantees. Next, we consider the problem of testing if a given matrix can be implemented by an election with a certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of checking if a given position matrix can be implemented by an election with a Condorcet winner. We complement our theoretical findings with experiments.

PDF Details DOI

MFCS Conference 2022 Conference Paper

Bounded Degree Nonnegative Counting CSP

  • Jin-Yi Cai
  • Daniel P. Szabo

Constraint satisfaction problems (CSP) encompass an enormous variety of computational problems. In particular, all partition functions from statistical physics, such as spin systems, are special cases of counting CSP (#CSP). We prove a complete complexity classification for every counting problem in #CSP with nonnegative valued constraint functions that is valid when every variable occurs a bounded number of times in all constraints. We show that, depending on the set of constraint functions ℱ, every problem in the complexity class #CSP(ℱ) defined by ℱ is either polynomial time computable for all instances without the bounded occurrence restriction, or is #P-hard even when restricted to bounded degree input instances. The constant bound in the degree depends on ℱ. The dichotomy criterion on ℱ is decidable. As a second contribution, we prove a slightly modified but more streamlined decision procedure (from [Jin-Yi Cai et al. , 2011]) for tractability. This enables us to fully classify a family of directed weighted graph homomorphism problems. This family contains both P-time tractable problems and #P-hard problems. To our best knowledge, this is the first family of such problems explicitly classified that are not acyclic, thereby the Lovász-goodness criterion of Dyer-Goldberg-Paterson [Martin E. Dyer et al. , 2006] cannot be applied.

Details

SODA Conference 2021 Conference Paper

An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures

  • Jin-Yi Cai
  • Tianyu Liu 0002

We give the first efficient approximate counting and sampling algorithms for the six-vertex model and the eight-vertex model on regions of the square lattice ℤ 2 in the low temperature regime. All previous algorithms for these problems are for high temperature settings, and rely on the rapid mixing of Markov chains. We prove that these natural Markov chains are torpidly mixing (exponentially slowly) in the low temperature settings. Rather than depending on rapid mixing MCMC, our algorithms are obtained by defining a special edge-2-coloring model, and showing an equivalence to (a linear combination of) abstract polymer models. We then prove the convergence of the cluster expansion of these polymer models. This allows us to employ the approach recently developed by Helmuth, Perkins, and Regts [25]. This combined with Barvinok's method [3, 42] via Taylor expansion (zero-free region of log partition function) gives the approximate counting and sampling algorithms. Significantly, these results provide the first counting problems that admit a fully polynomial time approximation scheme (FPTAS) on square lattice graphs but NP-hard to approximate even on bipartite graphs (rather than the weaker #BIS-hardness.)

Details

SODA Conference 2021 Conference Paper

New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification

  • Jin-Yi Cai
  • Zhiguo Fu
  • Shuai Shao 0001

We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. ∗ We further prove that there are no more: Together, they exhaust all P-time computable six-vertex models on planar graphs, assuming #P is not P. This leads to the following exact complexity classification: For every parameter setting in ℂ for the six-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. The new P-time cases in (2) provably cannot be subsumed by Kasteleyn's algorithm. They are obtained by a non-local connection to #CSP, defined in terms of a “loop space”. This is the first substantive advance toward a planar Holant classification with not necessarily symmetric constraints. We introduce Möbius transformation on ℂ as a powerful new tool in hardness proofs for counting problems.

Details

FOCS Conference 2020 Conference Paper

A Dichotomy for Real Boolean Holant Problems

  • Shuai Shao 0001
  • Jin-Yi Cai

We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions. It is proved that for every set F of real-valued constraint functions, Holant(F) is either P-time computable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this problem, and it uses many previous results and techniques. Dealing with some concrete functions plays an important role in this proof. In particular, two functions, called f6 and f8, and their associated families exhibit intriguing and extraordinary closure properties related to Bell states in quantum information theory.

Details

FOCS Conference 2020 Conference Paper

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

  • Jin-Yi Cai
  • Artem Govorov

The complexity of graph homomorphisms has been a subject of intense study [1], [2], [3], [4], [5], [6], [7], [8]. The partition function Z A (·) of graph homomorphism is defined by a symmetric matrix A over C. We prove that the complexity dichotomy of [7] extends to bounded degree graphs. More precisely, we prove that either G → Z A (G) is computable in polynomial-time for every G, or for some Δ > 0 it is #P-hard over (simple) graphs G with maximum degree Δ(G) ≤ Δ. The tractability criterion on A for this dichotomy is explicit, and can be decided in polynomial-time in the size of A. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, Z A (·) can be constructed from A, in the respective cases. cases.

Details

SODA Conference 2019 Conference Paper

Approximability of the Six-vertex Model

  • Jin-Yi Cai
  • Tianyu Liu 0002
  • Pinyan Lu

We take the first step toward a classification of the approximation complexity of the six-vertex model. This is a subject of extensive research in statistical physics. Our result concerns the approximability of the partition function on 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We show that the approximation complexity of the six-vertex model behaves dramatically differently on the two sides separated by the phase transition threshold. Furthermore, we present structural properties of the six-vertex model on planar graphs for parameter settings that have known relations to the Tutte polynomial T ( G; x, y ).

Details

SODA Conference 2019 Conference Paper

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms

  • Jin-Yi Cai
  • Artem Govorov

We develop a theory of graph algebras over general fields. This is modeled after the theory developed by Freedman, Lovász and Schrijver in [22] for connection matrices, in the study of graph homomorphism functions over real edge weight and positive vertex weight. We introduce connection tensors for graph properties. This notion naturally generalizes the concept of connection matrices. It is shown that counting perfect matchings, and a host of other graph properties naturally defined as Holant problems (edge models), cannot be expressed by graph homomorphism functions over the complex numbers (or even more general fields). Our necessary and sufficient condition in terms of connection tensors is a simple exponential rank bound. It shows that positive semidefiniteness is not needed in the more general setting.

Details

FOCS Conference 2015 Conference Paper

A Holant Dichotomy: Is the FKT Algorithm Universal?

  • Jin-Yi Cai
  • Zhiguo Fu
  • Heng Guo 0001
  • Tyson Williams

We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. In the study of counting complexity, such as #CSP, there are problems which are #P-hard over general graphs but P-time solvable over planar graphs. A recurring theme has been that a holographic reduction [36] to FKT precisely captures these problems. This dichotomy answers the question: Is this a universal strategy? Surprisingly, we discover new planar tractable problems in the Holant framework (which generalizes #CSP) that are not expressible by a holographic reduction to FKT. In particular, the putative form of a dichotomy for planar Holant problems is false. Nevertheless, we prove a dichotomy for #CSP 2, a variant of #CSP where every variable appears even times, that the presumed universality holds for #CSP 2. This becomes an important tool in the proof of the full dichotomy, which refutes this universality in general. The full dichotomy says that the new P-time algorithms and the strategy of holographic reductions to FKT together are universal for these locally defined counting problems. As a special case of our new planar tractable problems, counting perfect matchings (#PM) over k-uniform hypergraphs is P-time computable when the incidence graph is planar and k ≥ 5. The same problem is #P-hard when k = 3 or k = 4, also a consequence of the dichotomy. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is P-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5.

Details

FOCS Conference 2014 Conference Paper

The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems

  • Jin-Yi Cai
  • Heng Guo 0001
  • Tyson Williams

We show that an effective version of Siegel's Theorem on finiteness of integer solutions for a specific algebraic curve and an application of elementary Galois theory are key ingredients in a complexity classification of some Holant problems. These Holant problems, denoted by Holant(f), are defined by a symmetric ternary function f that is invariant under any permutation of the κ ≥ 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. The hardness, and thus the dichotomy, holds even when restricted to planar graphs. A special case of this result is that counting edge κ-colorings is #P-hard over planar 3-regular multigraphs for all κ ≥ 3. In fact, we prove that counting edge κ-colorings is #P-hard over planar r-regular multigraphs for all κ ≥ r ≥ 3. The problem is polynomial-time computable in all other parameter settings. The proof of the dichotomy theorem for Holant(f) depends on the fact that a specific polynomial p(x, y) has an explicitly listed finite set of integer solutions, and the determination of the Galois groups of some specific polynomials. In the process, we also encounter the Tutte polynomial, medial graphs, Eulerian partitions, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials.

Details

STOC Conference 2013 Conference Paper

A complete dichotomy rises from the capture of vanishing signatures: extended abstract

  • Jin-Yi Cai
  • Heng Guo 0001
  • Tyson Williams

We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions {F} on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric constraint functions (taking values without a finite modulus). We define and characterize all symmetric vanishing signatures. They turned out to be essential to the complete classification of Holant problems. The dichotomy theorem has an explicit tractability criterion. A Holant problem defined by a set of constraint functions {F} is solvable in polynomial time if it satisfies this tractability criterion, and is #P-hard otherwise. The tractability criterion can be intuitively stated as follows: A set {F} is tractable if (1) every function in {F} has arity at most two, or (2) {F} is transformable to an affine type, or (3) {F} is transformable to a product type, or (4) {F} is vanishing, combined with the right type of binary functions, or (5) {F} belongs to a special category of vanishing type Fibonacci gates. The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean #CSP. Holographic transformations play an indispensable role, not only as a proof technique, but also in the statement of the dichotomy criterion.

Details

STOC Conference 2012 Conference Paper

Complexity of counting CSP with complex weights

  • Jin-Yi Cai
  • Xi Chen 0001

We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions. We show that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our dichotomy theorem generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when F has a single symmetric binary function; (b) the problem of counting directed graph homomorphisms is the special case when F has a single but not-necessarily-symmetric binary function; and (c) the unweighted form of #CSP is when all functions in F take values in {0,1}.

Details

SODA Conference 2011 Conference Paper

Dichotomy for Holant* Problems of Boolean Domain

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant*( F ), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i. e. , a (non-zero) vector whose inner product with itself is zero.

Details

FOCS Conference 2010 Conference Paper

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights

  • Jin-Yi Cai
  • Xi Chen 0001

The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our theorem applies to all non-negative weighted form of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function Z A (G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability is algebraic using properties of polynomials.

Details

FOCS Conference 2010 Conference Paper

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i. e. , polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

Details

STOC Conference 2009 Conference Paper

Holant problems and counting CSP

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and CSP can be viewed as special cases of Holant Problems. We prove complexity dichotomy theorems in this framework. Because the framework is more stringent, previous dichotomy theorems for CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the CSP framework. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. The study of Holant Problems led us to discover and prove a complexity dichotomy theorem for the most general form of Boolean CSP where every constraint function takes values in the complex number field {C}.

Details

STOC Conference 2008 Conference Paper

A quadratic lower bound for the permanent and determinant problem over any characteristic! = 2

  • Jin-Yi Cai
  • Xi Chen 0001
  • Dong Li

In Valiant's theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field F of characteristic ≠2, and an integer n, what is the minimum m such that the permanent of an n x n matrix X=(x ij ) can be expressed as a determinant of an m x m matrix, where the entries of the determinant matrix are affine linear functions of x ij 's, and the equality is in F [X]. Mignon and Ressayre (2004) [11] proved a quadratic lower bound m=Ω(n 2 ) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠2.

Details

FOCS Conference 2008 Conference Paper

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

We propose a new method to prove complexity dichotomy theorems. First we introduce Fibonacci gates which provide a new class of polynomial time holographic algorithms. Then we develop holographic reductions. We show that holographic reductions followed by interpolations provide a uniform strategy to prove #P-hardness.

Details

FOCS Conference 2001 Conference Paper

On the Average-Case Hardness of CVP

  • Jin-Yi Cai

We prove a connection of the worst-case complexity to the average-case complexity based on the Closest Vector Problem (CVP) for lattices. We assume that there is an efficient algorithm which can approximately solve a random instance of CVP, with a non-trivial success probability. For lattices under a certain natural distribution, we show that one can approximately solve several lattice problems (including a version of CVP) efficiently for every lattice with high probability.

Details

FOCS Conference 2001 Conference Paper

S p 2 subseteq ZPP NP

  • Jin-Yi Cai

We show that the class S 2 is a subclass of ZPP 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 S 2 becomes the strongest version to date of the Karp-Lipton Theorem. We also discuss the problem of finding irrefutable proofs for S 2 in ZPP NP.

Details

FOCS Conference 1997 Conference Paper

Constant Depth Circuits and the Lutz Hypothesis

  • Jin-Yi Cai
  • D. Sivakumar
  • Martin J. Strauss

Resource-bounded measure theory is a study of complexity classes via an adaptation of the probabilistic method. The central hypothesis in this theory is the assertion that NP does not have measure zero in Exponential Time. This is a quantitative strengthening of NP/spl ne/P. We show that the analog in P of this hypothesis fails dramatically. In fact, we show that NTIME[n/sup 1/11/] has measure zero in P. These follow as consequences of our main theorem that the collection of languages accepted by constant-depth nearly exponential-size circuits has measure zero at polynomial time. In contrast, we show that the class AC/sup 0//sub 4/[/spl oplus/] of languages accepted by depth-4 polynomial-size circuits with AND, OR, NOT, and PARITY gates does not have measure zero at polynomial time. Our proof is based on techniques from circuit complexity theory and pseudorandom generators.

Details

FOCS Conference 1995 Conference Paper

Pseudorandom Generators, Measure Theory, and Natural Proofs

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

We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich (1994). We also provide a partial converse of this result.

Details

FOCS Conference 1995 Conference Paper

The Resolution of a Hartmanis Conjecture

  • Jin-Yi Cai
  • D. Sivakumar

Building on the recent breakthrough by M. Ogihara (1995), we resolve a conjecture made by J. Hartmanis (1978) regarding the (non) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC/sup 1/, then P collapses to NC/sup 1/.

Details

FOCS Conference 1994 Conference Paper

Efficient Average-Case Algorithms for the Modular Group

  • Jin-Yi Cai
  • Wolfgang H. J. Fuchs
  • Dexter Kozen
  • Zicheng Liu 0001

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 Y. Gurevich (1990). >

Details

FOCS Conference 1994 Conference Paper

The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices

  • Jin-Yi Cai
  • Richard J. Lipton
  • Yechezkel Zalcstein

We present a deterministic polynomial-time algorithm for the ABC problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial time algorithm, for the (easier) membership problem, for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions. >

Details

MFCS Conference 1992 Conference Paper

Promise Problems and Access to Unambiguous Computation

  • Jin-Yi Cai
  • Lane A. Hemachandra
  • Jozef Vyskoc

Abstract This paper studies the power of three types of access to unambiguous computation: nonadaptive access, fault-tolerant access, and guarded access. (1) Though for NP it is known that nonadaptive access has exponentially terse adaptive simulations, we show that UP has no such relativizable simulations: there are worlds in which ( k +1)-truth-table access to UP is not subsumed by k -Turing access to UP. (2) Though fault-tolerant access (i. e. , “1-helping” access) to NP is known to be no more powerful than NP itself, we give both structural and relativized evidence that fault tolerant access to UP suffices to recognize even sets beyond UP. Furthermore, we completely characterize, in terms of locally positive reductions, the sets that fault-tolerantly reduce to UP. (3) In guarded access, Grollmann and Selman's natural notion of access to unambiguous computation, a deterministic polynomial-time Turing machine asks questions to a nondeterministic polynomial-time Turing machine in such a way that the nondeterministic machine never accepts ambiguously. In contrast to guarded access, the standard notion of access to unambiguous computation is that of access to a set that is uniformly unambiguous—even for queries that it never will be asked by its questioner, it must be unambiguous. We show that these notions, though the same for nonadaptive reductions, differ for Turing and strong nondeterministic reductions.

Details

FOCS Conference 1989 Conference Paper

An Optimal Lower Bound on the Number of Variables for Graph Identification

  • Jin-Yi Cai
  • Martin Fürer
  • Neil Immerman

It is shown that Omega (n) variables are needed for first-order logic with counting to identify graphs on n vertices. This settles a long-standing open problem. The lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that three variables suffice to identify all graphs of color class size 3, and two variables suffice to identify almost all graphs. The lower bound is optimal up to multiplication by a constant because n variables obviously suffice to identify graphs on n vertices. >

Details

FOCS Conference 1989 Conference Paper

Lower Bounds for Constant Depth Circuits in the Presence of Help Bits

  • Jin-Yi Cai

The problem of how many extra bits of 'help' a constant depth circuit needs in order to compute m functions is considered. Each help bit can be an arbitrary Boolean function. An exponential lower bound on the size of the circuit computing m parity functions in the presence of m-1 help bits is proved. The proof is carried out using the algebraic machinery of A. Razborov (1987) and R. Smolensky (1987). A by-product of the proof is that the same bound holds for circuits with mod/sub p/ gates for a fixed prime p>2. The lower bound implies a random oracle separation for PH and PSPACE, which is optimal in a technical sense. >

Details

FOCS Conference 1989 Conference Paper

Subquadratic Simulations of Circuits by Branching Programs

  • Jin-Yi Cai
  • Richard J. Lipton

Boolean circuits and their simulations by bounded-width branching programs are considered. It is shown that every NC/sup 1/ circuit of size s can be simulated by a constant-width branching program of length s/sup 1. 811. .. /. Some related group-theoretic results are presented. >

Details

FOCS Conference 1988 Conference Paper

Take a Walk, Grow a Tree (Preliminary Version)

  • Sandeep N. Bhatt
  • Jin-Yi Cai

A simple randomized algorithm is presented for maintaining dynamically evolving binary trees on hypercube networks. The algorithm guarantees that: (1) nodes adjacent in the tree are within distance O(log log N) in an N-processor hypercube, and (2) with overwhelming probability, no hypercube processor is assigned more than O(1+M/N) tree nodes, where M is the number of nodes in the tree. The algorithm is distributed and does not require any global information. This is the first load-balancing algorithm with provably good performance. The algorithm can be used to parallelize efficiently any tree-based computation. It can also be used to maintain efficiently dynamic data structures such as quadtrees. A technique called tree surgery is introduced to deal with dependencies inherent in trees. Together with tree surgery, the study of random walks is used to analyze the algorithm. >

Details