« first day (732 days earlier)      last day (2048 days later) » 

4:51 AM
I accidently added a tag wiki suggestion for untagged, where I meant to edit an answer and add a tag. Please ignore that edit.
 
5:21 AM
@vzn I start reading the rjlipton blog, and ofc I bump into your comments :D
wow its a small world, bumped into Vor's comments as well
 
 
11 hours later…
vzn
4:30 PM
@Realz hi... rjlipton blog one of those "gems" youve referred to ... cite him in comment & answers...
hey have two bitcoin blogs from last few wks chk em out
missing your wild ideas/engagement around here :|
wrote up a new idea "SAT induction" related to some of your CS exercises wrt low-level algorithmic experiments
 
4:56 PM
@vzn hehe hi
I am unfortunately busy heh
but if you have something interesting on "sat induction" idea, sounds like something interesting
 
vzn
hi realz. still working on bitcoin mysterious one? is there any pt you will be able to divulge anything? its gone thru quite the commotion last few wks yeeks
 
@vzn yes, and yes, I can divulge everything just not here
 
vzn
do you have a paid job on something? curious
 
see above :D
 
vzn
dude irc is open also. or are you talking about private channel or something
 
5:00 PM
irc isn't google searchable
but we can use otr or whatever
 
vzn
not really following why google searchable vs open is an issue but its ok
 
I don't want this stuff to be online for posterity for anyone to see
 
vzn
yeah re SAT induction, need to cook up a toy case to promote it further. was musing on factoring actually...
 
factoring is a good toy case :D
unless you want to try to do some proofs like that rj post
haha
 
vzn
its just at a "glimmer in the eye" stage right now :|
which rjl post are you refing to, there are only hundreds to choose from :p
glad to hear you enjoy his blog
it is basically my favorite in TCS... & others
quite a phenomenon
a rare sr researcher who has an amazing amt of time to blog....
 
5:04 PM
it was a recent post and you commented on it
I disagree with your comment :D
oh you made several comments
I disagree with one of them
 
vzn
last one?
maybe you should comment. =) you can reply to comments in wordpress there is a 3level deep reply tree/levels
 
nah its ok
I can reply here though
 
vzn
right that would take 5m too much :p
 
haha
I don't think anyone said the paper directly implies P=NP
 
vzn
didnt have much space to flesh out my comment.
RJL is a bit "goofy" at times.
he does not rule out P=NP.
 
5:08 PM
but the idea that $P\ne NP$ implies that there are hard problems
 
vzn
he says basically "keep an open mind" lol
 
it is pretty hard to find such hard problems in practice
and here is a problem that should be hard, but was solved anyway
 
vzn
P!=NP implies a large scale statistical property.
it cant be understood by studying a few instances of problems.
 
your point doesn't matter here
yes it can
 
vzn
its a "large scale trend".
 
5:09 PM
because the chances of cracking these problems are very remote
very
 
vzn
it is easy to find hard problems.
 
really?
such as?
 
vzn
there are thousands of NP complete problems.
 
//sigh
instances
ok?
 
vzn
the EDP problem is hard.
it is very hard
the recent computational experiments only reinforce that.
 
5:11 PM
//sigh
bolding doesn't help your point
there are many many NP-complete problems that are very difficult to find random difficult instances for
which is why factoring is useful
and a few other problems
and every time someone finds a difficult class of instances, the next generation of solvers attack it
also graph isomorphism has this problem
 
vzn
notice how small the constants are in the EDP that are explored. C=2 solved, C=3 fails
 
no one actually knows of a hard class of instances, and each time someone does, the next generation of solvers renders it obsolete
 
vzn
C=3 could possibly never be resolved with a computer as far as anyone knows right now.
GI is very interesting in its own right as an NPI problem (which others have remarked actually that NPI problems seem uncommon)... fortnow was remarking that recently in his blog.
 
you are missing the point
rj isn't saying that all forms are not hard
 
vzn
random instances of SAT that are hard are easy to construct if ppl understand the transition pt phenomena
 
5:14 PM
he is saying that in many forms of the problem it is difficult to find hard problems
no
 
