Linear Phase Transition in Random Linear Constraint Satisfaction Problems

Our model is a generalized linear programming relaxation ofa much studied random K-SAT problem.Speci .cally,a set oflinear constraints C on K variables is fixed.From a pool of n variables, K variables are chosen uniformly at random and a constrain is chosen from C also uniformly at random.This procedure is repeated m times independently.

By: David P. Gamarnik

Published in: Probability Theory and Related Fields , volume 129, (no 3), pages 410-40 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .