Self-witnessing polynomial-time complexity and prime factorization

For a number of computational search problems, the existence of a polynomial-time algorithm for the problem implies that a polynomial-time algorithm for the problem is constructively known. Some instances of such self-witnessing polynomial-time complexity are presented. Our main result demonstrates this property for the problem of computing the prime factorization of a positive integer, based on a lemma which shows that a certificate for primality or compositeness can be constructed for a positive integer p in deterministic polynomial time given a complete factorization of p - 1.     

Efficient p-adic Cell Decompositions for Univariate Polynomials

Cell decompositions are constructed for polynomials f(x)Z_p[x] of degree n, such that n<p, using O(n²) cells. When f is square-free this yields a polynomial-time algorithm for counting and approximating roots in Z_p. These results extend to give a polynomial-time algorithm in the bit model for fZ[x].     

Rectangular Tiling in Multidimensional Arrays

We study the following tiling problem in d dimensions: given a d-dimensional rectangular array of nonnegative numbers and an integer p, partition the array into at most p rectangular subarrays so that the maximum weight of any subarray is minimized; the weight of a subarray is the sum of its elements. The rectangular tiling problem is motivated by applications in data mining, data partitioning, and video compression. Recently, Khanna, Muthukrishnan, and Paterson [SODA '98], showed that the tiling problem is NP-complete and gave a 2.5-approximation algorithm for d = 2.In this paper, we extend their result to multidimensional arrays and give an algorithm with approximation ratio , for d ≥ 2. The algorithm can be implemented to run in worst-case time O(N + p log N) time, where N is the size of the array, and the constant is of the order d!. We also obtain a similar algorithm for the dual tiling problem, where the goal is to compute a tiling of weight at most W using as few tiles as possible. Our algorithm yields an approximation factor (2d + 1).We implemented our algorithm and ran simulation tests on multidimensional arrays with random data. In our limited experiments, the algorithm always produced approximations that were no worse than factor two from the optimal.     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Sparse pseudorandom distributions

The existence of sparse pseudorandom distributions is proved. These are probability distributions concentrated in a very small set of strings, yet it is infeasible for any polynomial-time algorithm to distinguish between truly random coins and coins selected according to these distributions. It is shown that such distributions can be generated by (nonpolynomial) probabilistic algorithms, while probabilistic polynomial-time algorithms cannot even approximate all the pseudorandom distributions. Moreover, we show the existence of evasive pseudorandom distributions which are not only sparse, but also have the property that no polynomial-time algorithm may find an element in their support, except for a negligible probability. All these results are proved independently of any intractability assumption.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary

Abstract. We present a deterministic polynomial-time algorithm that computes the mixed discriminant of an n -tuple of positive semidefinite matrices to within an exponential multiplicative factor. To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n -tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling. As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in R ⁿ to within an error which depends only on the dimension. This answers a question of Dyer, Gritzmann and Hufnagel. A ``side benefit' is a generalization of Rado's theorem on the existence of a linearly independent transversal.     

A finite algorithm for the continuousp-center location problem on a graph

LetG=(V,E) be an undirected graph with positive integer edge lengths. Letm be the number of edges inE, and letd be the sum of the edge lengths. We prove that the solution value to the continuousp-center location problem is a rationalp ₁/p ₂, where logp ₁=O(m ⁵ logd+m ⁶ logp),i=1,2. This result is then used to construct a finite algorithm for the continuousp-center problem.     

A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

Algorithmic Chernoff-Hoeffding inequalities in integer programming

Proofs of classical Chernoff-Hoeffding bounds has been used to obtain polynomial-time implementations of Spencer's derandomization method of conditional probabilities on usual finite machine models: given m events whose complements are large deviations corresponding to weighted sums of n mutually independent Bernoulli trials. Raghavan's lattice approximation algorithm constructs for 0-1 weights, and integer deviation terms in O(mn)-time a point for which all events hold. For rational weighted sums of Bernoulli trials the lattice approximation algorithm or Spencer's hyperbolic cosine algorithm are deterministic precedures, but a polynomial-time implementation was not known. We resolve this problem with an O(mn²log $ {{mn}\over{\epsilon}} $)-time algorithm, whenever the probability that all events hold is at least ϵ > 0. Since such algorithms simulate the proof of the underlying large deviation inequality in a constructive way, we call it the algorithmic version of the inequality. Applications to general packing integer programs and resource constrained scheduling result in tight and polynomial-time approximations algorithms. © 1996 John Wiley & Sons, Inc.     

A spectral technique for random satisfiable 3CNF formulas

Let I be a random 3CNF formula generated by choosing a truth assignment ? for variables x₁, x_n uniformly at random and including every clause with i literals set true by ? with probability p_i, independently. We show that for any constants 0 ≤ η₂,η₃ ≤ 1 there is a constant d_min so that for all d ≥ d_min a spectral algorithm similar to the graph coloring algorithm of Alon and Kahale will find a satisfying assignment with high probability for p₁ = d/n², p₂ = η₂d/n², and p₃ = η₃d/n². Appropriately setting the η_i's yields natural distributions on satisfiable 3CNFs, not‐all‐equal‐sat 3CNFs, and exactly‐one‐sat 3CNFs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The regular polyhedra of type {p, 3} with 2p vertices

G(p, d) is a cubic (3-valent) graph consisting of a p-gon and a (p/d)-gon (a starpolygon) with corresponding vertices joined (the notation admits anomalous cases, when d=1 or (d, p)>1), and with a high degree of symmetry. It is shown here that the seven possible graphs G(p, d) are just the edge-graphs of the regular polyhedra of type {p, 3} with 2p vertices, and therefore 3p edges, 6 faces, and symmetry group of order 12p.     

Finding Skew Partitions Efficiently

A skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts A, B, C, D such that there are all possible edges between A and B and no edges between C and D. We present a polynomial-time algorithm for testing whether a graph admits a skew partition. Our algorithm solves the more general list skew partition problem, where the input contains, for each vertex, a list containing some of the labels A, B, C, D of the four parts. Our polynomial-time algorithm settles the complexity of the original partition problem proposed by Chvátal in 1985 and answers a recent question of Feder, Hell, Klein, and Motwani.     

Small cliques in random graphs

For d ≥ 1, a d-clique in a graph G is a complete d-vertex subgraph not contained in any larger complete subgraph of G. We investigate the limit distribution of the number of d-cliques in the binomial random graph G(n, p), p = p(n), n→∞.     

Carleson measures and the BMO space on the p ‐adic vector space

For a prime number p, let Q _p be the p ‐adic field and let Q _p ^d denote a vector space over Q _p which consists of all d ‐tuples of Q _p . Then we study the p ‐adic version of the Calderón–Zygmund decomposition, Carleson measures on the vector space Q _p ^{d +1} and the space BMO ( Q _p ^d ) of functions of bounded mean oscillation on Q _p ^d . In particular, it turns out that the operator norms of various oncoming operators are independent of the dimension d and the prime number p, which is one of the big differences from that of the Euclidean case. Interestingly, the independence of the dimension d and p makes it possible to develop Harmonic Analysis on the infinite dimensional p ‐adic vector space as the importance had already been pointed out in the Euclidean case (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Sharp Lp decay of oscillatory integral operators with certain homogeneous polynomial phases in several variables

In this paper, we obtain the L~p decay of oscillatory integral operators T_λ with certain homogeneous polynomial phase functions of degree d in(n + n)-dimensions; we require that d 2 n. If d/(d-n) p d/n,the decay is sharp and the decay rate is related to the Newton distance. For p = d/n or d/(d-n), we obtain the almost sharp decay, where "almost" means that the decay contains a log(λ) term. For otherwise, the L~p decay of T_λ is also obtained but not sharp. Finally, we provide a counterexample to show that d/(d-n) p d/n is not necessary to guarantee the sharp decay.     

Line-graphical degree sequences

A degree sequence π = (d₁, d₂,…,d_p), with d₁ ≥ d₂ ≥…≥ d_p, is line graphical if it is realized by the line graph of some graph. Degree sequences with line-graphical realizations are characterized for the cases d₁ = p - 1, d₁ = p - 2, d₁ ≤ 3, and d₁ = d_p. It is also shown that if a degree sequence with d₁ = p-1 is line graphical, it is uniquely line graphical. It follows that with possibly one exception each line-graphical realization of an arbitrary degree sequence must have either C₅, 2K₁, + K₂, K₁ + 2K₂, or 3K₁, as an induced subgraph.     

On the connectivity of maximal planar graphs

Let d₁ ? d₂ ? … ? d_p be the vertex degrees of a maximal planar graph G. Etourneau has shown that if d₁ ? 6 and d_p = 5, then G is 5-connected. We generalize Etourneau's result by giving sufficient conditions in terms of the vertex degrees for G to be d_p -connected.     

<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>-Integrability,Supports of Fourier Transforms and Uniqueness for Convolution Equations

It is proved that a nonzero function is not in L^p(Rⁿ) with p \le 2n/d if its Fourier transform is supported by a d-dimensional submanifold. It is shown that the assertion fails for p > 2n/d and d \ge n/2. The result is applied for obtaining uniqueness theorems for convolution equations in L^p-spaces.     

Groups of Units of Finite Commutative Group Rings*

Let R be a finite commutative ring with identity and ? _{p ^d} be the cyclic group of prime power order. Define R? _{p ^d} to mean the group ring of ? _{p ^d} over R. We determine the structure of the group of units of R? _{p ^d} in the case when R is generated by an element whose order is not divisible by p.