CASCADING RANDOM WALKS

DOI10.1142/S0129054105003182MaRDI QIDQ5462126zbMATH OpenOpenAlexFDO

Authors K. Subramani

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)

Recommendations

• Random walks for selected Boolean implication and equivalence problems
• Absorbing Random Walks and the NAE2SAT Problem
• Publication:4828947
• Solving the satisfiability problem by using randomized approach
• On 2-QBF truth testing in parallel

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1179314 (Why is no real title available?)
• scientific article; zbMATH DE number 1514781 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A randomized linear-time algorithm to find minimum spanning trees
• A simpler minimum spanning tree verification algorithm
• A theory of the learnable
• New methods for 3-SAT decision and worst-case analysis
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• On the Complexity of Timetable and Multicommodity Flow Problems
• Solving satisfiability in less than \(2^ n\) steps

Cited in

(8)

• A branching random walk among disasters
• Absorbing random walks and the NAE2SAT problem
• On memoryless provers and insincere verifiers
• scientific article; zbMATH DE number 1261202 (Why is no real title available?)
• Random walks for selected Boolean implication and equivalence problems
• scientific article; zbMATH DE number 2152205 (Why is no real title available?)
• scientific article; zbMATH DE number 1737509 (Why is no real title available?)
• Absorbing Random Walks and the NAE2SAT Problem

This page was built for publication: CASCADING RANDOM WALKS

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