“We study sev­eral prob­lems related to find­ing reset words in deter­min­is­tic finite automata. In par­tic­u­lar, we estab­lish that the prob­lem of decid­ing whether a short­est reset word has length k is com­plete for the com­plex­ity class DP. This result answers a ques­tion posed by Volkov. For the search prob­lems of find­ing a short­est reset word and the length of a short­est reset word, we estab­lish mem­ber­ship in the com­plex­ity classes FP^NP and FP^NP[log], respec­tively. More­over, we show that both these prob­lems are hard for FP^NP[log]. Finally, we observe that com­put­ing a reset word of a given length is FNP-​​complete.”

“Here we pro­pose a generic mech­a­nism — net­worked buffer­ing — for gen­er­at­ing robust traits in com­plex sys­tems that requires two basic con­di­tions to be sat­is­fied: 1) agents are ver­sa­tile enough to per­form more than one sin­gle func­tional role within a sys­tem and 2) agents are degen­er­ate, i.e. there exists par­tial over­lap in the func­tional capa­bil­i­ties of agents. Given these pre­req­ui­sites, degen­er­ate sys­tems can read­ily pro­duce a dis­trib­uted sys­temic response to local per­tur­ba­tions. Rec­i­p­ro­cally, excess resources related to a sin­gle func­tion can indi­rectly sup­port mul­ti­ple unre­lated func­tions within a degen­er­ate system.…”

“This paper presents a com­plex sys­tems overview of a power grid net­work. In recent years, con­cerns about the robust­ness of the power grid have grown because of sev­eral cas­cad­ing out­ages in dif­fer­ent parts of the world. In this paper, cas­cad­ing effect has been sim­u­lated on three dif­fer­ent net­works, the IEEE 300 bus test sys­tem, the IEEE 118 bus test sys­tem, and the WSCC 179 bus equiv­a­lent model, using the DC Power Flow Model. Power Degra­da­tion has been dis­cussed as a mea­sure to esti­mate the dam­age to the net­work, in terms of load loss and node loss. A net­work gen­er­a­tor has been devel­oped to gen­er­ate graphs with char­ac­ter­is­tics sim­i­lar to the IEEE stan­dard net­works and the gen­er­ated graphs are then … have been suggested.”

“We apply mul­ti­ple test­ing pro­ce­dures to the val­i­da­tion of esti­mated default prob­a­bil­i­ties in credit rat­ing sys­tems. The goal is to iden­tify rat­ing classes for which the prob­a­bil­ity of default is esti­mated inac­cu­rately, while still main­tain­ing a pre­de­fined level of com­mit­ting type I errors as mea­sured by the fam­i­ly­wise error rate (FWER) and the false dis­cov­ery rate (FDR). For FWER, we also con­sider pro­ce­dures that take pos­si­ble dis­crete­ness of the data resp. test sta­tis­tics into account. The per­for­mance of these meth­ods is illus­trated in a sim­u­la­tion set­ting and for empir­i­cal default data.”

“The major chal­lenge in design­ing a dis­crim­i­na­tive learn­ing algo­rithm for pre­dict­ing struc­tured data is to address the com­pu­ta­tional issues aris­ing from the expo­nen­tial size of the out­put space. Exist­ing algo­rithms make dif­fer­ent assump­tions to ensure effi­cient, poly­no­mial time esti­ma­tion of model para­me­ters. For sev­eral com­bi­na­to­r­ial struc­tures, includ­ing cycles, par­tially ordered sets, per­mu­ta­tions and other graph classes, these assump­tions do not hold. In this the­sis, we address the prob­lem of design­ing learn­ing algo­rithms for pre­dict­ing com­bi­na­to­r­ial struc­tures by intro­duc­ing two new assump­tions: (i) The first assump­tion is that a par­tic­u­lar count­ing prob­lem can be solved effi­ciently. The con­se­quence is a gen­er­al­i­sa­tion of the clas­si­cal ridge regres­sion for struc­tured pre­dic­tion. (ii) The sec­ond assump­tion is that a par­tic­u­lar sam­pling prob­lem can be solved efficiently. …”

“I’m not an econ­o­mist, but we’ve got five appli­cants for every sin­gle job open­ing. If you tell me that the best response to that sit­u­a­tion is to lay off hun­dreds of thou­sands of teach­ers, I will not accept that this means that you’re smarter and more expert than I am. I will instead con­clude — regard­less of your pres­tige or posi­tion or years of study — that you’re a moral imbe­cile. And know­ing what I know about your inabil­ity to make moral judg­ments I will have no rea­son to trust you to make com­pli­cated macro­eco­nomic ones.”

