Satisfiability of random systems of equations with nonuniform sampling of two-valued unknowns

DOI10.4213/MVK46MaRDI QIDQ4959031zbMATH OpenOpenAlexFDO

Authors A. V. Shapovalov

Publication date 15 September 2021

Published in Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/mvk46

zbMATH Keywords

satisfiabilityrandom hypergraphsprobabilistic algorithmssystem of discrete equations

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Hypergraphs (05C65)

Recommendations

• Properties of random systems of discrete equations with nonuniform sampling of unknowns
• Consistency and an algorithm recognising inconsistency of realisations of a system of random discrete equations with two-valued unknowns
• scientific article; zbMATH DE number 714477
• The probability of consistency of systems of random Boolean equations
• The satisfiability threshold for random linear equations

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3817702 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3480648 (Why is no real title available?)
• scientific article; zbMATH DE number 1245619 (Why is no real title available?)
• scientific article; zbMATH DE number 1245633 (Why is no real title available?)
• scientific article; zbMATH DE number 701118 (Why is no real title available?)
• scientific article; zbMATH DE number 714477 (Why is no real title available?)
• scientific article; zbMATH DE number 850374 (Why is no real title available?)
• scientific article; zbMATH DE number 850389 (Why is no real title available?)
• A threshold effect for systems of random equations of a special form
• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• Characteristics of random systems of linear equations over a finite field
• Consistency and an algorithm recognising inconsistency of realisations of a system of random discrete equations with two-valued unknowns
• Hypercycles in a random hypergraph
• Limiting characteristics of random systems of linear equations in residue ring
• On a probabilistic approach to solving systems of equations with integer-valued unknowns
• On the number of cycles in a random non-equiprobable graph
• Properties of random systems of discrete equations with nonuniform sampling of unknowns
• Random graphs.
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• The probability of consistency of systems of random Boolean equations

Cited in

(5)

• Phase transition in a system of random sparse Boolean equations
• Properties of random systems of discrete equations with nonuniform sampling of unknowns
• Random inequality constraint systems with few variables
• Consistency and an algorithm recognising inconsistency of realisations of a system of random discrete equations with two-valued unknowns
• Probability of unique integer solution to a system of linear equations

This page was built for publication: Satisfiability of random systems of equations with nonuniform sampling of two-valued unknowns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959031)