Data Structures and Algorithms

Linear-Time Algorithms to Color Topological Graphs

Authors: Warren D. Smith
Comments: On www since 2005; uploading to VIXRA for archival purposes. Figure on last page 22 with caption on p.21.

We describe a linear-time algorithm for 4-coloring planar graphs. We indeed give an O(V+E+|χ|+1)-time algorithm to C-color V-vertex E-edge graphs embeddable on a 2-manifold M of Euler characteristic χ where C(M) is given by Heawood's corrected (minimax optimal) formula. Finally, there is a linear-time algorithm to 5-color a graph embedded on any fixed surface M except that an M-dependent constant number of vertices are left uncolored. All the algorithms are simple and practical and run on a deterministic pointer machine, except for planar graph 4-coloring which involves enormous constant factors and requires an integer RAM with a random number generator. All of the algorithms mentioned so far are in the ultraparallelizable deterministic computational complexity class "NC." We also have more practical planar 4-coloring algorithms that can run on pointer machines in O(VlogV) randomized time and O(V) space, and a very simple O(V)-time coloring algorithm for planar graphs which conjecturally uses 4 colors.
Category: Data Structures and Algorithms

1. Aes Seems Weak. 2. Linear Time Secure Cryptography,

Authors: Warren D. Smith
Comments: On www since 2007. Uploading to VIXRA for archival purposes. Figure on last page 26. Also Markus Grassl computed an accompnying 171-page table of BCH codes which I wish I could upload as "accompanying data."

We describe a new simple but more powerful form of linear cryptanalysis. It appears to break AES (and undoubtably other cryptosystems too, e.g. SKIPJACK). The break is "nonconstructive," i.e. we make it plausible (e.g. prove it in certain approximate probabilistic models) that a small algorithm for quickly determining AES-256 keys from plaintext-ciphertext pairs exists – but without constructing the algorithm! The attack's runtime is comparable to performing 64^w encryptions where w is the (unknown) minimum Hamming weight in certain binary linear error-correcting codes (BLECCs) associated with AES-256. If w<43 then our attack is faster than exhaustive key search. Probably w<10. (Also there should be ciphertext-only attacks if the plaintext is natural English.)

Even if this break breaks due to the underlying models inadequately approximating the real world, we explain how AES still could contain "trapdoors" which would make cryptanalysis unexpectedly easy for anybody who knew the trapdoor. If AES's designers had inserted such a trapdoor, it could be very easy for them to convince us of that. But if none exist, then it is probably infeasibly difficult for them to convince us of that.We then discuss how to use the theory of BLECCs tobuild cryptosystems provably1. not containing trapdoors of this sort,2. secure against our strengthened form of linear cryptanalysis,3. secure against ``differential'' cryptanalysis,4. secure against D.J.Bernstein's timing attack.Using this technique we prove a fundamental theorem:it is possible to thus-encrypt $n$ bits with security$2^{cn}$, via an circuit $Q_n$ containing $le c n$two-input logic gatesand operating in $le c log n$ gate-delays, where the three $c$s denote(possibly different) positive constants and $Q_n$ is constructiblein polynomial$(n)$ time.At the end we give tables of useful binary codes.
Category: Data Structures and Algorithms

Complexity of Minimization

Authors: Warren D. Smith
Comments: 15 Pages. On internet since 2000; uploading to VIXRA for archival purposes.

An important problem in numerical analysis is trying to minimize (or maximize) a real function F(x₁,x₂,...,x_d) of d real variables. We investigate (and survey) its computational complexity borderlines.

Results include (precise theorem statements are in the text): Minimizing, e.g., functions specified by polynomial formulas involving both trigonometric and ordinary arguments, is undecidable. Hence consider plain rational functions; we'll show minimizing these (more precisely, deciding whether the minimum lies below some threshold) is in NP. If the sum of the numerator and denominator degrees of a (multivariate) rational function is ≤4, then finding all its local minima is in P, except for the 4+0 case of a quartic polynomial (or its reciprocal) in which case it is NP-complete. (There is a slight caveat for the case 3+1; the "polynomial" runtime unfortunately depends also on an additional parameter, but for practical purposes this does not matter.) Indeed, even deciding whether a specified point is a localmin is NP-complete for a quartic. Minimizing a linear function in a cube is polynomial, but minimizing a quadratic in a cube is NP-complete. Minimizing a quadratic in a ball is in P, but it is NP-complete for a quartic (cubics: unknown). In all theseNP-completeness results, even approximating the value of the min is NP-complete, and the problems remain NP-complete even if all integers are input in unary. The P minimization algorithms for low degree rational functions involve new techniques of "multi-stage minimization" and "dimension reduction."

Minimizing functions "unimodal on lines," is in P. Solving systems of nonlinear equations F&8407;(x⃗)=0 is in P, if all the nonlinear functions $F_k are monotonic on lines. We present evidence that minimizing strictly unimodal functions (with exactly one minimum, and no saddlepoints) is exponentially hard; but if additionally the function obeys certain derivative bounds, then hardness seems to occur precisely when there are extremely long "winding valleys."
Category: Data Structures and Algorithms