“The Lin-​​Kernighan heuris­tic is known to be one of the most suc­cess­ful heuris­tics for the Trav­el­ing Sales­man Prob­lem (TSP). It has also proven its effi­ciency in appli­ca­tion to some other prob­lems. In this paper we dis­cuss pos­si­ble adap­ta­tions of TSP heuris­tics for the Gen­er­al­ized Trav­el­ing Sales­man Prob­lem (GTSP) and focus on the case of the Lin-​​Kernighan algo­rithm. At first, we pro­vide an easy-​​to-​​understand descrip­tion of the orig­i­nal Lin-​​Kernighan heuris­tic. Then we pro­pose sev­eral adap­ta­tions, both triv­ial and com­pli­cated. Finally, we con­duct a fair com­pe­ti­tion between all the vari­a­tions of the Lin-​​Kernighan adap­ta­tion and some other GTSP heuris­tics. It appears that our adap­ta­tion of the Lin-​​Kernighan algo­rithm for the GTSP repro­duces the suc­cess of the orig­i­nal heuris­tic. Dif­fer­ent vari­a­tions of our adap­ta­tion out­per­form all other heuris­tics in a wide range of trade-​​offs between solu­tion qual­ity and run­ning time, mak­ing Lin-​​Kernighan the state-​​of-​​the-​​art GTSP local search.”

“Each time-​​series has its own lin­ear trend, the direc­tion­al­ity of a time­series, and remov­ing the lin­ear trend is cru­cial to get the more intu­itive match­ing results. Sup­port­ing the lin­ear detrend­ing in sub­se­quence match­ing is a chal­leng­ing prob­lem due to a huge num­ber of pos­si­ble sub­se­quences. In this paper we define this prob­lem the lin­ear detrend­ing sub­se­quence match­ing and pro­pose its effi­cient index-​​based solu­tion. To this end, we first present a notion of LD-​​windows (LD means lin­ear detrend­ing), which is obtained as fol­lows: we elim­i­nate the lin­ear trend from a sub­se­quence rather than each win­dow itself and obtain LD-​​windows by divid­ing the sub­se­quence into win­dows. Using the LD-​​windows we then present a lower bound­ing the­o­rem for the index-​​based match­ing solu­tion and for­mally prove its correctness.…”

“In the social sci­ences, it is use­ful to under­stand the rel­a­tive sim­i­lar­i­ties of con­cepts that are embed­ded in a par­tic­u­lar text (from a par­tic­u­lar group or a par­tic­u­lar per­son). For exam­ple, in try­ing to esti­mate con­ser­v­a­tive bias in FoxNews, one might esti­mate its ten­dency to asso­ciate con­ser­v­a­tive con­cepts (con­ser­v­a­tive, repub­li­can) and good con­cepts (good, pos­i­tive, etc.), com­pared to con­ser­v­a­tive and bad con­cepts. The out­put would indi­cate con­ser­v­a­tive favoritism. This com­par­i­son could be fur­ther refined by tak­ing into account impor­tant “base­line” infor­ma­tion about the valences asso­ci­ated with lib­eral, namely lib­eral and good in com­par­i­son to lib­eral and bad.…”

Some­times physics is just pretty.

“The Open Enter­prise is a new orga­ni­za­tional design. Unlike orga­ni­za­tions using tra­di­tional man­age­ment struc­tures, Open Enter­prises replace the com­mand and con­trol hier­ar­chy with a mer­i­toc­racy based on col­lab­o­ra­tion and open participation.

Orga­ni­za­tions that adopt this new orga­ni­za­tional struc­ture can make deci­sions faster and respond quicker to their mar­kets. They look more like liv­ing dynamic net­works, and less like pyra­mids. Peo­ple work­ing in these orga­ni­za­tions will have (and feel) more own­er­ship. They’re more engaged in their work, and have the free­dom to work on what they want, when they want to. Most impor­tantly this model enables peo­ple to once again bring their full human­ity – val­ues, beliefs and pas­sions – to the work­place, remov­ing dis­con­nect between orga­ni­za­tional and per­sonal values”

Specif­i­cally: “Genome-​​wide asso­ci­a­tion study of hair length in dogs”

“The human immune sys­tem has numer­ous prop­er­ties that make it ripe for exploita­tion in the com­pu­ta­tional domain, such as robust­ness and fault tol­er­ance, and many dif­fer­ent algo­rithms, col­lec­tively termed Arti­fi­cial Immune Sys­tems (AIS), have been inspired by it. Two gen­er­a­tions of AIS are cur­rently in use, with the first gen­er­a­tion rely­ing on sim­pli­fied immune mod­els and the sec­ond gen­er­a­tion util­is­ing inter­dis­ci­pli­nary col­lab­o­ra­tion to develop a deeper under­stand­ing of the immune sys­tem and hence pro­duce more com­plex mod­els. Both gen­er­a­tions of algo­rithms have been suc­cess­fully applied to a vari­ety of prob­lems, includ­ing anom­aly detec­tion, pat­tern recog­ni­tion, opti­mi­sa­tion and robotics.…”

