Open Hub
Open Hub

 Settings |  Report Duplicate

0
I Use This!
Very Low Activity

Commits : Listings

Analyzed about 4 hours ago. based on code collected 1 day ago.
Nov 05, 2025 — Nov 05, 2026
Commit Message Contributor Files Modified Lines Added Lines Removed Code Location Date
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document and CNFSATSolver.py
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
More... about 9 years ago
(*) Bugs fixed in prob_dist() (*) restored lsmr() (*) logs for some other clause-variable combinations have been committed to testlogs/. Observed per literal probability is close to random matrix probability of 1/sqrt(mn)
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
More... about 9 years ago
--------------------------------------------------------------------------------------------------------------------------------------- CNF3SAT Approximate Solver Update - All possible variable-clause combinations --------------------------------------------------------------------------------------------------------------------------------------- (*) Solve_SAT2() function has been changed to take both number of variables and clauses as parameters (*) Bug in EquationsB creation has been fixed so that length of b equals number of clauses. This was causing dimension mismatch and incompatible dimensions in LSMR and LSQR (*) Logs for 18*16 clauses-variables random 3CNFs have been committed to testlogs/. MaxSAT percentage is ~96% after 1200 random CNF iterations . Per literal probability is too less than 1/sqrt(mn) obtained from random matrix analysis and therefore converges much below 100%.
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
+-------------------------------------------------------------------------------------------------------------------------------------------- +454. (FEATURE and THEORY) Commits - Approximate SAT solver - 15 September 2017 +-------------------------------------------------------------------------------------------------------------------------------------------- +(*) Some debug statements have been included to print average probability of each literal's occurrence in random 3CNF. +(*) SATsolver has been re-executed with 20 clauses and 20 variables and probability of occurrence of each literal has been logged. +(*) This was necessitated to ascertain the pseudorandomness of the clauses and CNFs created. +(*) Average probability of a literal is less than previous estimate of 1/n = 1/20 = 0.05 for 100% satisfied clauses but still converges to usual 97% for 100 iterations. +(*) logs committed to testlogs/
Srinivasan Kannan
More... about 9 years ago
+-------------------------------------------------------------------------------------------------------------------------------------------- +454. (FEATURE and THEORY) Commits - Approximate SAT solver - 15 September 2017 +-------------------------------------------------------------------------------------------------------------------------------------------- +(*) Some debug statements have been included to print average probability of each literal's occurrence in random 3CNF. +(*) SATsolver has been re-executed with 20 clauses and 20 variables and probability of occurrence of each literal has been logged. +(*) This was necessitated to ascertain the pseudorandomness of the clauses and CNFs created. +(*) Average probability of a literal is less than previous estimate of 1/n = 1/20 = 0.05 for 100% satisfied clauses but still converges to usual 97% for 100 iterations. +(*) logs committed to testlogs/
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document - Corrections to Least Square Error estimation of Approximate SAT solver
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
------------------------------------------------------------------------------------------------------------------------------------------------ Analysis of Error Upperbound for Approximate CNFSAT Solver based on Lovasz Local Lemma clause dependency digraph - continued - 1 September 2017 ------------------------------------------------------------------------------------------------------------------------------------------------ (*) Least Squares lsqr() function has been replaced by recent lsmr() least square function mentioned to be faster. (*) For 10 variables and 10 clauses for 54068 random 3CNF iterations following were the percentage of satisfied CNFs and clauses satisfied per CNF: Percentage of CNFs satisfied so far: 79.6722706172 Average Percentage of Clauses per CNF satisfied: 97.6276609517 (*) Again the percentage of clauses satisfied per random 3CNF converges to ~98% after ~54000 random 3CNFs. (*) The clauses are created by randomly choosing each literal and its negation independent of any other literal or clause and thus are identically, independently distributed. CNFs can repeat since this is not a permutation. (*) Repetitive convergence of number of clauses satisfied per CNF to 98% is mysterious in varied clause-variable combinations. (*) Previous error bound analysis does not assume least squares and is based only on LLL. But Least Squares is about sum of squares of errors minimization i.e Error^2 = |Ax-b|^2 is minimized e.g A'Ax=A'b, partial first derivative of error set to 0. System of equations translated from each 3CNF is overdetermined or underdetermined mostly i.e number of variables and number of clauses are not equal. (*) Motivation for least squares for boolean CNF is the relaxation achieved: An example assignment for a literal, 0.88 is inclined towards boolean 1 and 0.02 is inclined towards boolean 0. (*) Convergence to 98% implies probability of average number of clauses satisfied per 3CNF > 0.98n must be almost 0. (*) Following Binomial Tail Bound: Pr[#SATclauses >= 0.98n] <= e^(-n*(0.98log(0.98e(d+1)) + 0.02log(0.02(ed+e)/(ed+e-1)))) is maximized when there are no overlaps - d=0. Pr[#SATclauses >= 0.98n] <= e^(-n*(0.98log(0.98e) + 0.02log(0.02(e)/(e-1)))) Pr[#SATclauses >= 0.98n] <= e^(-n*(0.41701 - 0.02999) Pr[#SATclauses >= 0.98n] <= e^(-n*0.38701) ~ 0 for large n.
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
More... about 9 years ago
-------------------------------------------------------------------------------------------------------------------------------------------- Approximate CNFSAT Solver update - SciPy Sparse --------------------------------------------------------------------------------------------------------------------------------------------- (*) imported scipy.sparse.linalg least squares function lsqr(). (*) Number of clauses and variables set to 18 each. (*) After 673 iterations of Random 3CNFs following satisfied clauses data were observed: Percentage of CNFs satisfied so far: 58.7537091988 Average Percentage of Clauses per CNF satisfied: 97.0161556215
Srinivasan Kannan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago
Updated AsFer Design Document
Srinivasan Kannan
as K.Srinivasan
More... about 9 years ago