ML + ATP + collatz = ? (via weka)

:idea: hi all here are some wild half baked ideas and slightly )( more on using/ combining ML (machine learning) with ATP (automated theorem proving). both topics have been big in this blog and lately am trying to harmmer out some (new) ideas on how to merge them in a grandiose 21st century vision. there are also some preliminary experiments here.

how would one apply an ML algorithm to collatz? the whole area is quite unexplored of uniting ML algorithms with number theory or TCS proofs but yet seems open to experimentation. number theoretic problems are similar to analyzing pseudorandom functions, or functions with “signal mixed with noise” much like with Big Data. have long had a nagging suspicion theres something potentially big lurking in this (right now seemingly) exotic marriage. ie a tip/ (very big?) iceberg floating around. ML is absolutely centric to empirical approaches to problems for decades and is now after years of sometimes painstaking development on very strong theoretical and practical footing.

it appears to me the sensible main/ natural idea on how to apply it would be to try to create a prediction algorithm for trajectory stopping distance, the key “apparently unpredictable” aspect. stopping distance is not known to be bounded (not sure why wrote those words, “lol”) but is bounded for all experimental values. suppose one came up with a learning algorithm that predicted the pseudorandom-looking stopping distances. the error scaling would be a key factor. does the error increase or worse, “blow up” somehow as the model scales to very large numbers? this is a nonobvious & maybe sort of subtle question that could lead to a lot of study wrt the different ML algorithms.

Continue reading

chrome hardcore poweruser bookmark sync (defect) blues :(

:evil: hi all a quick note about a recent cyberglitch thats really extremely bumming me out, crimping my style! have been using chrome for years as a heavy/ hardcore power user, it seems to be the most tuned/ high performance browser around. also heavily use the bookmark management and cloud synchronize features (~5K bookmarks and counting lying around for half baked blog concepts/ themes/ ideas, personal research/ projects, much else, etc!). but ouch! that seems to have gotten clobbered recently. my bookmark and history syncing silently started failing across devices.

started to look into it and it seems to coincide with an update by google to their bookmarks manager. am not the only one hating this new interface! google made it mandatory and rolled it out to all users despite massive user complaints/ pushback on the beta. was starting to get the hang of it (not really liking it but finding it workable) but the failed syncing is a massive dealbreaker for me. (its still not clear if the two issues are connected but they’re suspiciously close.)

Continue reading

AI/ robotics spring geek fest, zeitgeist, movies & performances etc

sonoya :star: :star: :star: :!: hi all this blog is triggered by the fabulous-but-creepy new movie EX MACHINA. in a word: outstanding! [a25][a26][a27][a28] :D

saw it saturday and was really blown away. it has a violent ending but it seemed almost shakespearean. great scifi movies seem not so common, there are maybe only a few every few years. to me this movie had almost “matrix level” intellectual and performance quality and the director has topnotch nerd cred instigating a reddit mini-orgasm.[a29]

have been tracking various robotics/ AI links and my bookmarks runneth over lately. can barely keep up. the two areas are increasingly dramatically fusing in scientific/ research realms and this is lately reflected in the vivid/ visceral hollywood imagination.

Continue reading

flash crash program trading villain Sarao charged by USDoJ

imagehi all. on the topic of program/ high frequency trading 1st considered here ~1yr ago. recently the USDOJ (US dept justice) announced a charge against a daytrader for “illegal trading”. this is a very rare charge, am not even clear on the legality of it, it was not really explained in their press release. looking over the charges, they are for “fraud and manipulation of prices” and a charge called “spoofing”. this made international headlines.[a11][a12][a13][a15] there is some indication this may have played a key role in the so-called “flash crash” from years ago (May 2010)

“spoofing” appears to be the process of posting bids or asks that are not later committed as trades, esp for large amts of money. its funky, but is it really illegal? a trading exchange is an auction and the mechanism not to follow through on a bid or an ask is built into the system. seems these types of rules need to be handled with algorithm constraints/ limits built into the code, not nec legalities/ laws & trials.

however, has anything like this ever been prosecuted before?

the defendant apparently used program trading mechanisms, but this is quite disturbing from a CS pov. program trading is rampant in markets, and highly used by large multibilliondollar hedge funds, and admittedly its a gray area legally. what are the legalities of a program that makes/ effects trades but behaves erratically?

Continue reading

arithmetic circuit complexity, Valiants VP=?VNP, recent advances/ breakthroughs, new directions

462016_orig :star: :idea: :!: :?: hi all. recently there have been some interesting results on arithmetic circuit complexity as cited by fortnow, which relates the classes VP/VNP invented by valiant over ~3½ decades ago. the VP=?VNP problem has been reduced to a depth-4 circuit question which is very impressive and maybe verging/ bordering on a breakthrough, afaik for 1st time reducing it to a finite/ constant depth.[a1][a7][a8] (shades/ echoes of Zhangs 2013 breakthrough?) there are also recent results that seem to advance the depth 3 case significantly.[a9]

alas though the connection to VP=?VNP to P=?NP is apparently not very strong, but there has been shown to be a collapse in the complexity hierarchy by Burgisser if they (that is the former (V)NP!) are proven to be equal… (get this… wait for it…) assuming the Generalized Riemann Hypothesis![a13]

apparently a framework/ problem/ conjecture in this area provably equivalent to P vs NP has not yet been made, but its not so implausible to think that a P=?NP or P/poly=?NP type connection could be (eventually) constructed in this area. in fact given its history & directions, it seems almost inevitable.

there are a lot of great surveys.[a1][a2][a3][a4][a5] but alas a lot of this is outside of streamlined/ polished textbook presentations.

the field catches my eye because have long conjectured, and as written up about ~2½ yr ago (near/ shortly after the birth/ launch of this blog & in fact part of its original inspiration/ rationale/ raison d’être) that there is a strong connection between “factoring” monotone boolean circuits, which can be written in expressions closely resembling multivariate polynomials, and P vs NP. and recently factoring multivariate polynomials has been shown to have some deep connections to polynomial identity testing,[a10] which in turn with recently announced results (apr23rd! & maybe some of the key motivation/ inspiration/ tipping point/ trigger for this post!) now seems to be connected to some results in arithmetic circuit complexity, also depth 3 circuits.[a6]

so far there are not much research or strong connections made between boolean/ monotone circuits and arithmetic circuits — there are some papers but it would be a quite a challenging exercise to survey them… any takers? — nevertheless there is some sign of overlap, eg Berkowitz has worked in both areas. (he is the author of one of the standout results in monotone circuit complexity relating to slice functions cited in my earlier P=?NP conjecture/ “outline” blog.) acc wikipedia/ algebraic circuits: “One benchmark in our understanding of the computation of polynomials is the work of Valiant, Skyum, Berkowitz and Rackoff.[4] They showed that if a polynomial f of degree r has a circuit of size s, then f also has a circuit of size polynomial in r and s of depth O(log(r) log(s))”

lower bounds are a notoriously difficult area and these new advances ought to definitely be celebrated by the wider community, and they might even be some milestones/ signposts signalling/ pointing to some longterm/ ultimate eventual success of the circuit program, but alas it seems there are not that many people paying attn to this field. there is one lucky 24v mathoverflow question so thats a modest )( encouraging sign that its not merely a narrow/ abstruse area/ niche inside TCS.[a11]

Continue reading