vzn
which alas few TCS researchers do seem to be aware/understand that
are you familiar with the transition pt?
 
those aren't really hard, random SAT can be solved in polynomial time
yes
 
vzn
bzzzzt
 
vzn
unf "random" is just too vague a word & it can be misleading ... needs to be carefully defined
 
5:16 PM
w.e the case, practical problems such as finding a proof are supposed to be the hardest problems
 
vzn
interesting, but see zilch ref in that paper abstract to transition pt
NP complete problems cannot be understood at all without understanding of the transition pt.
it is possible there is not a single RJL blog on this subj. dont think have ever seen him talk about it.
there is not even a good wikipedia page on transition pt in computational problems. thats a big hole there.
 
the phase transition is elementary
everyone knows of it
 
vzn
its key to understanding the nature of hard instances wrt random instances
 
I disagree
 
vzn
the transition pt explains why a naive random algorithm for picking random instances will generally only generate "easy" ones
because unless the instances are "contrived" to be close to the transition pt, on avg one would expect they would not be. because the TP is a "narrow" region among all random instances.
 
5:20 PM
like I said you missed the point entirely
this wasn't a random SAT problem
this was constructed
these types of problems are supposed to be the hardest
 
vzn
all SAT problems are "constructed".
 
it is constructed by conversion from a proof
 
vzn
it is conceivable there is TP like phenomena within the EDP. undiscovered.
 
insignificant
 
vzn
in other words there is prob some way to formulate EDP so that this transition pt property becomes more apparent.
 
5:21 PM
it is unrelated to the blog post
 
vzn
EDP is largely unstudied from an empirical POV so far.
 
again unrelated
 
vzn
the SAT attack idea is only a few yrs old! it originated in a relatively recent polymath attack.
 
SAT attack idea?
 
vzn
EDP is very old, something like over 3/4 century, but using SAT solvers against it was only just invented/discovered.
 
5:23 PM
what relevance does EDP have to rjlipton?
 
vzn
its tempting to think this attack on EDP says something about P=NP (as with RJL), but its more naturally taken as evidence that P!=NP.
 
meh
it means nothing
an attack on P=NP can happen in any of the NP-complete problems
 
vzn
RJL has studied EDP a bit theoretically, but not empirically at all.
 
humans not being able to wrap their heads around one problem just means that humans are dumb
 
vzn
many problems are much harder than humans
agreed that many humans are dumb :p
 
5:28 PM
yes, but a different form of the same problem suddenly seems doable
that is his point
and SAT is the most useful, practical form
and for all intents and purposes, every practical problem thrown at SAT is ... easy
almost every practical problem
the reason why there is an SAT competition and not an EDP competition?
because EE uses SAT to verify their stuff, among other practical, useful industries
and guess what, these are seemingly hard combinatorial problems
and the SAT solvers keep surprising
 
vzn
SAT is awesome. many problems should be translated to it that arent currently. that is part of the SAT induction idea.
 
the problem with translation is what rj calls "power index"
it blows up upon conversion
 
vzn
yes, cite EE refs on my own blog in a P!=NP attack proposal.
 
also, it seems, conversion isn't always helpful - this is one way to generate hard instances
reconstructing the original problem in the converted state can be hard
 
vzn
EDP needs to be studied wrt SAT, agreed that was a brilliant step that hopefully will spawn new research, ideally even a whole research program
 
5:31 PM
take too much time
@vzn what I am saying is that it might not help
EDP -> SAT might generate hard instances, even from easy EDP
 
vzn
current experiments/paper basically shows that EDP->SAT instances are hard. just because something was solved does not mean it is not hard
 
heh
increase the size, if it is still solved, it is easy :P
 
vzn
that wikipedia-size SAT proof output is (circumstantial) evidence P!=NP. RJL is mixed up
 
what?
I disagree, I don't think it is evidence of anything, but it is encouraging
I dunno why you think rjl is mixed up
 
vzn
my position, highly excited/encouraging of further SAT work in this area & with other number theory/math problems.
but its relation to P=?NP is spurious at this pt
 
5:39 PM
shrug
 
vzn
we can agree on some of this, maybe lots of this =D
 
