CASCADING RANDOM WALKS

DOI10.1142/S0129054105003182zbMath1097.68147OpenAlexW2026105979MaRDI QIDQ5462126

K. Subramani and Vahan Mkrtchyan

Publication date: 1 August 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054105003182

zbMATH Keywords

random walkcoin-flippingCascading walkQ2SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items (3)

Absorbing random walks and the NAE2SAT problem ⋮ Random walks for selected Boolean implication and equivalence problems ⋮ On memoryless provers and insincere verifiers

Cites Work

• Solving satisfiability in less than \(2^ n\) steps
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A simpler minimum spanning tree verification algorithm
• New methods for 3-SAT decision and worst-case analysis
• A theory of the learnable
• On the Complexity of Timetable and Multicommodity Flow Problems
• A randomized linear-time algorithm to find minimum spanning trees
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: CASCADING RANDOM WALKS