Open Hub
Open Hub

 Settings |  Report Duplicate

0
I Use This!
Very Low Activity

Commits : Listings

Analyzed about 7 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
Hardy-Ramanujan Approximate Ray Shooting Queries for Factors - Optimization in Computational Geometric Factorization ---------------------------------------------------------------------------------------------------------------------- 1. Ray Shooting Queries based on Hardy-Ramanujan Theorem for Normal Order of number of factors of an integer has been implemented as a new function. 2. Each approximate factor is queried by a ray from origin of slope tan(m*pi/(2*k*loglogN)) intersecting hyperbolic arc bow and approximate factors are: sqrt(N/[tan(m*pi/(2*k*loglogN))])-1 for m=1,2,3,...,kloglogN 3. Two integers have been factorized using local tile search and comparison between approximate factors and actual factors have been logged in: python-src/testlogs/DiscreteHyperbolicFactorizationUpperbound_TileSearch_Optimized.HardyRamanujanRayShootingQueries.log.21March2018 python-src/testlogs/DiscreteHyperbolicFactorizationUpperbound_TileSearch_Optimized.HardyRamanujanRayShootingQueries2.log.21March2018 4. Approximate Ray Shooting could be useful for integers having large value of factor multiplicity BigOmega (sum of prime factor powers) 5. Constant k has been hardcoded presently and has to be heuristically found. 6. Approximate Factors are helpful for sieving huge integers and binary search can be localized based on these approximate factors as beacons.It is not necessary to search the entire pixelated hyperbolic arc.
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - Hardy-Ramanujan Approximate Ray Shooting Queries - Computational Geometric Factorization
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Updated AsFer Design Document - Counterexample in Majority Voting, Belief Propagation, Intrinsic Merit
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Updated AsFer Design Document - SAT Solver Random Matrix LSMR/LSQR Analysis
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Updated AsFer Design Document - SAT Solver Update - nonuniform_choice3() updated for constant multiple in expansion of the variables array
Srinivasan Kannan
More... over 8 years ago
SAT Solver Update - nonuniform_choice3() updated for constant multiple in expansion of the variables array ----------------------------------------------------------------------------------------------------------------- 1. CNFSATSolver.py nonuniform_choice3() has been changed to expand the variables array by following relation: n + x = n*sqrt(alpha) x = n*(sqrt(alpha)-1) => array of n variables is expanded to array of size n*(sqrt(alpha)-damp) for alpha = number_of_clauses/number_of_variables 2. damp variable has been hardcoded to 2 than 1 which approximates theoretical 1/sqrt(m*n) probability well because of round-off. 3. This expansion creates an approximate nonuniform probability 1/n*sqrt(alpha) per literal excluding replicated skew variable which is filtered in the while loops 4. Example SAT Solver logs for 1000 variables and Alpha=4.267 has been committed to python-src/testlogs/CNFSATSolver.1000variablesAlpha4.267.log.19March2018 5. MAXSAT Approximation ratio again is 90-91% for 20+ random 3SATs and nonuniform per literal probability almost matches 1/sqrt(m*n) (till penultimate decimal)
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - SAT Solver Non-Uniform Choice Average Probabilities and Skew Variable
Srinivasan Kannan
More... over 8 years ago
SAT Solver has been updated for a new nonuniform_choice3() function based on an Epsilon Bias Test Snippet EpsilonBiasNonUniformChoice.py which has been added to repository. This is similar to nonuniform_choice2() but Probabilities of nonuniformly chosen literals are computed separately and updated within the while loops also. Algorithm is similar to nonuniform_choice2() which elongates a permutation by replicating a skew variable. Average probabilities of all variables other than skew variable almost match the random matrix 1/sqrt(m*n) probability. Logs which print these probabilities for 1000 variables and Alpha=1/Alpha=4.267 have been committed to testlogs/CNFSATSolver.1000variablesAlpha1.log.16March2018 and testlogs/CNFSATSolver.1000variablesAlpha4.267.log.16March2018.
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - SAT Solver Update - Variables and Alpha as parameters and two Alpha Versus MAXSAT ratio graph plots
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
SAT Solver Update - Variables and Alpha as parameters and two Alpha Versus MAXSAT ratio graph plots -------------------------------------------------------------------------------------------------------------------------------------------- SAT Solver has been updated to accept commandline parameters of number of variables and Alpha (Clause/Variable ratio) as: $python CNFSATSolver.py <number_of_variables> <alpha> Some debug prints have been changed. Following sets of SATs were solved and variation of MAXSAT approximation ratio versus Alpha has been captured as graph (for nonuniform_choice()): ----------------------------------------------------------- Number of Variables - 600 (after atleast 15 random 3SAT iterations) ----------------------------------------------------------- Alpha Observed MAXSAT Approximation Ratio ------- ----------------------------------- 1 94.5% 2 92.7% 3 91.5% 4 90.74% 4.267 90.45% 5 90.28% 6 90.25% ----------------------------------------------------------- Number of Variables - 300 (after atleast 15 random 3SAT iterations) ----------------------------------------------------------- Alpha Observed MAXSAT Approximation Ratio ------ ----------------------------------- 1 95% 2 93% 3 92% 4 90.6% 4.267 90.6% 5 90.49% 6 90.73%
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
SAT Solver Update - Non-uniform Choice 2 - 5000 variables and Alpha=4.267 and some intuition ------------------------------------------------------------------------------------------------------------------------------------------- SAT Solver has been updated for a new nonuniform choice function nonuniform_choice2() which has following algorithm: - Each permutation nPn of length n is elongated to n*n*alpha length array by replicating one of the variables (of largest index) - Literals are chosen from this new array as (n*n*alpha)P1 or (n*n*alpha)P3 - This creates a probability of fraction n/(n*n*alpha)=1/(n*alpha) for per literal choice. But this implementation was found to be no different from nonuniform_choice() which chooses a submatrix in per literal probability and therefore has been commented at present. MAXSAT approximation ratio observed was 88% for nonuniform_choice2() versus 90% for nonuniform_choice(). 5000 variables and Alpha=4.267 have been solved for few iterations and MAXSAT approximation ration is 90-91%. In all the benchmarks done so far, it has been observed that equal variables-clause combinations almost always converge to ~95% MAXSAT approximation ratio and Alpha=4.267 almost always converge to ~90-91%. Though these numbers are not conclusive and comprehensive, previous emerging pattern is too striking.
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - SAT Solvers and Phase Transition at Alpha=4.26
Srinivasan Kannan
More... over 8 years ago
SAT Solver Update - Non-Uniform Choice - 3200 variables and 3100 clauses and Alpha=4.26 Phase Transition ----------------------------------------------------------------------------------------------------------------------------------------- SAT Solver has been updated for some aesthetics - literal selection in non-uniform choice has been parametrized: sequential or simultaneous based on how three random literals are chosen per random 3SAT clause - sequentially as 3*nP1 or simultaneously as nP3. But no difference was observed between these two choices. Number of variables is set to 3200 and clauses to 3100. LSMR iteration has been increased to 5 and conlim reduced to 10. For few random 3SATs, observed MAXSAT approximation ratio average stands at ~95%. This accuracy has been observed to increase proportional to number of LSMR iterations. Commercial SAT solvers solve million variable-clause combinations in few seconds but in exponential time. Two other logs have been committed which solve the notorious Alpha=4.26 Clause/Variable ratio, which is known to be hardest subset of SAT and where a phase transition occurs from easy-to-hard. Number of unsatisfiable formulae increase for alpha > 4.26. MAXSAT approximation ratio observed for few random 3SAT instances is ~91% for number of variables 300 and 1000 and alpha=4.26. Observed per literal probability is skewed and substituting it in random matrix MAXSAT approximation ratio m^2*n^2*p^4 shows an anomaly. Another fact is observed per literal probability does not change at all for any number of iterations and stays put and because of this observed MAXSAT ratio converges within few iterations itself.
Srinivasan Kannan
More... over 8 years ago
SAT Solver Update - Non-Uniform Choice - For both equal and unequal number of clauses and variables -------------------------------------------------------------------------------------------------------------------------------------------- SAT Solver has been updated to include a new Non-Uniform Choice function for creating random SAT instances by choosing a literal by probability = 1/sqrt(m*n) which works for both equal and unequal number of clauses. This new function chooses non-uniformly. This function creates a submatrix of dimension (sqrt(m),sqrt(n)) chosen uniformly from larger matrix of (m clauses * n variables) by invoking choice() function to choose sqrt(m) rows from m rows and sqrt(n) columns from n columns. This uniformly chooses sqrt(m)*sqrt(n) entries from m*n entries of random matrix. This simulates the random matrix probability 1/sqrt(m*n) = sqrt(m*n)/m*n. From this submatrix 3 literals are chosen in succession to create a random 3SAT clause. Replace flag in choice() was set to False and True while creating random clause and there was not much difference and has been set to True.Logs for following 3 variables-clauses combinations have been committed to testlogs/ for ~100 random 3SAT instances each: 1000 variables, 1000 clauses - CNFSATSolver.1000variables1000clauses.NonUniformChoice.log.11March2018 1100 variables, 1200 clauses - CNFSATSolver.1100variables1200clauses.NonUniformChoice.log.11March2018 1200 variables, 1100 clauses - CNFSATSolver.1200variables1100clauses.NonUniformChoice.log.11March2018 From logs it is evident non-uniform choice function defined as previously approximately simulates the bias and almost matches theoretical 1/sqrt(m*n) random matrix expected per literal probability. LSMR algorithm has been chosen and MAXSAT approximation ratio is 91-93% for 100 iterations for each of the 3 variable-clause combinations. For equal variable-clause combinations, non-uniform choice function is equivalent to choice() and expected and observed probabilities per literal agree fully. Previous benchmarks have been done to verify the random matrix theory for Satisfiability problem which is a probabilistic average case P?=NP problem mentioned in hardness amplification conflicts previously. There is also a special case conflict with PARITYSAT Hastad-Linial-Mansour-Nisan Theorem circuit size counterexample mentioned in 53.15. Also unequal variable-clause SATs can be simulated by equal variable-clause SATs by setting redundant variables to 0 in disjunction of the literals in clauses or redundant clauses in conjunction to 1. Thus non-uniform choice may not be necessary. 11042,1 Bot
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
SAT Solver Update - 2500 clauses and 2500 variables - LSMR,LSQR and PseudoInverse Benchmarks
Srinivasan Kannan
More... over 8 years ago
------------------------------------------------------------------------------------------------------------------------- SAT Solver Update - 2500 clauses and 2500 variables - LSMR,LSQR and PseudoInverse Benchmarks ------------------------------------------------------------------------------------------------------------------------- 1. SAT Solver class has been changed to accept the algorithm as parameter which can be function names for LSMR,LSQR,PseudoInverse,SPSOLVE, SOLVE etc., 2. 2500 variables and 2500 clauses combination of SAT instances have been benchmarked by invoking LSMR, LSQR and PseudOInverse(pinv2) separately. 3. LSMR benchmark has 405 random 3SAT instances and is the fastest, LSQR and PseudoInverse(pinv2) benchmarks have only few random 3SAT instances. 4. LSQR and PseudoInverse(pinv2) are equally slower compared to LSMR by many orders of magnitude. 5. But approximation ratio for LSMR is 91-92% while LSQR and PseudoInverse trend at 96-97% though for small number of iterations. This probably implies an accuracy versus speed tradeoff: LSMR is less accurate but fast while LSQR and PseudoInverse(pinv2) are more accurate but less fast. 6. Observed probability per literal for all three coincide with random matrix 1/sqrt(m*n) uniform distribution probability per literal 7. These numbers are only representative figures and number of iterations for LSQR and PseudoInverse(pinv2) are too meagre.
Srinivasan Kannan
More... over 8 years ago
SAT Solver Update - pinv2() - 1000 variables and 1000 clauses
Srinivasan Kannan
More... over 8 years ago
+---------------------------------------------------------------------------------------------------------------------------------------------- +519. (THEORY and FEATURE-DONE) SAT Solver Update - pinv2() - 1000 variables and 1000 clauses - 6 March 2018 +---------------------------------------------------------------------------------------------------------------------------------------------- +SAT Solver has been updated to use pinv2() pseudoinverse function which has been documented to be faster. After removing some code causing +redundant bottleneck, 1000 variables-1000 clauses random SATs have been solved by pinv2() and matrix multiplication to find real assignments which have been rounded. This means solving a million entry matrix (1000*1000). MAXSAT approximation ratio is 97%-98% again. Probability per literal average observed coincides with theoretical value of 1/sqrt(m*n). It has to be noted that Random matrix expectation for solving SAT translated to linear system of equations is an average case solution and is not worst case. This >7/8 approximation could imply AverageP=AverageNP or PromiseP=PromiseNP (for equal number of variables-clauses) if not P=NP. This is the likely reason for observed per literal probability being 97% asymptotically less than theoretical per literal probability 100%.
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - SAT Solver Update - Moore-Penrose Pseudoinverse and Conflicts between SAT Solver and Hardness of Majority
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Hardness of Majority Voting, SAT Solver Update - Compressed Sensing and Moore-Penrose Pseudoinverse ----------------------------------------------------------------------------------------------------------------------------------------------- Approximate CNF SAT Solver has been updated to invoke Moore-Penrose Pseudoinverse function to compute approximate inverse of random 3SAT matrix and is multiplied as A^-1*b to find assignments x. Compressed Sensing implementation already uses pseudoinverse to decompress image from sketch which is similar to this SAT solver. Performance is almost similar to LSMR and MAXSAT approximation ratio hovers around 97-98% for 306 random 3SAT instances of 21 variables and 21 clauses. Randomized rounding threshold has been increased to 0.5 from 0.1 (a literal is set to 0 if it is < 0.5 and to 1 if >= 0.5). Observed per literal probabilities are equal to random matrix expected probability 1/sqrt(m*n). This reduces SAT solving to Compressed Sensing.
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Updated AsFer Design Document - Hardness Amplification for Majority+Voter Composition
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Updated AsFer Design Document - Corrections - Sensitivity Conjecture
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Updated AsFer Design Document - Majority+Voter Composition Hardness Amplification Lemma - Sensitivity Conjecture
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - Majority+Voter Composition Hardness Amplification Lemma
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - Least Square Approximate SAT Solver
Srinivasan Kannan
More... over 8 years ago
Least Squares LSMR SAT solver implementation has been updated to print LSMR internal calculations. Maximum iterations, conlim, atol, btol parameters have been set to least values for reducing latency. But this reduces MAXSAT accuracy to ~94% which is still above 88% (7/8 approximation). SciPy Sparse dsolve.spsolve() was tried for solving least squares by csc_matrix and there were nan errors.Finally, LSMR looks to be the best of the lot. Logs for few random 3SATs of (21 clauses, 21 variables) have been committed to testlogs/CNFSATSolver.21variables21clauses.log.4March2018. Observed average probability of choosing a literal again agrees quite well to 1/sqrt(m*n) Random Matrix theoretical probability as gleaned from logs.
Srinivasan Kannan
More... over 8 years ago
Recursive Lambda Function Growth - ConceptNet5 support, Per random walk Lambda Function Composition Tree Graph Tensor Neuron Network Intrinsic Merit ------------------------------------------------------------------------------------------------------- Recursive Lambda Function Growth implementation has been updated to print per random walk lambda function composition tree and its Graph Tensor Neuron Network Intrinsic Merit. Similarity has been made configurable by a flag to choose between 2 Antology Nets - WordNet and ConceptNet. Logs for this have been committed to testlogs/RecursiveLambdaFunctionnGrowth.log.GraphTensorNeuronNetwork.3March2018. Logs show a striking similarity between Maximum Intrinsic Merit Random Walk Composition and Centralities/Classes of the definition graph (excerpts below): ... grow_lambda_function3(): Maximum Per Random Walk Graph Tensor Neuron Network Intrinsic Merit : (u'(present(etc,(infrastructure(country,(urban(area,(Mumbai(city,largest))))))))', 3.790350877192983) ... ============================================================================================================= Unsupervised Classification based on top percentile Core numbers of the definition graph(subgraph of WordNet) ============================================================================================================= This document belongs to class: Mumbai ,core number= 12 This document belongs to class: infrastructure ,core number= 9 ... which is an evidence to the fact intrinsic merit peaks for random walks through high core numbered hub word vertices. Another aspect of ConceptNet's relevance to Graph Tensor Neuron Network is the strong resemblance of word2vec word embeddings to Connectomes in Computational Neuroscience (mentioned in references). Connectomes are the wiring diagrams for neurons in brain. Word2Vec clusters similar words of a text in vector space forming a clique. These word cluster cliques are wired together into a text graph. Thus Graph representation of Text and Neuron Cliques and Connectome Information Propagation Among Cliques of Neurons have uncanny similarities.
Srinivasan Kannan
More... over 8 years ago
Updated AsFer Design Document - ConceptNet5 and Graph Tensor Neuron Network Intrinsic Merit
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Approximate SAT Solver and ConceptNet REST client updates - 21 variables,21 clauses LSMR and Common Ancestor Distance in ConceptNet5
Srinivasan Kannan
as K.Srinivasan
More... over 8 years ago
Approximate SAT Solver and ConceptNet REST client updates - 21 variables,21 clauses LSMR and Common Ancestor Distance in ConceptNet5 --------------------------------------------------------------------------------------------------------------------------- 1.Least Square SAT solver has been updated to print more readable debug messages and highlight MAXSAT approximation ratio average for SATs solved thus far 2.Number of variables and clauses is set to 21,21 and MAXSAT ratio is 98% for 34 random 3SATs 3.Logs for 21,21 has been committed to testlogs/CNFSATSolver.21variables21clauses.log.28February2018 which shows the observed literal probabilities and random matrix 1/sqrt(m*n) literal probability agreeing well. 4.This is because of uniform unbiased (mostly) choice() when number of clauses = number of variables causing 1/sqrt(m*n) = 1/n 5.For unequal clauses and variables numbers, an epsilon biased PRG implementation in linux kernel is necessary (random.c might have to be rewritten) --------------------- 6.ConceptNet5 client has been updated to include a related() function wrapper which invokes /related REST endpoint for finding similar concepts. 7.ConceptNet5 finds related concepts by word embeddings implementation of word2vec which maps each word to a vector and similar words/concepts are clustered together in this vector space. More precisely, word distances are represented as a word-word 2 dimensional matrix/graph and sum of path edge weights between word pair is the distance. 8.For finding distance between two concepts a common ancestor algorithm has been implemented in new conceptnet_distance() function which recursively invokes related() to deep learn concepts and grows paths between the two concept endpoints. This recursion stops when paths grown from both ends meet i.e when there is a common ancestor (inspired by Savitch and USTCONN in logspace theorems). 9.Common ancestors are printed in end and distance between the concepts is also printed 10.Some example conceptnet_distance() invocations have been captured in ConceptNet/testlogs/ConceptNet5Client.log.28February2018
Srinivasan Kannan
More... over 8 years ago