@vzn look, if you can use SAT for such large proofs, perhaps SAT itself can assist in proving $P\stackrel{?}{=}NP$
 
vzn
try not to be so nonchalant/blase once in awhile :p
@RealzSlaw that is a/the idea behind SAT induction
 
you mean your idea?
 
vzn
yep.
 
5:41 PM
don't have high hopes lol, solving large proofs is usually not something SAT solvers do well (which is why this was surprising)
 
vzn
there is a "SAT induction" construction that attacks P=?NP
 
but who knows
 
vzn
will have to start with less ambitious attacks 1st though to gain any traction/momentum
 
you can try using an interactive prover
that uses SAT for the gaps
 
vzn
its a new prover idea basically
somewhat interactive
 
5:43 PM
the automated theorem provers do use SAT and other solvers as backend for the gaps
 
vzn
it is indeed looking at a key "gap" so to speak
 
but you would still need a proof
an outline
 
vzn
actually was thinking 1st of attacking collatz with it, its possibly within reach
SAT induction creates the outline/proof =D
 
btw are you aware of the polynomial-time algorithm for NP-complete problems?
(assuming P=NP)
 
vzn
ofc
 
5:45 PM
run that, eventually you might get the correct algorithm :P
 
vzn
it doesnt exist wink :p
 
