Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

Homotopy types for tamely approximable Sobolev maps between manifolds

We define a class ^p (M,N) of Sobolev maps from a manifoldM into a manifoldN, in such a way that each mapu ^p (M, N) has a well defined [p]-homotopy type, providedN satisfies a topological hypothesis. Using this, we prove the existence of minimizers in [p]-homotopy classes for some polyconvex variational problems.     

Inclusion-exclusion: Exact and approximate

It is often required to find the probability of the union of givenn eventsA ₁ ,...,A _n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A _i )= _i – _i<j Pr(A _i A _j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A _i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums _|S|=j Pr( _iS A _i ) forj=1,...k, approximates Pr(A _i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v _l ^m C _i is an instance of the general problem that had been extensively studied [7]. HereA _i is the set of assignments that satisfyC _i , and Pr( _iS A _i )=a _S /2ⁿ where _iS C _i is satisfied bya _S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa _S for, say, all cardinalities . Quite surprisingly, already the numbersa _S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

Some results about the spectrum of commutative Banach algebras under the weak topology and applications

LetA be a commutative Banach algebra with a nonempty spectrum A. By weak we denote the relative weak topology induced on A by (A ^*,A ^**). In this note we study some properties of the topological space (A, weak) and present some applications of the results obtained and tools used to amenability, weakly compact homomorphisms, weakly compact subsets of the spectrum of the uniform algebras and to a characterization of the synthesizable ideals of the algebraA.     

Variable step size destabilizes the Störmer/leapfrog/verlet method

For fixed step-sizeh the Störmer method is stable for the standard test equationÿ= ² y,>0, if and only ifh<2. We show that for variable step sizeh _n there does not exist a (positive) limit onh which ensures stability. Nor can we guarantee stability if, in addition, we limit the step size ratioh _n/h _n–1.This work was supported in part by National Science Foundation Grant DMS 90 15533.     

Perturbed unstable variational inequalities with unbounded operators on approximately given sets

The stability and convergence of the solutions of perturbed and regularized variational inequality to the solutions of the primary (unstable a priori) variational inequality with proper monotone operator are investigated. All the objects of inequality: the operatorA, the right-hand partf and the set of constrains are to be perturbed. At the same time no assumptions of boundedness and smoothness of the operatorA are used. The connection between the parameters of perturbations, which guarantees strong convergence of approximate solutions, is established. It is proved that the existence of the solution to the unperturbed variational inequality is necessary and sufficient condition for convergence of the regularized perturbed inequality solutions.This research was supported in part by the Ministry of Science Grant 3481-1-91 and by the Ministry of Absorption Center for Absorption in Science.     

The erdös-dushnik-miller theorem for topological graphs and orders

A topological graph is a graph G=(V, E) on a topological space V such that the edge set E is a closed subset of the product space V x V. If the graph contains no infinite independent set then, by a well-known theorem of Erdös, Dushnik and Miller, for any infinite set LV, there is a subset LL of the same oardinality |L| = |L| such that the restriction G L is a complete graph. We investigate the question of whether the same conclusion holds if we weaken the hypothesis and assume only that some dense subset AV does not contain an infinite independent set. If the cofinality cf (|L|)>|A|, then there is an L as before, but if cf (|L|)<-|A|, then some additional hypothesis seems to be required. We prove that, if the graph GA is a comparability graph and A is a dense subset, then for any set LV such that cf (|L|)>, there is a subset LL of size |L|=|L| such that GL is complete. The condition cf (|L|)> is needed.Research supported by NSERC grant #A5198.     

5－（4－乙酰氧基苯基），10，15，20－三苯基卟啉金属配合物修饰的铂支撑双层脂膜的IV性质

合成并表征了５－（４－乙酰氧基苯基），１０，１５，２０－三苯基卟啉及其金属配合物，将它们作为修饰物，制得铂支撑的双层脂膜，用循环伏安法研究了抗坏血酸的氧化还原反应，并对其机理作了探讨。     

Biological generation of tritiated vitamin D3 metabolites and their purification by high-performance liquid chromatography

Summary A simple, reproducible method for the biological synthesis of tritiated 24,25-dihydroxycholecalciferol, 25,26-dihydroxycholecalciferol and 1,25-dihydroxycholecalciferol is described. Kidney homogenates from both vitamin D deficient and replete chicks were usedin vitro to generate these dihydroxylated metabolites using 25 (23,24-³H) hydroxycholecalciferol as the substrate. Tritiated products were purified by Sephadex LH 20 chromatography followed by high-performance liquid chromatography; the identity of each metabolite was established by chromatography with authentic crystalline preparations.Presented at the Symposium organised by the Chromatography Discussion Group, held at Hatfield Lodge on 29 November 1979.