Interpolation by a Game

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]).     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Lattice gas generalization of the hard hexagon model. II. The local densities as elliptic functions

In a previous paper we considered an extension of the hard hexagon model to a solvable two-dimensional lattice gas with at most two particles per pair of adjacent sites. Here we use various mathematical identities (in particular Gordon's generalization of the Rogers-Ramanujan relations) to express the local densities in terms of elliptic functions. The critical behavior is then readily obtained.Supported in part by the National Science Foundation Grant MCS 8201733.     

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002     

Statistical mechanics of warm and cold unfolding in proteins

We present a statistical mechanics treatment of the stability of globular proteins which takes explicitly into account the coupling between the protein and water degrees of freedom. This allows us to describe both the cold and the warm unfolding, thus qualitatively reproducing the known thermodynamics of proteins. Received: 19 March 1998 / Revised and Accepted: 25 May 1998     

动力系统简介

本文对动力系统这一学科的历史、理论、应用以及与其他学科的联系作一简介.     

The nanogranular nature of C-S-H

Despite its ubiquitous presence as binding phase in all cementitious materials, the mechanical behavior of calcium-silicate-hydrates (C-S-H) is still an enigma that has deceived many decoding attempts from experimental and theoretical sides. In this paper, we propose and validate a new technique and experimental protocol to rationally assess the nanomechanical behavior of C-S-H based on a statistical analysis of hundreds of nanoindentation tests. By means of this grid indentation technique we identify in situ two structurally distinct but compositionally similar C-S-H phases heretofore hypothesized to exist as low density (LD) C-S-H and high density (HD) C-S-H, or outer and inner products. The main finding of this paper is that both phases exhibit a unique nanogranular behavior which is driven by particle-to-particle contact forces rather than by mineral properties. We argue that this nanomechanical blueprint of material invariant behavior of C-S-H is a consequence of the hydration reactions during which precipitating C-S-H nanoparticles percolate generating contact surfaces. As hydration proceeds, these nanoparticles pack closer to center on-average around two characteristic limit packing densities, the random packing limit (η=64%) and the ordered face-centered cubic (fcc) or hexagonal close-packed (hcp) packing limit (η=74%), forming a characteristic LD C-S-H and HD C-S-H phase.     

The property of being polynomial for Mal’tsev constraint satisfaction problems

A combinatorial constraint satisfaction problem aims at expressing in unified terms a wide spectrum of problems in various branches of mathematics, computer science, and AI. The generalized satisfiability problem is NP-complete, but many of its restricted versions can be solved in a polynomial time. It is known that the computational complexity of a restricted constraint satisfaction problem depends only on a set of polymorphisms of relations which are admitted to be used in the problem. For the case where a set of such relations is invariant under some Mal’tsev operation, we show that the corresponding constraint satisfaction problem can be solved in a polynomial time. __________ Translated from Algebra i Logika, Vol. 45, No. 6, pp. 655–686, November–December, 2006.     

On a point of order

A method of using algebraic curves to obtain estimates of critical points accurate enough to identify them as simple algebraic numbers (if that is what they are) is discussed and illustrated with an application to the (q-state Potts model on the triangular lattice for cases of pure two-site interactions and pure three-site interactions. In the latter case the critical point is conjectured to be . In a similar conjecture for the critical percolation probability on thedirected square lattice,q _c ^1/2 (q _c +3)=2(q _c +p _c =1).     

Hamiltonian limit of the 3D Zamolodchikov model

A two-dimensional quantum Hamiltonian _N,M commuting with the layer-to-layer transfer matrix of the three-dimensional Zamolodchikov model is derived. This Hamiltonian is defined on a lattice ofN×M sites. The special casesN×2, 2×M, and 3×M are studied.This paper is dedicated to Cyril Domb.