it does
Diagram of complexity classes provided that P [[≠ NP. The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by Ladner's theorem.]] The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. It was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" and is considered by many to be the most important open problem in the field. It ...
 
vzn
ok SAT induction will find it if it exists =) which it likely doesnt
 
haha
 
vzn
yeah anyway have to cook up a toy example of it...
so you are working for BTC right now but not a conventional job?
see your se activity flattened out
 
5:50 PM
not here :P
 
vzn
thought you were tired of cs.se (with good reason) but maybe just se in general...?
 
not tired
not enough time
 
vzn
yeah ok
 
doing a lot of cs-research but only in specific areas
 
vzn
it is defn a huge time sink
 
5:51 PM
haha it is
but you know what
cs and math SEs are worthy time sinks
better than ... english.SE or reddit
lol
I have some really nice stuff on cs.SE
surprised myself with some nice answers :D
 
vzn
re SAT induction need +1 on this plz :\
-4
Q: similarity of SAT instances, detecting/analyzing/mapping

vzn consider two SAT formulas $f_1, f_2$ generated via some systematic process & with some "inherent similarity". suppose one wishes to determine how their solutions are "interrelated" such that eg solutions or SAT solver work (eg DPLL branching) on $f_1$ can be "leveraged" (in best case, reused) ...

 
haha you keep trying
 
vzn
have you seen that se trend graph of pts across se's for user?
 
vzn
"network profile"
your "spikes" are pretty amazing.
 
5:55 PM
haha nice, thanks
 
vzn
~1K spike SO late 2012 amazing
 
ah yeah
that was one question
guy gave me two ~400 pt bounties
 
vzn
amazing which one
 
25
A: Quantifiable metrics (benchmarks) on the usage of header-only c++ libraries

Realz SlawUpdate This was Real Slaw's original answer. His answer above (the accepted one) is his second attempt. I feel that his second attempt answers the question entirely. - Homer6 Well, for comparison, you can look up the idea of "unity build" (nothing to do with the graphics engine). Basically, a "...

I gave two answers
first one was regular answer, but he put a bounty for "numbers"
so I made the experiment
gave me two bounties
haha
 
vzn
awesome
se is really cool sometimes
+1 =D
 
5:58 PM
haha thanks
yeah, when I next have a break, I think imma arxiv some of my cs answers
I have several huge NP-hardness reductions
and some other answers I am proud of
 
vzn
thx for vote
highly recommend that
rooting for you
need to write up some stuff myself
was asking around about that recently
looking for non-Latex fmt for arXiv with less hassle
more se- or wordpress-like. html mainly with latex sections.
 
LaTeX is awesome
heh
 
vzn
it can be a hassle to write the entire paper in it imho
 
stackedit.io
it is essentially cs/math.se
but for your private use
integrates with google docs
 
vzn
yeah have heard of it
 
6:01 PM
in google docs you can add it as an application
 
vzn
need a paper fmt for arxiv though.
 
I prep all my stuff there
 
vzn
it seems to be good
 
ah, arxiv wants latex
they have some tools that make use of it
why not just use latex?
 
vzn
-2
Q: html/mathJax on arXiv?

vznhave seen some HTML papers on arXiv in the past. is there a standard for HTML+mathjax or HTML+LaTeX papers on arxiv? examples? basically am looking for a less complex version of a paper format that does not require full compiling with a latex compiler etc., somewhat like wordpress pages th...

there are a few HTML papers on arxiv. not common.
 
6:02 PM
mm
 
vzn
saw them yrs ago & was a bit surprised but thought it had potential
 
use latex :D
I use writelatex
 
vzn
unf maybe more used by cranks right now =(
yeah writelatex sounds good
 
and you can use tikz too
make nice diagrams
my NP-reductions look awesome 'cause of tikz
 
vzn
<- volunteer as peer reviewer wink =D
marzio debasi has threatened to write up some stuff too on his blog
 
6:03 PM
they don't need peer review on arxiv
heh I saw Vor commenting on rjlipton's blog too
 
vzn
<- volunteering to peer review your paper pre-posting if you need it
 
haha ok
thanks
I think there are some novel answers on cs.SE
 
vzn
did you give up on stemreview? we got a few more signups & have edited it slightly more.
 
not just mine
I gave up before it started lol
 
vzn
posted an example se hot question that was a review. from stats.se
 
6:05 PM
we knew it wouldn't go anywere
 
vzn
you are quite the leader/promoter there dude
 
lol
PR is a full time job
 
vzn
not forgetting our 1+hr long chat on promotion dude
yeah its endless
another time sink
it went further than either of us expected.
~20+ signups
 
heh
I linked it from reddit
got a lot of upvotes there
 
vzn
0
Q: "facebook coming to end" question on stats.se

vzn is facebook coming to an end? stats.se fyi this is a recent example/model of (imho) a very worthwhile/successful use/exercise of the stackexchange model to review a scientific/electronic preprint. this paper was covered by the MSM (business media) because it predicted a dramatic decline in f...

 
6:07 PM
@vzn I also have partial tools to create a review website
 
vzn
shows that se can potentially do very well with sci peer review
 
but there are others trying to do the same thing
 
vzn
got a tumbleweed badge on that question tho. geez, ouch
 
wats that for
 
vzn
nobody is succeeding yet :|
its a silly badge for basically "nobody noticed your question whatsoever"
 
6:08 PM
they are making websites for reviewing
@vzn I made a google pdf viewer clone
 
vzn
dude the idea for tools is great, respect that, but its not the crucial issue really.
 
for this imaginary website
its on github
so now anyone can host a pdf viewer
it even extracts text
 
vzn
the big hurdle (like other area51 sites) is just getting users/commitment. did you hear about AI group recently failing in beta? a shame.
 
and the text is selectable
 
vzn
gilles was involved with that a bit
 
6:10 PM
yeah I heard
see thats the problem
if it is a "commitment" it is hard to get people
if it is a "resource", then people come naturally
 
vzn
it is hard for ppl to commit.
just like in dating... :p
 
ok vzn
I have to do work
 
vzn
yeah.
dont be a stranger wink nice chatting
 
haha, I'll come back next time I am reading a blog and notice your nick
or you can get on freenode
 
vzn
freenode is that irc?
have had long time to think re: starting groups, getting volunteers etc. its somewhat related to at least 3 sociogical/psychological phenomena.
also related to cs.se partipation which the mods complain about. (eg also beta graduation etc)
yuval was just lamenting on that in meta
 
6:16 PM
yuval is like a king lol
he should be paid fulltime
 
vzn
hes brilliant =D but resists chatting =(
For me the central question is whether the site is ever going to graduate. — Yuval Filmus 12 hours ago
few recognize/realize how amazing his bkg
 
vzn
hes at IAS! O.o
 
I'll never catch up now ....
 
vzn
The Institute for Advanced Study, located in Princeton, New Jersey, United States, is an independent postdoctoral center for theoretical research and intellectual inquiry. Schools There are no degree programs or experimental facilities at the Institute, and research is funded by endowments, grants and gifts — it does not support itself with tuition or fees. Research is never contracted or directed; it is left to each individual researcher to pursue his or her own goals. The Institute is not part of any educational institution. However, because Princeton University's science departme...
 
6:21 PM
yeah
 
vzn
tried to get him to expand one of his recent answers/proof sketches into a writeup, think it has potential, he skipped it =(
no comment...
 
he's busy
 
vzn
busy earning pts & nothing else :p
 
lol
 
vzn
answering undergraduates :p
 
6:26 PM
thats how you get to 39000
 
vzn
showoff :p
 
the ones no one else will answer
keeping the site 88% answered
I bet without him the site would be <50% answered
 
vzn
its all good
 
it might be half dead even
 
vzn
wish he was a teeny bit )( more sociable
but of course its CS geeks we're talking about here :p
 
6:27 PM
stop being human pls
 
vzn
?
 
vzn
... gotta dig up that Q/A was hoping hed writeup it really is cool
he deserves some kind of recognition, it really is cool, have cited him repeatedly in chat which of course is a big deal :\
1man phenomenon
 
lol
 
vzn
recent q on byzantine generals (problem at heart of bitcoin)...
4
Q: Lamport's Byzantine Generals Algorithm

mattrixI've stumbled at the first OralMessage algorithm in Lamport, et al's paper. I've searched the web and there are dozens of sites, restating in exactly the same terms and examples, which isn't helping me. Lamport claims the algorithm can handle (n-1)/3 traitors, and works when the commander is a ...

(going thru my recent faves)
ah here is the YF Q/A am planning to write some related stuff up on blog at some pt
5
Q: Possible to construct a probabilistic halting problem solver?

IgglybooI'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some primality testers are probabilistic(they give you yes or no but have a chance to be wrong). Would it be...

 
6:33 PM
I don't see yuval
 
vzn
his answer.
admit, was hassling/provoking him in comments somewhat...
 
I am blind, I don't see it
oh
 
vzn
there is more 2 life than se answers/rep pts.... :\
 
second question
 
vzn
maybe should write up an answer myself. up to 5 votes hmmm
am not getting much votes on my A's lately not makin me wanna work much =(
 
6:36 PM
lol
you have been gamified
congrats :D
now you need "rep" for everything
 
vzn
luv votes :p
 
ok i g2g
 
vzn
np have fun
re gamification, but what if its too hard/big hassle to earn points...
tricky stuff
true a double edged sword.
re area51, participation/engagement old/new groups (incl cs.se), graduating beta etc, these are the basic sociological/psychological challenges/hurdles/barriers etc:
(& also re sci peer review)
Somebody Else's Problem (also known as Someone Else's Problem or SEP) is a psychological effect where individuals/populations of individuals choose to dissociate themselves from an issue that may be in critical need of recognition. Such issues may be of large concern to the population as a whole but can easily be a choice of ignorance by an individual. Author Douglas Adams' description of the condition, which he ascribes to a physical "SEP field," has helped make it a generally recognized phenomenon. Somebody Else's Problem used to capture public attention on matters that may have been over...
A free rider, in economics, refers to someone who benefits from resources, goods, or services without paying for the cost of the benefit. The term "free rider" was first used in economic theory of public goods, but similar concepts have been applied in to other contexts, including collective bargaining, antitrust law, psychology and political science. Free riding may be considered as a free rider problem when it leads to under-provision of goods or services, or when it leads to overuse or degradation of a common property resource. Although the term originated in economic theory, simila...
The tragedy of the commons is an economics theory by Garrett Hardin, according to which individuals, acting independently and rationally according to each one's self-interest, behave contrary to the whole group's long-term best interests by depleting some common resource. The concept is often cited in connection with sustainable development, meshing economic growth and environmental protection, as well as in the debate over global warming. "Commons" can include the atmosphere, oceans, rivers, fish stocks, national parks and any other shared resource. The tragedy of the commons has particu...
 
6:55 PM
@RealzSlaw Not necessarily; he's quick about it, too.
 

« first day (732 days earlier)      last day (2048 days later) »