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
wow its a small world, bumped into Vor's comments as well

11 hours later…
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

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

do you have a paid job on something? curious

see above :D

dude irc is open also. or are you talking about private channel or something

5:00 PM
but we can use otr or whatever

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

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

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
I disagree with one of them

last one?
maybe you should comment. =) you can reply to comments in wordpress there is a 3level deep reply tree/levels

nah its ok

right that would take 5m too much :p

haha
I don't think anyone said the paper directly implies P=NP

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

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

P!=NP implies a large scale statistical property.
it cant be understood by studying a few instances of problems.

yes it can

its a "large scale trend".

5:09 PM
because the chances of cracking these problems are very remote
very

it is easy to find hard problems.

really?
such as?

there are thousands of NP complete problems.

//sigh
instances
ok?

the EDP problem is hard.
it is very hard
the recent computational experiments only reinforce that.

5:11 PM
//sigh
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

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

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

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

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

bzzzzt

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

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

its key to understanding the nature of hard instances wrt random instances

I disagree

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

all SAT problems are "constructed".

it is constructed by conversion from a proof

it is conceivable there is TP like phenomena within the EDP. undiscovered.

insignificant

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

EDP is largely unstudied from an empirical POV so far.

again unrelated

the SAT attack idea is only a few yrs old! it originated in a relatively recent polymath attack.

SAT attack idea?

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?

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

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

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

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

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

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

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

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

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

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$

try not to be so nonchalant/blase once in awhile :p
@RealzSlaw that is a/the idea behind SAT induction

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)

there is a "SAT induction" construction that attacks P=?NP

but who knows

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

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

it is indeed looking at a key "gap" so to speak

but you would still need a proof
an outline

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)

ofc

5:45 PM
run that, eventually you might get the correct algorithm :P

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 ...

ok SAT induction will find it if it exists =) which it likely doesnt

haha

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

thought you were tired of cs.se (with good reason) but maybe just se in general...?

not tired
not enough time

yeah ok

doing a lot of cs-research but only in specific areas

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

re SAT induction need +1 on this plz :\
-4

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

have you seen that se trend graph of pts across se's for user?

"network profile"

5:55 PM
haha nice, thanks

~1K spike SO late 2012 amazing

ah yeah
that was one question
guy gave me two ~400 pt bounties

amazing which one

25

Update 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 "...

first one was regular answer, but he put a bounty for "numbers"
gave me two bounties
haha

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

thx for vote
highly recommend that
rooting for you
need to write up some stuff myself
looking for non-Latex fmt for arXiv with less hassle
more se- or wordpress-like. html mainly with latex sections.

LaTeX is awesome
heh

it can be a hassle to write the entire paper in it imho

stackedit.io
it is essentially cs/math.se

yeah have heard of it

6:01 PM

need a paper fmt for arxiv though.

I prep all my stuff there

it seems to be good

ah, arxiv wants latex
they have some tools that make use of it
why not just use latex?

-2

have 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

saw them yrs ago & was a bit surprised but thought it had potential

use latex :D
I use writelatex

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

<- 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

<- 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

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

posted an example se hot question that was a review. from stats.se

6:05 PM
we knew it wouldn't go anywere

you are quite the leader/promoter there dude

lol
PR is a full time job

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
got a lot of upvotes there

0

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

shows that se can potentially do very well with sci peer review

but there are others trying to do the same thing

got a tumbleweed badge on that question tho. geez, ouch

wats that for

nobody is succeeding yet :|

6:08 PM
they are making websites for reviewing

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

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

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

it is hard for ppl to commit.
just like in dating... :p

ok vzn
I have to do work

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

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

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

hes at IAS! O.o

I'll never catch up now ....

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

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

busy earning pts & nothing else :p

lol

6:26 PM
thats how you get to 39000

showoff :p

the ones no one else will answer
I bet without him the site would be <50% answered

its all good

it might be half dead even

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

?

... 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

recent q on byzantine generals (problem at heart of bitcoin)...
4

I'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

I'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

I am blind, I don't see it
oh

there is more 2 life than se answers/rep pts.... :\

second question

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

ok i g2g

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.