On the critical exponents of random k‐SAT

There has been much recent interest in the satisfiability of random Boolean formulas. A random k‐SAT formula is the conjunction of m random clauses, each of which is the disjunction of k literals (a variable or its negation). It is known that when the number of variables n is large, there is a sharp transition from satisfiability to unsatisfiability; in the case of 2‐SAT this happens when m/n → 1, for 3‐SAT the critical ratio is thought to be m/n ≈ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called ν = ν_k (the smaller the value of ν the sharper the transition). Experiments have suggested that ν₃ = 1.5 ± 0.1. ν₄ = 1.25 ± 0.05, ν₅ = 1.1 ± 0.05, ν₆ = 1.05 ± 0.05, and heuristics have suggested that ν_k → 1 as k → ∞. We give here a simple proof that each of these exponents is at least 2 (provided the exponent is well defined). This result holds for each of the three standard ensembles of random k‐SAT formulas: m clauses selected uniformly at random without replacement, m clauses selected uniformly at random with replacement, and each clause selected with probability p independent of the other clauses. We also obtain similar results for q‐colorability and the appearance of a q‐core in a random graph. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 182–195, 2002     

The plus construction, Postnikov towers and universal central module extensions

Given a connected spaceX, we consider the effect of Quillen’s plus construction on the homotopy groups ofX in terms of its Postnikov decomposition. Specifically, using universal properties of the fibration sequenceAX→X→X ⁺, we explain the contribution of π _n X to π _n X ⁺, π _n+1 X ⁺ and π _n AX, π _n+1 AX explicitly in terms of the low dimensional homology of π _n X regarded as a module over π₁ X. Key ingredients developed here for this purpose are universal II-central fibrations and a theory of universal central extensions of modules, analogous to universal central extensions of perfect groups. Research partially supported by NSERC of Canada.     

Active long pulse shaping technique of pulsed CO2 laser using multi-pulse discharge control

We describe the pulse forming of pulsed CO₂ laser using multi-pulse superposition technique. Various pulse shapes, high duty cycle pulse forming network (PFN) are constructed by time sequence. This study shows a technology that makes it possible to make various long pulse shapes by activating SCRs of three PFN modules consecutively at a desirable delay time with the aid of a PIC one-chip microprocessor. The power supply for this experiment consists of three PFN modules. Each PFN module uses a capacitor, a pulse forming inductor, a SCR, a high voltage pulse transformer, and a bridge rectifier on each transformer secondary. The PFN modules operate at low voltage by driving the primary of HV pulse transformer. The secondary of the transformer has a full-wave rectifier, which passes the pulse energy to the load in a continuous sequence.We investigated various long pulse shapes as different trigger time intervals of SCRs among three PFN modules. As a result, we could obtain laser beam with various pulse shapes and durations from about 250 to 1000 μs.     

Efficient microwave induced direct α-halogenation of carbonyl compounds

A novel and direct method for the synthesis of α-halocarbonyl compounds using sequential treatment of carbonyl compounds with [hydroxy(tosyloxy)iodo]benzene followed by magnesium halides under solvent-free microwave irradiation conditions is described.     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Partially isometric dilations of noncommuting -tuples of operators

Given a row contraction of operators on a Hilbert space and a family of projections on the space that stabilizes the operators, we show there is a unique minimal joint dilation to a row contraction of partial isometries that satisfy natural relations. For a fixed row contraction the set of all dilations forms a partially ordered set with a largest and smallest element. A key technical device in our analysis is a connection with directed graphs. We use a Wold decomposition for partial isometries to describe the models for these dilations, and we discuss how the basic properties of a dilation depend on the row contraction.