3 papers
cs.DS2026
New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
Sanjay Jain, Junqiang Peng, Frank Stephan +2
Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical P-complete problem, it represents a fundame…
cs.DS2024
An Improved Algorithm for Sparse Instances of SAT
Sanjay Jain, Tzeh Yuan Neoh, Frank Stephan
We show that the CNF satisfiability problem (SAT) can be solved in time , where is either the maximum number of occurrences of any variable or the average…
math.LO2024
Classifying different criteria for learning algebraic structures
Nikolay Bazhenov, Vittorio Cipriani, Sanjay Jain +2
In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a lear…