“This paper is con­cerned with design­ing self-​​driven fit­ness func­tions for Embed­ded Evo­lu­tion­ary Robot­ics. The pro­posed approach con­sid­ers the entropy of the sensori-​​motor stream gen­er­ated by the robot con­troller. This entropy is com­puted using unsu­per­vised learn­ing; its max­i­miza­tion, achieved by an on-​​board evo­lu­tion­ary algo­rithm, imple­ments a “curios­ity instinct”, favour­ing con­trollers vis­it­ing many diverse sensori-​​motor states (sms). Fur­ther, the set of sms dis­cov­ered by an indi­vid­ual can be trans­mit­ted to its off­spring, mak­ing a cul­tural evo­lu­tion mode pos­si­ble. Cumu­la­tive entropy (com­puted from ances­tors and cur­rent indi­vid­ual vis­its to the sms) defines another self-​​driven fit­ness; its opti­miza­tion imple­ments a “dis­cov­ery instinct”, as it favours con­trollers vis­it­ing new or rare sensori-​​motor states. Empir­i­cal results on the bench­mark prob­lems pro­posed by Lehman and Stan­ley (2008) com­par­a­tively demon­strate the mer­its of the approach.”

“Music com­po­si­tion used to be a pen and paper activ­ity. These these days music is often com­posed with the aid of com­puter soft­ware, even to the point where the com­puter com­pose parts of the score autonomously. The com­po­si­tion of most styles of music is gov­erned by rules. We show that by approach­ing the automa­tion, analy­sis and ver­i­fi­ca­tion of com­po­si­tion as a knowl­edge rep­re­sen­ta­tion task and for­mal­is­ing these rules in a suit­able log­i­cal lan­guage, pow­er­ful and expres­sive intel­li­gent com­po­si­tion tools can be eas­ily built. …”

“… Using wire­less sen­sor net­work tech­nol­ogy, we obtained high-​​resolution data of CPIs dur­ing a typ­i­cal day at an Amer­i­can high school, per­mit­ting the recon­struc­tion of the social net­work rel­e­vant for infec­tious dis­ease trans­mis­sion. At a 94% cov­er­age, we col­lected 762,868 CPIs at a max­i­mal dis­tance of 3 meters among 788 indi­vid­u­als. The data revealed a high den­sity net­work with typ­i­cal small world prop­er­ties and a rel­a­tively homoge­nous dis­tri­b­u­tion of both inter­ac­tion time and inter­ac­tion part­ners among subjects.…”

“The goal of this work is to pro­vide an empir­i­cal basis for research on image seg­men­ta­tion and bound­ary detec­tion. To this end, we have col­lected 12,000 hand-​​labeled seg­men­ta­tions of 1,000 Corel dataset images from 30 human sub­jects. Half of the seg­men­ta­tions were obtained from pre­sent­ing the sub­ject with a color image; the other half from pre­sent­ing a grayscale image. The pub­lic bench­mark based on this data con­sists of all of the grayscale and color seg­men­ta­tions for 300 images. The images are divided into a train­ing set of 200 images, and a test set of 100 images.”

“We present a novel algo­rithm for seg­men­ta­tion of nat­ural images that har­nesses the prin­ci­ple of min­i­mum descrip­tion length (MDL). Our method is based on obser­va­tions that a homo­ge­neously tex­tured region of a nat­ural image can be well mod­eled by a Gauss­ian dis­tri­b­u­tion and the region bound­ary can be effec­tively coded by an adap­tive chain code. The opti­mal seg­men­ta­tion of an image is the one that gives the short­est cod­ing length for encod­ing all tex­tures and bound­aries in the image, and is obtained via an agglom­er­a­tive clus­ter­ing process applied to a hier­ar­chy of decreas­ing win­dow sizes as multi-​​scale tex­ture fea­tures. The opti­mal seg­men­ta­tion also pro­vides an accu­rate esti­mate of the over­all cod­ing length and hence the true entropy of the image. We test our algo­rithm on the pub­licly avail­able Berke­ley Seg­men­ta­tion Dataset. It achieves state-​​of-​​the-​​art seg­men­ta­tion results com­pared to other exist­ing methods.”

I won­der to what extent this sort of thing might be use­ful in heuris­tics for Pareto-​​ranking