Jump to ContentJump to Main Navigation
Information, Physics, and Computation$
Users without a subscription are not able to see the full content.

Marc Mézard and Andrea Montanari

Print publication date: 2009

Print ISBN-13: 9780198570837

Published to Oxford Scholarship Online: September 2009

DOI: 10.1093/acprof:oso/9780198570837.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 01 April 2020

Linear equations with Boolean variables

Linear equations with Boolean variables

(p.403) 18 Linear equations with Boolean variables
Information, Physics, and Computation

Marc Mézard

Andrea Montanari

Oxford University Press

Solving a system of linear equations over a finite field is arguably one of the most fundamental operations in mathematics. This chapter considers a specific ensemble of random linear systems over Boolean variables, named XORSAT, and discusses the structure of its set of solutions. In large instances, the affine subspace of solutions can exhibit a remarkably rich geometrical structure. When the ratio of equations to variables is increased, the system first gets into an intermediate phase where solutions cluster in many well separated regions of the hypercube. Then it encounters a second phase transition and gets into an ‘UNSAT’ phase where the probability of existence of a solution vanishes. The study uses belief propagation equations, and a combinatorial analysis of the 2-core in the associated factor graph.

Keywords:   linear system, Boolean variables, XORSAT, belief propagation, cluster, 2-core

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .