These are my recent Pin​board​.in links:

• Pub­lish­ing Has Per­ished: Long Live the Per­sonal Cloud | Cloud­line | Wired​.com

  “Even that arrange­ment wouldn’t be ideal, though. When a pub­lisher aban­dons an arti­cle of mine, it also aban­dons links to it from any page that referred to the arti­cle. In the sci­en­tific and aca­d­e­mic realms, dig­i­tal object iden­ti­fiers (DOIs) are used to mint name­spaces that can tran­scend the life­times (or atten­tion spans) of indi­vid­ual pub­lish­ers. That tech­nol­ogy hasn’t yet trick­led down to the rest of us, but I’d love to have my per­sonal cloud imple­ment such a scheme and be the resolver of last resort for my pub­lished work.”
  
  via:vielmetti pub­lish­ing archives extended-​​mind mem­ory make-​​it-​​so

• [1206.1355] A Cov­er­age The­ory of Bista­tic Radar Net­works: Worst-​​Case Intru­sion Path and Opti­mal Deployment

  “In this paper, we study opti­mal radar deploy­ment for intru­sion detec­tion, with focus on net­work cov­er­age. In con­trast to the disk-​​based sens­ing model in a tra­di­tional sen­sor net­work, the detec­tion range of a bista­tic radar depends on the loca­tions of both the radar trans­mit­ter and radar receiver, and is char­ac­ter­ized by Cassini ovals. Fur­ther­more, in a net­work with mul­ti­ple radar trans­mit­ters and receivers, since any pair of trans­mit­ter and receiver can poten­tially form a bista­tic radar, the detec­tion ranges of dif­fer­ent bista­tic radars are cou­pled and the cor­re­spond­ing net­work cov­er­age is inti­mately related to the loca­tions of all trans­mit­ters and receivers, mak­ing the opti­mal deploy­ment design highly non-​​trivial. Clearly, the detectabil­ity of an intruder depends on the high­est SNR received by all pos­si­ble bista­tic radars. We focus on the worst-​​case intru­sion detectabil­ity, i.e., the min­i­mum pos­si­ble detectabil­ity along all pos­si­ble intru­sion paths. Although it is plau­si­ble to deploy radars on a short­est line seg­ment across the field, it is not always opti­mal in gen­eral, which we illus­trate via counter-​​examples. We then present a suf­fi­cient con­di­tion on the field geom­e­try for the opti­mal­ity of short­est line deploy­ment to hold. Fur­ther, we quan­tify the local struc­ture of detectabil­ity cor­re­spond­ing to a given deploy­ment order and spac­ings of radar trans­mit­ters and receivers, build­ing on which we char­ac­ter­ize the opti­mal deploy­ment to max­i­mize the worst-​​case intru­sion detectabil­ity. Our results show that the opti­mal deploy­ment loca­tions exhibit a bal­anced struc­ture. We also develop a polynomial-​​time approx­i­ma­tion algo­rithm for char­ac­ter­iz­ing the worse-​​case intru­sion path for any given loca­tions of radars under ran­dom deployment.”
  
  opti­miza­tion sim­u­la­tion nudge-​​targets coevo­lu­tion minimax-​​problems

• [1206.0323] Fair­ness and Sta­bil­ity Analy­sis of Con­ges­tion Con­trol Schemes in Vehic­u­lar Ad-​​hoc Networks

  “Coop­er­a­tive vehi­cle safety (CVS) sys­tems oper­ate based on broad­cast of vehi­cle posi­tion and safety infor­ma­tion to neigh­bor­ing cars. The com­mu­ni­ca­tion medium of CVS is a vehic­u­lar ad-​​hoc net­work. One of the main chal­lenges in large scale deploy­ment of CVS sys­tems is the issue of scal­a­bil­ity. To address the scal­a­bil­ity prob­lem, sev­eral con­ges­tion con­trol meth­ods have been pro­posed and are cur­rently under field study. These algo­rithms adapt trans­mis­sion rate and power based on net­work mea­sures such as chan­nel busy ratio. We exam­ine two such algo­rithms and study their dynamic behav­ior in time and space to eval­u­ate sta­bil­ity (in time) and fair­ness (in space) prop­er­ties of these algo­rithms. We present sta­bil­ity con­di­tions and eval­u­ate sta­bil­ity and fair­ness of the algo­rithms through sim­u­la­tion exper­i­ments. Results show that there is a trade-​​off between fast con­ver­gence, tem­po­ral sta­bil­ity and spa­tial fair­ness. The proper ranges of para­me­ters for achiev­ing sta­bil­ity are pre­sented for the dis­cussed algo­rithms. Sta­bil­ity is ver­i­fied for all typ­i­cal road den­sity cases. Fair­ness is shown to be nat­u­rally achieved for some algo­rithms, while under the same con­di­tions other algo­rithms may suf­fer from unfair­ness issues. A method for resolv­ing unfair­ness is intro­duced and eval­u­ated through simulations.”
  
  robot­ics com­plex­ol­ogy emergent-​​design traffic-​​models collective-​​behavior performance-​​measure nudge-​​targets sim­u­la­tion

• [1205.6147] A curvature-​​driven effec­tive attrac­tion in mul­ti­com­po­nent membranes

  “We study closed liq­uid mem­branes that seg­re­gate into three phases due to dif­fer­ences in the chem­i­cal and phys­i­cal prop­er­ties of its com­po­nents. The shape and in-​​plane mem­brane arrange­ment of the phases are cou­pled through phase-​​specific bend­ing ener­gies and line ten­sions. We use sim­u­lated anneal­ing Monte Carlo sim­u­la­tions to find low-​​energy struc­tures, allow­ing both phase arrange­ment and mem­brane shape to relax. The three-​​phase sys­tem is the sim­plest one in which there are mul­ti­ple inter­face pairs, allow­ing us to ana­lyze inter­fa­cial pref­er­ences and pair­wise dis­tinct line ten­sions. We observe the system’s pref­er­ence for inter­face pairs that max­i­mize dif­fer­ences in spon­ta­neous cur­va­ture. From a pat­tern selec­tion per­spec­tive, this acts as an effec­tive attrac­tion between phases of most dis­parate spon­ta­neous cur­va­ture. We show that this effec­tive attrac­tion is robust enough to per­sist even when the inter­face between these phases is the most penal­ized by line ten­sion. This effect is dri­ven by geom­e­try and not by any explicit component-​​component interaction.”
  
  sim­u­la­tion membrane-​​physics clas­si­fi­ca­tion phase-​​diagrams nudge-​​targets

• [1205.2170] Col­lab­o­ra­tive Search on the Plane with­out Communication

  “We use dis­trib­uted com­put­ing tools to pro­vide a new per­spec­tive on the behav­ior of coop­er­a­tive bio­log­i­cal ensem­bles. We intro­duce the Ants Nearby Trea­sure Search (ANTS) prob­lem, a gen­er­al­iza­tion of the clas­si­cal cow-​​path prob­lem, which is rel­e­vant for col­lec­tive for­ag­ing in ani­mal groups. In the ANTS prob­lem, k iden­ti­cal (prob­a­bilis­tic) agents, ini­tially placed at some cen­tral loca­tion, col­lec­tively search for a trea­sure in the two-​​dimensional plane. The trea­sure is placed at a tar­get loca­tion by an adver­sary and the goal is to find it as fast as pos­si­ble as a func­tion of both k and D, where D is the dis­tance between the cen­tral loca­tion and the target.…”
  
  low-​​hanging-​​fruit nudge-​​targets agent-​​based autonomous-​​agents

• [1206.1571] Steady-​​state fluc­tu­a­tions of a genetic feed­back loop: an exact solution

  “…For the case where the degra­da­tion rate of bound and free pro­tein is the same, our solu­tion is at vari­ance with a pre­vi­ous claim of an exact solu­tion (Hornos et al, Phys. Rev. E {bf 72}, 051907 (2005) and sub­se­quent stud­ies). We show explic­itly that this is due to an unphys­i­cal for­mu­la­tion of the under­ly­ing mas­ter equa­tion in those studies.”
  
  unphys­i­cal bio­chem­istry mod­els analytical-​​models-​​of-​​messy-​​old-​​life

• [1202.0937] Com­pres­sive binary search

  Some­thing inter­est­ing but very dif­fi­cult in here about rep­re­sen­ta­tion the­ory for meta­heuris­tics, and prac­ti­cal (con­tex­tual) land­scape recon­fig­u­ra­tion. “In this paper we con­sider the prob­lem of locat­ing a nonzero entry in a high-​​dimensional vec­tor from pos­si­bly adap­tive lin­ear mea­sure­ments. We con­sider a recur­sive bisec­tion method which we dub the com­pres­sive binary search and show that it improves on what any non­adap­tive method can achieve. We also estab­lish a non-​​asymptotic lower bound that applies to all meth­ods, regard­less of their com­pu­ta­tional com­plex­ity. Com­bined, these results show that the com­pres­sive binary search is within a dou­ble log­a­rith­mic fac­tor of the opti­mal performance.”
  
  needle-​​in-​​a-​​haystack algo­rithms computational-​​complexity

• [1107.0500] Fac­tor­iza­tion of Matri­ces of Quaternions

  “We review known fac­tor­iza­tion results in quater­nion matri­ces. Specif­i­cally, we derive the Jor­dan canon­i­cal form, polar decom­po­si­tion, sin­gu­lar value decom­po­si­tion, the QR fac­tor­iza­tion. We prove there is a Schur fac­tor­iza­tion for com­mut­ing matri­ces, and from this derive the spec­tral the­o­rem. We do not con­sider algo­rithms, but do point to some of the numer­i­cal lit­er­a­ture. Rather than work directly with matri­ces of quater­nions, we work with com­plex matri­ces with a spe­cific sym­me­try based on the dual oper­a­tion. We dis­cuss related results regard­ing com­plex matri­ces that are self-​​dual or sym­met­ric, but per­haps not Hermitian.”
  
  quan­tums algo­rithms matri­ces open-​​questions nudge-​​targets amus­ing

• [1204.0163] Coor­di­na­tion and Emer­gence in the Cel­lu­lar Auto­mated Fash­ion Game

  “Fash­ion plays such a cru­cial rule in the evo­lu­tion of cul­ture and soci­ety that it is regarded as a sec­ond nature to the human being. Also, its impact on econ­omy is quite non­triv­ial. On what is fash­ion­able, inter­est­ingly, there are two view­points that are both extremely wide­spread but almost oppo­site: con­formists think that what is pop­u­lar is fash­ion­able, while rebels believe that being dif­fer­ent is the essence. Fash­ion color is fash­ion­able in the first sense, and Lady Gaga in the sec­ond. We inves­ti­gate a model where the pop­u­la­tion con­sists of the afore-​​mentioned two groups of peo­ple that are located on a spa­tial struc­ture. The­o­ret­i­cally, this model is equiv­a­lent to the match­ing pen­nies game on the cor­re­spond­ing net­work, and has its own inter­est to game the­ory: it is a hybrid model of pure com­pe­ti­tion and pure coop­er­a­tion. This is true because when a con­formist meets a rebel, they play the zero sum match­ing pen­nies game, which is pure com­pe­ti­tion. When two con­formists (rebels) meet, they play the (anti-​​) coor­di­na­tion game, which is pure coop­er­a­tion. Sim­u­la­tion shows that in most cases peo­ple can reach an extra­or­di­nar­ily high degree of coop­er­a­tion, through self­ish, myopic, naive, and local inter­ac­tions. Phase tran­si­tion, as well as emer­gence of many inter­est­ing pat­terns, is also observed.”
  
  cellular-​​automata agent-​​based social-​​dynamics com­plex­ol­ogy

• [1205.3111] Sta­bil­ity of Boolean Mul­ti­plex Networks

  “We extend the for­mal­ism of Ran­dom Boolean Net­works with canal­iz­ing rules to mul­ti­level com­plex net­works. The for­mal­ism allows to model genetic net­works in which each gene might take part in more than one sig­nal­ing path­way. We use a semi-​​annealed approach to study the sta­bil­ity of this class of mod­els when cou­pled in a mul­ti­plex net­work and show that the ana­lyt­i­cal results are in good agree­ment with numer­i­cal sim­u­la­tions. Our main find­ing is that the mul­ti­plex struc­ture pro­vides a mech­a­nism for the sta­bi­liza­tion of the sys­tem and of chaotic regimes of indi­vid­ual lay­ers. Our results help under­stand­ing why some genetic net­works that are the­o­ret­i­cally expected to oper­ate in the chaotic regime can actu­ally dis­play dynam­i­cal stability.”
  
  boolean-​​networks com­plex­ol­ogy kauff­ma­nia inter­est­ing

• [1109.1488] Are Opin­ions Based on Sci­ence: Mod­el­ling Social Response to Sci­en­tific Facts

  Oh how I laughed and laughed. “As sci­en­tists we like to think that mod­ern soci­eties and their mem­bers base their views, opin­ions and behav­iour on sci­en­tific facts.…”
  
  sci­ence! cultural-​​assumptions agent-​​based sim­u­la­tion social-​​networks

• [1206.0594] Sim­ple and Deter­min­is­tic Matrix Sketching

  I hadn’t heard of matrix sketch­ing before; war­rants a look someday.
  
  algo­rithms operations-​​research data-​​cleaning summarization-​​algorithms nudge-​​targets

• [1205.0537] A greedy-​​navigator approach to nav­i­ga­ble city plans

  “We use a set of four the­o­ret­i­cal nav­i­ga­bil­ity indices for street maps to inves­ti­gate the shape of the result­ing street net­works, if they are grown by opti­miz­ing these indices. The indices com­pare the per­for­mance of sim­u­lated nav­i­ga­tors (hav­ing a par­tial infor­ma­tion about the sur­round­ings, like humans in many real sit­u­a­tions) to the per­for­mance of opti­mally nav­i­gat­ing indi­vid­u­als. We show that our sim­ple greedy short­cut con­struc­tion strat­egy gen­er­ates the emerg­ing struc­tures that are dif­fer­ent from real road net­work, but not incon­ceiv­able. The result­ing city plans, for all nav­i­ga­tion indices, share com­mon qual­i­ta­tive prop­er­ties such as the ten­dency for tri­an­gu­lar blocks to appear, while the more quan­ti­ta­tive fea­tures, such as degree dis­tri­b­u­tions and clus­ter­ing, are char­ac­ter­is­ti­cally dif­fer­ent depend­ing on the type of met­rics and rout­ing strate­gies. We show that it is the type of met­rics used which deter­mines the over­all shapes char­ac­ter­ized by struc­tural het­ero­gene­ity, but the rout­ing schemes con­tribute to more sub­tle details of local­ity, which is more empha­sized in case of unre­stricted con­nec­tions when the edge cross­ing is allowed.”
  
  city-​​planning emer­gence emergent-​​design agent-​​based nudge-​​targets

• [1105.0703] Adap­tive Cut Gen­er­a­tion Algo­rithm for Improved Lin­ear Pro­gram­ming Decod­ing of Binary Lin­ear Codes

  “…Then, we pro­pose a new and effec­tive algo­rithm to gen­er­ate par­ity inequal­i­ties derived from cer­tain addi­tional redun­dant par­ity check (RPC) con­straints that can elim­i­nate pseudocode­words pro­duced by the LP decoder, often sig­nif­i­cantly improv­ing the decoder error-​​rate per­for­mance. The cut-​​generating algo­rithm is based upon a spe­cific trans­for­ma­tion of an ini­tial parity-​​check matrix of the lin­ear block code. We also design two vari­a­tions of the pro­posed decoder to make it more effi­cient when it is com­bined with the new cut-​​generating algo­rithm. Sim­u­la­tion results for sev­eral low-​​density parity-​​check (LDPC) codes demon­strate that the pro­posed decod­ing algo­rithms sig­nif­i­cantly nar­row the per­for­mance gap between LP decod­ing and ML decoding.”
  
  linear-​​programming information-​​theory algo­rithms nudge-​​targets searching-​​under-​​the-​​streetlight

• [1203.4802] A Reference-​​Free Algo­rithm for Com­pu­ta­tional Nor­mal­iza­tion of Shot­gun Sequenc­ing Data

  “Deep shot­gun sequenc­ing and analy­sis of genomes, tran­scrip­tomes, ampli­fied single-​​cell genomes, and metagenomes has enabled inves­ti­ga­tion of a wide range of organ­isms and ecosys­tems. How­ever, sam­pling vari­a­tion in short-​​read data sets and high sequenc­ing error rates of mod­ern sequencers present many new com­pu­ta­tional chal­lenges in data inter­pre­ta­tion. These chal­lenges have led to the devel­op­ment of new classes of map­ping tools and {em de novo} assem­blers. These algo­rithms are chal­lenged by the con­tin­ued improve­ment in sequenc­ing through­put. We here describe dig­i­tal nor­mal­iza­tion, a single-​​pass com­pu­ta­tional algo­rithm that sys­tem­atizes cov­er­age in shot­gun sequenc­ing data sets, thereby decreas­ing sam­pling vari­a­tion, dis­card­ing redun­dant data, and remov­ing the major­ity of errors. Dig­i­tal nor­mal­iza­tion sub­stan­tially reduces the size of shot­gun data sets and decreases the mem­ory and time require­ments for {em de novo} sequence assem­bly, all with­out sig­nif­i­cantly impact­ing con­tent of the gen­er­ated con­tigs. We apply dig­i­tal nor­mal­iza­tion to the assem­bly of micro­bial genomic data, ampli­fied single-​​cell genomic data, and tran­scrip­tomic data. Our imple­men­ta­tion is freely avail­able for use and modification.”
  
  genomics bioin­for­mat­ics algo­rithms sta­tis­tics data-​​cleaning

• [0908.2741] B-​​Rank: A top N Rec­om­men­da­tion Algorithm

  “In this paper B-​​Rank, an effi­cient rank­ing algo­rithm for rec­om­mender sys­tems, is pro­posed. B-​​Rank is based on a ran­dom walk model on hyper­graphs. Depend­ing on the setup, B-​​Rank out­per­forms other state of the art algo­rithms in terms of pre­ci­sion, recall (19% — 50%), and inter list diver­sity (20% — 60%). B-​​Rank cap­tures well the dif­fer­ence between pop­u­lar and niche objects. The pro­posed algo­rithm pro­duces very promis­ing results for sparse and dense vot­ing matri­ces. Fur­ther­more, a rec­om­men­da­tion list update algo­rithm is introduced,to cope with new votes. This tech­nique sig­nif­i­cantly reduces com­pu­ta­tional com­plex­ity. The imple­men­ta­tion of the algo­rithm is sim­ple, since B-​​Rank needs no para­me­ter tuning.”
  
  algo­rithms peer-​​production bench­mark­ing amus­ing

• [1205.2777] Mod­el­ling slowly chang­ing dynamic gene-​​regulatory networks

  “Dynamic gene-​​regulatory net­works are com­plex since the num­ber of poten­tial com­po­nents involved in the sys­tem is very large. Esti­mat­ing dynamic net­works is an impor­tant task because they com­pro­mise valu­able infor­ma­tion about inter­ac­tions among genes. Graph­i­cal mod­els are a pow­er­ful class of mod­els to esti­mate con­di­tional inde­pen­dence among ran­dom vari­ables, e.g. inter­ac­tions in dynamic sys­tems. Indeed, these inter­ac­tions tend to vary over time. How­ever, the lit­er­a­ture has been focused on sta­tic net­works, which can only reveal over­all struc­tures. Time-​​course exper­i­ments are per­formed in order to tease out sig­nif­i­cant changes in net­works. It is typ­i­cally rea­son­able to assume that changes in genomic net­works are few because sys­tems in biol­ogy tend to be sta­ble. We intro­duce a new model for esti­mat­ing slowly changes in dynamic gene-​​regulatory net­works which is suit­able for a high-​​dimensional dataset, e.g. time-​​course genomic data. Our method is based on i) the penal­ized like­li­hood with $ell_1$-norm, ii) the penal­ized dif­fer­ences between con­di­tional inde­pen­dence ele­ments across time points and iii) the heuris­tic search strat­egy to find opti­mal smooth­ing para­me­ters. We imple­ment a set of lin­ear con­straints nec­es­sary to esti­mate sparse graphs and penal­ized chang­ing in dynamic net­works. These con­straints are not in the lin­ear form. For this rea­son, we intro­duce slack vari­ables to re-​​write our prob­lem into a stan­dard con­vex opti­miza­tion prob­lem sub­ject to equal­ity lin­ear con­straints. We show that GL$_Delta$ per­forms well in a sim­u­la­tion study. Finally, we apply the pro­posed model to a time-​​course genetic dataset T-​​cell.”
  
  gene-​​regulatory-​​networks mod­el­ing systems-​​biology operations-​​research linear-​​programming nudge-​​targets

• [1205.3532] New Algo­rithms on Rooted Triplet Consistency

  “An evo­lu­tion­ary tree (phy­lo­ge­netic tree) is a binary, rooted, unordered tree that mod­els the evo­lu­tion­ary his­tory of cur­rently liv­ing species in which leaves are labeled by species. In this paper, we inves­ti­gate the prob­lem of find­ing the max­i­mum con­sen­sus evo­lu­tion­ary tree from a set of given rooted triplets. A rooted triplet is a phy­lo­ge­netic tree on three leaves and shows the evo­lu­tion­ary rela­tion­ship of the cor­re­spond­ing three species. The men­tioned prob­lem is known to be APX-​​hard. We present two new heuris­tic algo­rithms. For a given set of m triplets on n species, the Fast­Tree algo­rithm runs in O(mn^2) which is faster than any other pre­vi­ously known algo­rithms, although, the out­come is less sat­is­fac­tory. The BPMTR algo­rithm runs in O(mn^3) and in aver­age per­forms bet­ter than any other pre­vi­ously known approx­i­ma­tion algo­rithms for this problem.”
  
  cladis­tics algo­rithms open-​​questions nudge-​​targets

• [1205.3720] A k-​​shell decom­po­si­tion method for weighted networks

  “One major lim­i­ta­tion of most cen­tral­ity mea­sures, includ­ing the k-​​core decom­po­si­tion method, is their design to work on unweighted graphs. How­ever, in prac­tice, real net­works are weighted, and their weights describe impor­tant and well defined prop­er­ties of the under­ly­ing sys­tems. In order to over­come this lim­i­ta­tion two main approaches were fol­lowed, but, both hav­ing draw­backs of their own. Under the first approach one would com­pletely neglect the weights and per­form the analy­sis on the unweighted net­work, but then one chooses to neglect an impor­tant prop­erty of the net­work. The sec­ond approach would be to con­sider only links with weights above some — (usu­ally) arbi­trary cho­sen — thresh­old value. How­ever, this approach has a draw­back since it has to deal with the selec­tion of a proper cut-​​off value, and as we will dis­cuss later, this could have sig­nif­i­cant impact on the results. Addi­tion­ally, by neglect­ing links bel­low a thresh­old, the net­work becomes sparser with some nodes get­ting dis­con­nected and not con­sid­ered by the applied method afterwards.”
  
  network-​​theory social-​​networks algo­rithms graph-​​theory

• [1109.2341] Guar­an­teed suc­cess­ful strate­gies for a square achieve­ment game on an n by n grid

  “At some places (see the ref­er­ences) Mar­tin Erick­son describes a cer­tain game: “Two play­ers alter­nately write O’s (first player) and X’s (sec­ond player) in the unoc­cu­pied cells of an n x n grid. The first player (if any) to occupy four cells at the ver­tices of a square with hor­i­zon­tal and ver­ti­cal sides is the win­ner.” Then he asks “What is the out­come of the game given opti­mal play?” or “What is the small­est n such that the first player has a win­ning strategy?” ”
  
  nudge-​​targets game-​​theory mathematical-​​recreations

• [1206.0217] Effi­cient tech­niques for min­ing spa­tial databases

  “Clus­ter­ing is one of the major tasks in data min­ing. In the last few years, Clus­ter­ing of spa­tial data has received a lot of research atten­tion. Spa­tial data­bases are com­po­nents of many advanced infor­ma­tion sys­tems like geo­graphic infor­ma­tion sys­tems VLSI design sys­tems. In this the­sis, we intro­duce sev­eral effi­cient algo­rithms for clus­ter­ing spa­tial data. First, we present a grid-​​based clus­ter­ing algo­rithm that has sev­eral advan­tages and com­pa­ra­ble per­for­mance to the well known effi­cient clus­ter­ing algo­rithm. The algo­rithm has sev­eral advan­tages. The algo­rithm does not require many input para­me­ters. It requires only three para­me­ters, the num­ber of the points in the data space, the num­ber of the cells in the grid and a per­cent­age. The num­ber of the cells in the grid reflects the accu­racy that should be achieved by the algo­rithm. The algo­rithm is capa­ble of dis­cov­er­ing clus­ters of arbi­trary shapes. The com­pu­ta­tional com­plex­ity of the algo­rithm is com­pa­ra­ble to the com­plex­ity of the most effi­cient clus­ter­ing algo­rithm. The algo­rithm has been imple­mented and tested against dif­fer­ent ranges of data­base sizes. The per­for­mance results show that the run­ning time of the algo­rithm is supe­rior to the most well known algo­rithms (CLARANS [23]). The results show also that the per­for­mance of the algo­rithm do not degrade as the num­ber of the data points increases.”
  
  GIS sta­tis­tics clus­ter­ing context-​​sensitive-​​data nudge-​​targets data-​​mining

• [1205.5407] FASTSUBS: An Effi­cient Admis­si­ble Algo­rithm for Find­ing the Most Likely Lex­i­cal Sub­sti­tutes Using a Sta­tis­ti­cal Lan­guage Model

  “Lex­i­cal sub­sti­tutes have found use in the con­text of word sense dis­am­bigua­tion, unsu­per­vised part-​​of-​​speech induc­tion, para­phras­ing, machine trans­la­tion, and text sim­pli­fi­ca­tion. Using a sta­tis­ti­cal lan­guage model to find the most likely sub­sti­tutes in a given con­text is a suc­cess­ful approach, but the cost of a naive algo­rithm is pro­por­tional to the vocab­u­lary size. This paper presents the Fast­subs algo­rithm which can effi­ciently and cor­rectly iden­tify the most likely lex­i­cal sub­sti­tutes for a given con­text based on a sta­tis­ti­cal lan­guage model with­out going through most of the vocab­u­lary. The effi­ciency of Fast­subs makes large scale exper­i­ments based on lex­i­cal sub­sti­tutes fea­si­ble. For exam­ple, it is pos­si­ble to com­pute the top 10 sub­sti­tutes for each one of the 1,173,766 tokens in Penn Tree­bank in about 6 hours on a typ­i­cal work­sta­tion. The same task would take about 6 days with the naive algo­rithm. An imple­men­ta­tion of the algo­rithm and a dataset with the top 100 sub­sti­tutes of each token in the WSJ sec­tion of the Penn Tree­bank are avail­able from the author’s web­site at this http URL”
  
  lin­guis­tics data-​​cleaning algo­rithms nudge-​​targets clas­si­fi­ca­tion

• [1204.1002] Fast Multi-​​Scale Detec­tion of Rel­e­vant Communities

  “Nowa­days, net­works are almost ubiq­ui­tous. In the past decade, com­mu­nity detec­tion received an increas­ing inter­est as a way to uncover the struc­ture of net­works by group­ing nodes into com­mu­ni­ties more densely con­nected inter­nally than exter­nally. Yet most of the effec­tive meth­ods avail­able do not con­sider the poten­tial lev­els of organ­i­sa­tion, or scales, a net­work may encom­pass and are there­fore lim­ited. In this paper we present a method com­pat­i­ble with global and local cri­te­ria that enables fast multi-​​scale com­mu­nity detec­tion. The method is derived in two algo­rithms, one for each type of cri­te­rion, and imple­mented with 6 known cri­te­ria. Uncov­er­ing com­mu­ni­ties at var­i­ous scales is a com­pu­ta­tion­ally expen­sive task. There­fore this work puts a strong empha­sis on the reduc­tion of com­pu­ta­tional com­plex­ity. Some heuris­tics are intro­duced for speed-​​up pur­poses. Exper­i­ments demon­strate the effi­ciency and accu­racy of our method with respect to each algo­rithm and cri­te­rion by test­ing them against large gen­er­ated multi-​​scale net­works. This study also offers a com­par­i­son between cri­te­ria and between the global and local approaches.”
  
  social-​​networks network-​​theory algo­rithms community-​​detection

• [1105.2204] A Bayesian Model of NMR Spec­tra for the Decon­vo­lu­tion and Quan­tifi­ca­tion of Metabo­lites in Com­plex Bio­log­i­cal Mixtures

  Now this one is cool.
  
  sta­tis­tics inverse-​​problems bio­chem­istry signal-​​processing algo­rithms machine-​​learning nudge-​​targets inference-of-things-that-aren’t-toys

• Growthol­ogy: Civic Startup Accelerator

  “…What exactly are we talk­ing about when we say ‘using data’? Steven John­son wrote an inter­est­ing piece in Wired two years ago using New York City 311 call data. Those city subway/​train/​bus route apps on your smart­phone? Pos­si­ble thanks to city gov­ern­ments open­ing up their data. The recently released Kauff­man Foun­da­tion health care report con­tains plenty of dis­cus­sion and ideas for both the pub­lic and pri­vate sector.”
  
  social-​​entrepreneurship public-​​policy star­tups business-​​development-​​sortof shadow-​​economies open-​​science

• [1205.4422] 3D-​​Algorithms of Com­posed Pur­suit Navigation

  “The prob­lem of pur­su­ing a mov­ing tar­get is always one of the main top­ics in nav­i­ga­tion. In the lit­er­a­tures, there are two well-​​known algo­rithms called Pure Pur­suit and Pure Ren­dezvous nav­i­ga­tion in the 3-​​dimensional space $mathbb{R}^3$. In this paper, these two meth­ods are com­bined to intro­duce a novel fam­ily of pur­su­ing algo­rithms called Com­posed Pur­suit Nav­i­ga­tion. The Kine­matic and geo­met­ric prop­er­ties of this nav­i­ga­tion is stud­ied. The tra­jec­to­ries of this new fam­ily of algo­rithms ben­e­fit the advan­tages of two known meth­ods and its promi­nence is demon­strated in two real exam­ples. More­over, it is shown that the met­ric related to the algo­rithms are given by Mat­sumoto metrics.”
  
  operations-​​research algo­rithms nudge-​​targets

• [1205.5975] A Domain-​​Specific Com­piler for Lin­ear Alge­bra Operations

  “We present a pro­to­typ­i­cal lin­ear alge­bra com­piler that auto­mat­i­cally exploits domain-​​specific knowl­edge to gen­er­ate high-​​performance algo­rithms. The input to the com­piler is a tar­get equa­tion together with knowl­edge of both the struc­ture of the prob­lem and the prop­er­ties of the operands. The out­put is a vari­ety of high-​​performance algo­rithms, and the cor­re­spond­ing source code, to solve the tar­get equa­tion. Our approach con­sists in the decom­po­si­tion of the input equa­tion into a sequence of library-​​supported ker­nels. Since in gen­eral such a decom­po­si­tion is not unique, our com­piler returns not one but a num­ber of algo­rithms. The poten­tial of the com­piler is shown by means of its appli­ca­tion to a chal­leng­ing equa­tion aris­ing within the genome-​​wide asso­ci­a­tion study. As a result, the com­piler pro­duces mul­ti­ple “best” algo­rithms that out­per­form the best exist­ing libraries.”
  
  domain-​​specific-​​language linear-​​algebra software-​​engineering com­piler nudge-​​targets

• [1206.1098] The inter­play of intrin­sic and extrin­sic bounded noises in genetic networks

  “After being con­sid­ered as a nui­sance to be fil­tered out, it became recently clear that bio­chem­i­cal noise plays a com­plex role, often fully func­tional, for a genetic net­work. The influ­ence of intrin­sic and extrin­sic noises on genetic net­works has inten­sively been inves­ti­gated in last ten years, though con­tri­bu­tions on the co-​​presence of both are sparse. Extrin­sic noise is usu­ally mod­eled as an unbounded white or col­ored gauss­ian sto­chas­tic process, even though real­is­tic sto­chas­tic per­tur­ba­tions are clearly bounded. In this paper we con­sider Gillespie-​​like sto­chas­tic mod­els of non­lin­ear net­works, i.e. the intrin­sic noise, where the model jump rates are affected by col­ored bounded extrin­sic noises syn­the­sized by a suit­able bio­chem­i­cal state-​​dependent Langevin sys­tem. These sys­tems are described by a mas­ter equa­tion, and a sim­u­la­tion algo­rithm to ana­lyze them is derived. This new mod­el­ing par­a­digm should enlarge the class of sys­tems amenable at mod­el­ing. We inves­ti­gated the influ­ence of both ampli­tude and auto­cor­re­la­tion time of a extrin­sic Sine-​​Wiener noise on: $(i)$ the Michaelis-​​Menten approx­i­ma­tion of noisy enzy­matic reac­tions, which we show to be applic­a­ble also in co-​​presence of both intrin­sic and extrin­sic noise, $(ii)$ a model of enzy­matic futile cycle and $(iii)$ a genetic tog­gle switch. In $(ii)$ and $(iii)$ we show that the pres­ence of a bounded extrin­sic noise induces qual­i­ta­tive mod­i­fi­ca­tions in the prob­a­bil­ity den­si­ties of the involved chem­i­cals, where new modes emerge, thus sug­gest­ing the pos­si­bile func­tional role of bounded noises.”
  
  bio­chem­istry structural-​​biology reaction-​​networks biological-​​engineering noise its-​​complicated-​​inside-​​a-​​cell sim­u­la­tion nudge-​​targets

• [1205.3058] A Tight Lower Bound on the Con­trol­la­bil­ity of Net­works with Mul­ti­ple Leaders

  “In this paper we study the con­trol­la­bil­ity of net­worked sys­tems with sta­tic net­work topolo­gies using tools from alge­braic graph the­ory. Each agent in the net­work acts in a decen­tral­ized fash­ion by updat­ing its state in accor­dance with a nearest-​​neighbor aver­ag­ing rule, known as the con­sen­sus dynam­ics. In order to con­trol the sys­tem, exter­nal con­trol inputs are injected into the so called leader nodes, and the influ­ence is prop­a­gated through­out the net­work. Our main result is a tight topo­log­i­cal lower bound on the rank of the con­trol­la­bil­ity matrix for such sys­tems with arbi­trary net­work topolo­gies and pos­si­bly mul­ti­ple leaders.”
  
  network-​​theory algo­rithms emergent-​​design nudge-​​targets

• [1205.3180] Community-​​Quality-​​Based Player Rank­ing in Col­lab­o­ra­tive Games with no Explicit Objectives

  “How­ever, when the game has no clear objec­tives, no met– ric exists to mea­sure player con­tri­bu­tion qual­ity. Indeed, each player may have a dif­fer­ent per­sonal moti­va­tion to achieve dif– fer­ent self-​​imposed goals [4], and player actions can be con– sidered fair or dis­rup­tive towards the com­mu­nity depend­ing on whether they respect or dam­age other player con­tri­bu­tions. In these cases, there is a very abstract and sub­jec­tive shared implicit objec­tive that could be described as build­ing a fair and not dis­rup­tive player com­mu­nity. It should be noted that fair play­ers ben­e­fit from their behav­ior, as it is more likely that other play­ers act fair towards them. Fur­ther­more, a com– munity of dis­rup­tive play­ers seems to repel fair play­ers and the com­mu­nity qual­ity has an intu­itive ten­dency to grad­u­ally drop off. Con­trar­ily, a com­mu­nity of fair play­ers lures new fair play­ers, which lead, in turn, to an increase of the commu– nity quality.”
  
  social-​​dynamics game-​​theory col­lab­o­ra­tion performance-​​measure teams ranking-​​schemes agile-​​management to-​​explore

• [1205.3648] 6-​​Body Cen­tral Con­fig­u­ra­tions Formed by Two Isosce­les Triangles

  “In this paper,we show the exis­tence of a class of 6-​​body cen­tral con­fig­u­ra­tions with two isosce­les tri­an­gles; which are con­gru­ent to each other and keep some distance.We also study the nec­es­sary con­di­tions about masses for the bod­ies which can form a cen­tral configuration.”
  
  N-​​body-​​problems sim­u­la­tion mathematical-​​recreations nudge-​​targets special-​​cases inverse-​​problems-​​done-​​backwards

• [1206.1074] Memetic Arti­fi­cial Bee Colony Algo­rithm for Large-​​Scale Global Optimization

  Peo­ple who mis­un­der­stand the dif­fer­ence between a “pro­gram”, a “design pat­tern” and an “algo­rithm”, I’m think­ing. That said, an inter­est­ing camel’s nose for get­ting more con­tex­tual nar­ra­tive and less ridicu­lous over­gen­er­al­iza­tion (even acci­den­tally) in an engi­neer­ing paper.…
  
  algo­rithms pro­gram­ming subjective-​​objective-​​decontextualization-​​bias rather-​​interesting

• [1205.2200] A Greedy Dou­ble Swap Heuris­tic for Nurse Scheduling

  “One of the key chal­lenges of nurse sched­ul­ing prob­lem (NSP) is the num­ber of con­straints placed on prepar­ing the timetable, both from the reg­u­la­tory require­ments as well as the patients’ demand for the appro­pri­ate nurs­ing care spe­cial­ists. In addi­tion, the pref­er­ences of the nurs­ing staffs related to their work sched­ules add another dimen­sion of com­plex­ity. Most solu­tions pro­posed for solv­ing nurse sched­ul­ing involve the use of math­e­mat­i­cal pro­gram­ming and gen­er­ally con­sid­ers only the hard con­straints. How­ever, the psy­cho­log­i­cal needs of the nurses are ignored and this resulted in sub­se­quent inter­ven­tions by the nurs­ing staffs to rem­edy any defi­ciency and often results in last minute changes to the sched­ule. In this paper, we present a staff pref­er­ence opti­miza­tion frame­work which is solved with a greedy dou­ble swap heuris­tic. The heuris­tic yields good per­for­mance in speed at solv­ing the prob­lem. The heuris­tic is sim­ple and we will demon­strate its per­for­mance by imple­ment­ing it on open source spread­sheet software.”
  
  sched­ul­ing operations-​​research heuris­tics performance-​​measure nudge-​​targets

• What is Max? « Cycling 74

  “Max gives you the parts to cre­ate unique sounds, stun­ning visu­als, and engag­ing inter­ac­tive media. These parts are called ‘objects’ – visual boxes that con­tain tiny pro­grams to do some­thing spe­cific. Each object does some­thing dif­fer­ent. Some make noises, some make video effects, oth­ers just do sim­ple cal­cu­la­tions or make deci­sions. In Max you add objects to a visual can­vas and con­nect them together with patch­cords. You can use as many as you like. By com­bin­ing objects, you cre­ate inter­ac­tive and unique soft­ware with­out ever writ­ing any code (you can do that too if you really want to). Just connect.”
  
  visual-​​programming genetic-​​programming-​​target generative-​​art soft­ware lan­guages

• [1205.3397] 1.85 Approx­i­ma­tion for Min-​​Power Strong Connectivity

  “Given a directed sim­ple graph G=(V,E) and a nonnegative-​​valued cost func­tion the power of a ver­tex u in a directed span­ning sub­graph H is given by the max­i­mum cost of an arcs of H exit­ing u. The power of H is the sum of the power of its ver­tices. Power Assign­ment seeks to min­i­mize the power of H while H sat­is­fies some con­nec­tiv­ity con­straint. In this paper, we assume E is bidi­rected (for every directed edge e in E, the oppo­site edge exists and has the same cost), while H is required to be strongly con­nected. This is the orig­i­nal power assign­ment prob­lem intro­duced by Chen and Huang in 1989, who proved that bidi­rected min­i­mum span­ning tree has approx­i­ma­tion ratio at most 2 (this is tight). In Approx 2010, we intro­duced a Greedy approx­i­ma­tion algo­rithm and claimed a ratio of 1.992. Here we improve the analy­sis to 1.85.”
  
  algo­rithms computational-​​complexity operations-​​research nudge-​​targets

• [1206.1106] No More Pesky Learn­ing Rates

  “The per­for­mance of sto­chas­tic gra­di­ent descent (SGD) depends crit­i­cally on how learn­ing rates are tuned and decreased over time. We pro­pose a method to auto­mat­i­cally adjust mul­ti­ple learn­ing rates so as to min­i­mize the expected error at any one time. The method relies on local gra­di­ent vari­a­tions across sam­ples. Using a num­ber of con­vex and non-​​convex learn­ing tasks, we show that the result­ing algo­rithm matches the per­for­mance of the best set­tings obtained through sys­tem­atic search, and effec­tively removes the need for learn­ing rate tuning.”
  
  opti­miza­tion algo­rithms gradient-​​descent adaptive-​​control silos-​​in-​​action

• Prac­tic­ing Ruby

  “Get­ting bet­ter at soft­ware devel­op­ment can be hard work. There is an end­less sea of learn­ing mate­ri­als out there, but just fig­ur­ing out what top­ics you should focus on could take up all of your time if you let it. Don’t fall into that trap, instead, let me do the leg­work for you! As a sub­scriber to Prac­tic­ing Ruby, you’ll get access to well-​​polished weekly brain dumps about top­ics that will help you become a bet­ter Ruby devel­oper. You’ll also be able to join a ded­i­cated group of Prac­tic­ing Ruby­ists in lively con­ver­sa­tions about the eclec­tic mix of top­ics I’m writ­ing about.”
  
  Ruby pro­gram­ming tuto­r­ial sub­scrip­tions to-​​read

• [1206.1103] Peri­odiz­ing qua­sicrys­tals: Anom­alous dif­fu­sion in qua­si­peri­odic systems

  “We intro­duce a con­struc­tion to embed a qua­si­peri­odic lat­tice of obsta­cles into a sin­gle unit cell of a higher-​​dimensional space, with peri­odic bound­ary con­di­tions. This con­struc­tion trans­par­ently shows the exis­tence of chan­nels in these systems,in which par­ti­cles may travel with­out col­lid­ing, up to a crit­i­cal obsta­cle radius. It pro­vides a sim­ple and effi­cient algo­rithm for numer­i­cal sim­u­la­tion of dynam­ics in qua­si­peri­odic struc­tures, as well as giv­ing a nat­ural notion of uni­form dis­tri­b­u­tion (mea­sure) and aver­ages. As an appli­ca­tion, we sim­u­late dif­fu­sion in a two-​​dimensional qua­sicrys­tal, find­ing three dif­fer­ent regimes, in par­tic­u­lar atyp­i­cal weak super-​​diffusion in the pres­ence of chan­nels, and sub-​​diffusion when obsta­cles overlap.”
  
  qua­sicrys­tals tiling algo­rithms topol­ogy sim­u­la­tion computational-​​geometry

• [1205.3193] A Com­par­a­tive Study of Col­lab­o­ra­tive Fil­ter­ing Algorithms

  “Col­lab­o­ra­tive fil­ter­ing is a rapidly advanc­ing research area. Every year sev­eral new tech­niques are pro­posed and yet it is not clear which of the tech­niques work best and under what con­di­tions. In this paper we con­duct a study com­par­ing sev­eral col­lab­o­ra­tive fil­ter­ing tech­niques — both clas­sic and recent state-​​of-​​the-​​art — in a vari­ety of exper­i­men­tal con­texts. Specif­i­cally, we report con­clu­sions con­trol­ling for num­ber of items, num­ber of users, spar­sity level, per­for­mance cri­te­ria, and com­pu­ta­tional com­plex­ity. Our con­clu­sions iden­tify what algo­rithms work well and in what con­di­tions, and con­tribute to both indus­trial deploy­ment col­lab­o­ra­tive fil­ter­ing algo­rithms and to the research community.”
  
  overview collaborative-​​filtering performance-​​space pre­dic­tion algo­rithms swarms

• Ben Linus and the Magic Box — YouTube

  Genetic Pro­gram­ming explained. [accord­ing to most folks]
  
  genetic-​​programming Lost self-​​definition you-​​keep-​​using-​​that-​​word

• [1204.6170] A dis­trib­uted resource allo­ca­tion algo­rithm for many processes

  “Resource allo­ca­tion is the prob­lem that a process may enter a crit­i­cal sec­tion CS of its code only when its resource require­ments are not in con­flict with those of other processes in their crit­i­cal sec­tions. For each exe­cu­tion of CS, these require­ments are given anew. In the resource require­ments, lev­els can be dis­tin­guished, such as e.g. read access or write access. We allow infi­nitely many processes that com­mu­ni­cate by reli­able asyn­chro­nous mes­sages and have finite mem­ory. A sim­ple starvation-​​free solu­tion is pre­sented. Processes only wait for one another when they have con­flict­ing resource require­ments. The cor­rect­ness of the solu­tion is argued with invari­ants and tem­po­ral logic. It has been ver­i­fied with the proof assis­tant PVS.”
  
  distributed-​​processing con­cur­rency nudge-​​targets algo­rithms mod­el­ing

• [1205.5911] A Hough Trans­form Approach to Solv­ing Lin­ear Min-​​Max Problems

  “Sev­eral ways to accel­er­ate the solu­tion of 2D/​3D lin­ear min-​​max prob­lems in $n$ con­straints are dis­cussed. We also present an algo­rithm for solv­ing such prob­lems in the 2D case, which is supe­rior to CGAL’s lin­ear pro­gram­ming solver, both in per­for­mance and in stability.”
  
  algo­rithms computational-​​geometry nudge-​​targets convex-​​hulls linear-​​programming

• [1205.2664] A Bayesian Sam­pling Approach to Explo­ration in Rein­force­ment Learning

  “We present a mod­u­lar approach to rein­force­ment learn­ing that uses a Bayesian rep­re­sen­ta­tion of the uncer­tainty over mod­els. The approach, BOSS (Best of Sam­pled Set), dri­ves explo­ration by sam­pling mul­ti­ple mod­els from the pos­te­rior and select­ing actions opti­misti­cally. It extends pre­vi­ous work by pro­vid­ing a rule for decid­ing when to resam­ple and how to com­bine the mod­els. We show that our algo­rithm achieves nearop­ti­mal reward with high prob­a­bil­ity with a sam­ple com­plex­ity that is low rel­a­tive to the speed at which the pos­te­rior dis­tri­b­u­tion con­verges dur­ing learn­ing. We demon­strate that BOSS per­forms quite favor­ably com­pared to state-​​of-​​the-​​art reinforcement-​​learning approaches and illus­trate its flex­i­bil­ity by pair­ing it with a non-​​parametric model that gen­er­al­izes across states.”
  
  exploration-​​and-​​exploitation algo­rithms machine-​​learning reinforcement-​​learning integrate-​​method-​​into-​​GP

• Stowe Boyd

  “The new media folks des­per­ately want to write for some hypo­thet­i­cal audi­ence, one they can find the cen­ter of. They are like bor­der col­lies, wired to herd sheep and fran­tic if they can’t find any.”
  
  disintermediation-​​in-​​action jour­nal­ism public-​​policy poll­sters cultural-​​assumptions

• [1205.2282] A Dis­cus­sion on Par­al­leliza­tion Schemes for Sto­chas­tic Vec­tor Quan­ti­za­tion Algorithms

  “This paper stud­ies par­al­leliza­tion schemes for sto­chas­tic Vec­tor Quan­ti­za­tion algo­rithms in order to obtain time speed-​​ups using dis­trib­uted resources. We show that the most intu­itive par­al­leliza­tion scheme does not lead to bet­ter per­for­mances than the sequen­tial algo­rithm. Another dis­trib­uted scheme is there­fore intro­duced which obtains the expected speed-​​ups. Then, it is improved to fit imple­men­ta­tion on dis­trib­uted archi­tec­tures where com­mu­ni­ca­tions are slow and inter-​​machines syn­chro­niza­tion too costly. The schemes are tested with sim­u­lated dis­trib­uted archi­tec­tures and, for the last one, with Microsoft Win­dows Azure plat­form obtain­ing speed-​​ups up to 32 Vir­tual Machines.”
  
  algo­rithms distributed-​​processing par­al­leliza­tion nudge-​​targets

• Crypto break­through shows Flame was designed by world-​​class sci­en­tists | Ars Technica

  “More inter­est­ingly, the results have shown that not our pub­lished chosen-​​prefix col­li­sion attack was used, but an entirely new and unknown vari­ant,” Stevens wrote in a state­ment dis­trib­uted on Thurs­day. “This has led to our con­clu­sion that the design of Flame is partly based on world-​​class crypt­analy­sis. Fur­ther research will be con­ducted to recon­struct the entire chosen-​​prefix col­li­sion attack devised for Flame.“ The analy­sis rein­forces the­o­ries that researchers from Kasper­sky Lab, CrySyS Lab, and Syman­tec pub­lished almost two weeks ago. Namely, Flame could only have been devel­oped with the back­ing of a wealthy nation-​​state. Stevens’ and de Weger’s con­clu­sion means that, in addi­tion to a team of engi­neers who devel­oped a global mal­ware plat­form that escaped detec­tion for at least two years, Flame also required world-​​class cryp­tog­ra­phers who have bro­ken new ground in their field. “It’s not a garden-​​variety col­li­sion attack, or just an imple­men­ta­tion of pre­vi­ous MD5 col­li­sions papers—which would be dif­fi­cult enough,” Matthew Green, a pro­fes­sor spe­cial­iz­ing in cryp­tog­ra­phy in the com­puter sci­ence depart­ment at Johns Hop­kins Uni­ver­sity, told Ars. “There were math­e­mati­cians doing new sci­ence to make Flame work.”
  
  cryp­tog­ra­phy MD5-​​woops algo­rithms nudge-​​targets

• On Out­reach: something’s got to give | Neu­rotic Physiology

  “A change in the way acad­e­mia views out­reach is going to take a while, and it may take even longer for sci­ence com­mu­ni­ca­tion to become a really respected “alter­na­tive” career. In the mean­time, many sci­en­tists DO do out­reach. They go into schools, they give talks at bars, they talk to their friends and fam­ily. Some of them send me and other sci­ence blog­gers arti­cles (THANK YOU!! And you know, never hes­i­tate to send me an arti­cle!) to cover, or speak out proudly in sup­port of their work. There IS sci­ence out­reach out there, and a lot of it is GREAT.”
  
  sci­ence! academic-​​culture disintermediation-​​targets-​​who-​​have-​​noticed

• [1206.0785] The Quan­tum Frontier

  “Many open prob­lems remain. Some are of a fun­da­men­tal nature. What does nature allow us to com­pute effi­ciently? What does nature allow us to make secure? Oth­ers are of a more prac­ti­cal nature. How will we build scal­able quan­tum com­put­ers? For what prob­lems are there effec­tive quan­tum algo­rithms? How broad an impact will quan­tum infor­ma­tion pro­cess­ing have? At the very least, quan­tum com­pu­ta­tion, and quan­tum infor­ma­tion pro­cess­ing more gen­er­ally, has changed for­ever how human­ity thinks about and works with physics, com­pu­ta­tion, and information.”
  
  quan­tums quantum-​​computing overview

• [1205.6867] Min­i­miz­ing the aver­age dis­tance to a clos­est leaf in a phy­lo­ge­netic tree

  “In this paper we described a sim­ple new cri­te­rion, min­i­miz­ing the Aver­age Dis– tance to the Clos­est Leaf (ADCL), for find­ing a sub­set of sequences that either rep­re­sent the diver­sity of the sequences in a sam­ple, or are close on aver­age to a set of query sequences. In doing so, abun­dance infor­ma­tion is taken into account and attempt to strike a bal­ance between opti­mal­ity and cen­tral­ity in the tree. In par­tic­u­lar, this cri­te­rion is the only way in which we are aware to pick sequences that are phy­lo­ge­net­i­cally close on aver­age to a set of query sequences. We have also inves­ti­gated means of min­i­miz­ing the ADCL, includ­ing a heuris­tic that per­forms well in prac­tice and an exact dynamic pro­gram. ADCL min­i­miza­tion appears to avoid pick­ing chimeric sequences in simulation.”
  
  algo­rithms phy­lo­ge­net­ics cladis­tics performance-​​measure nudge-​​targets bioin­for­mat­ics

• fish’s fish shell

  “How do I run a com­mand from his­tory? Type some part of the com­mand, and then hit the up or down arrow keys to nav­i­gate through his­tory matches.”
  
  want unix shell

• [1206.0823] Orthog­o­nal Match­ing Pur­suit with Noisy and Miss­ing Data: Low and High Dimen­sional Results

  “Many mod­els for sparse regres­sion typ­i­cally assume that the covari­ates are known com­pletely, and with­out noise. Par­tic­u­larly in high-​​dimensional appli­ca­tions, this is often not the case. This paper devel­ops effi­cient OMP-​​like algo­rithms to deal with pre­cisely this set­ting. Our algo­rithms are as effi­cient as OMP, and improve on the best-​​known results for miss­ing and noisy data in regres­sion, both in the high-​​dimensional set­ting where we seek to recover a sparse vec­tor from only a few mea­sure­ments, and in the clas­si­cal low-​​dimensional set­ting where we recover an unstruc­tured regres­sor. In the high-​​dimensional set­ting, our support-​​recovery algo­rithm requires no knowl­edge of even the sta­tis­tics of the noise. Along the way, we also obtain improved per­for­mance guar­an­tees for OMP for the stan­dard sparse regres­sion prob­lem with Gauss­ian noise.”
  
  sta­tis­tics algo­rithms nudge-​​targets performance-​​measure cultural-​​assumptions-​​of-​​statistics

• [1204.5213] Solv­ing Weighted Vot­ing Game Design Prob­lems Opti­mally: Rep­re­sen­ta­tions, Syn­the­sis, and Enumeration

  “We study the inverse power index prob­lem for weighted vot­ing games: the prob­lem of find­ing a weighted vot­ing game in which the power of the play­ers is as close as pos­si­ble to a cer­tain tar­get dis­tri­b­u­tion. Our goal is to find algo­rithms that solve this prob­lem exactly. Thereto, we study var­i­ous sub­classes of sim­ple games, and their asso­ci­ated rep­re­sen­ta­tion meth­ods. We sur­vey algo­rithms and impos­si­bil­ity results for the syn­the­sis prob­lem, i.e., con­vert­ing a rep­re­sen­ta­tion of a sim­ple game into another rep­re­sen­ta­tion. We con­tribute to the syn­the­sis prob­lem by show­ing that it is impos­si­ble to com­pute in poly­no­mial time the list of ceil­ing coali­tions (also known as shift-​​maximal los­ing coali­tions) of a game from its list of roof coali­tions (also known as shift-​​minimal win­ning coali­tions), and vice versa. ”
  
  inverse-​​problems algo­rithms game-​​theory vot­ing nudge-​​targets

• [1206.0937] Detect­ing Acti­va­tions over Graphs using Span­ning Tree Wavelet Bases

  “This paper focuses on the prob­lem of detect­ing acti­va­tions over a graph when obser­va­tions are cor­rupted by noise. The prob­lem of detect­ing graph-​​structured acti­va­tions is rel­e­vant to many appli­ca­tions includ­ing iden­ti­fy­ing con­ges­tion in router and road net­works, elic­it­ing pref­er­ences in social net­works, and detect­ing viruses in human and com­puter net­works. Fur­ther­more, these appli­ca­tions require that the method is scal­able to large graphs. Luck­ily, com­puter sci­ence boasts a plethora of effi­cient graph based algo­rithms that we can adapt to the detec­tion framework.”
  
  sta­tis­tics network-​​theory algo­rithms pattern-​​discovery inverse-​​problems nudge-​​targets

• [1206.1270] Fac­tor­ing non­neg­a­tive matri­ces with lin­ear programs

  “This paper describes a new approach for com­put­ing non­neg­a­tive matrix fac­tor­iza­tions (NMFs) with lin­ear pro­gram­ming. The key idea is a data-​​driven model for the fac­tor­iza­tion, in which the most salient fea­tures in the data are used to express the remain­ing fea­tures. More pre­cisely, given a data matrix X, the algo­rithm iden­ti­fies a matrix C that sat­is­fies X is approx­i­mately equal to CX and some lin­ear con­straints. The matrix C selects fea­tures, which are then used to com­pute a low-​​rank NMF of X. A the­o­ret­i­cal analy­sis demon­strates that this approach has the same type of guar­an­tees as the recent NMF algo­rithm of Arora et al. (2012). In con­trast with this ear­lier work, the pro­posed method (1) has bet­ter noise tol­er­ance, (2) extends to more gen­eral noise mod­els, and (3) leads to effi­cient, scal­able algo­rithms. Exper­i­ments with syn­thetic and real datasets pro­vide evi­dence that the new approach is also supe­rior in prac­tice. An opti­mized C++ imple­men­ta­tion of the new algo­rithm can fac­tor a multi-​​Gigabyte matrix in a mat­ter of minutes.”
  
  via:cshalizi algo­rithms linear-​​programming nudge-​​targets

• [1206.1032] Fre­quent Pat­terns min­ing in time-​​sensitive Data Stream

  “Min­ing fre­quent item­sets through sta­tic Data­bases has been exten­sively stud­ied and used and is always con­sid­ered a highly chal­leng­ing task. For this rea­son it is inter­est­ing to extend it to data streams field. In the stream­ing case, the fre­quent pat­terns’ min­ing has much more infor­ma­tion to track and much greater com­plex­ity to man­age. Infre­quent items can become fre­quent later on and hence can­not be ignored. The out­put struc­ture needs to be dynam­i­cally incre­mented to reflect the evo­lu­tion of item­set fre­quen­cies over time. In this paper, we study this prob­lem and specif­i­cally the method­ol­ogy of min­ing time-​​sensitive data streams. We tried to improve an exist­ing algo­rithm by increas­ing the tem­po­ral accu­racy and dis­card­ing the out-​​of-​​date data by adding a new con­cept called the “Shak­ing Point”. We pre­sented as well some exper­i­ments illus­trat­ing the time and space required.”
  
  pattern-​​discovery time-​​series data-​​mining algo­rithms trad­ing nudge-​​targets

• [1206.0580] O(1) Delta Com­po­nent Com­pu­ta­tion Tech­nique for the Qua­dratic Assign­ment Problem

  “The paper describes a novel tech­nique that allows to reduce by half the num­ber of delta val­ues that were required to be com­puted with com­plex­ity O(N) in most of the heuris­tics for the qua­dratic assign­ment prob­lem. Using the cor­re­la­tion between the old and new delta val­ues, obtained in this work, a new for­mula of com­plex­ity O(1) is pro­posed. Found result leads up to 25% per­for­mance increase in such well-​​known algo­rithms as Robust Tabu Search and oth­ers based on it.”
  
  algo­rithms com­bi­na­torics operations-​​research quadratic-​​assignment nudge-​​targets

• [1206.1268] Para­me­ter Esti­ma­tion Through Ignorance

  “Dynam­i­cal mod­el­ling lies at the heart of our under­stand­ing of phys­i­cal sys­tems. Its role in sci­ence is deeper than mere oper­a­tional fore­cast­ing, in that it allows us to eval­u­ate the ade­quacy of the math­e­mat­i­cal struc­ture of our mod­els. Despite the impor­tance of model para­me­ters, there is no gen­eral method of para­me­ter esti­ma­tion out­side lin­ear sys­tems. A new rel­a­tively sim­ple method of para­me­ter esti­ma­tion for non­lin­ear sys­tems is pre­sented, based on vari­a­tions in the accu­racy of prob­a­bil­ity fore­casts. It is illus­trated on the Logis­tic Map, the Henon Map and the 12-​​D Lorenz96 flow, and its abil­ity to out­per­form lin­ear least squares in these sys­tems is explored at var­i­ous noise lev­els and sam­pling rates. As expected, it is more effec­tive when the fore­cast error dis­tri­b­u­tions are non-​​Gaussian. The new method selects para­me­ter val­ues by min­i­miz­ing a proper, local skill score for con­tin­u­ous prob­a­bil­ity fore­casts as a func­tion of the para­me­ter val­ues. This new approach is eas­ier to imple­ment in prac­tice than alter­na­tive non­lin­ear meth­ods based on the geom­e­try of attrac­tors or the abil­ity of the model to shadow the obser­va­tions. New direct mea­sures of inad­e­quacy in the model, the “Implied Igno­rance” and the infor­ma­tion deficit are introduced.”
  
  sta­tis­tics symbolic-​​regression parameter-​​estimation algo­rithms nudge-​​targets

• 10 Time­frames | Con­tents Magazine

  “…And lis­ten, trust me, even if you do not feel that way at the end of these years, even if you are feel­ing burned out and done with the vagaries of social user design inter­ac­tion uni­ver­sal community-​​driven agile infor­ma­tion expe­ri­ence, even if you are ready to close your lap­top screen for­ever, you are beloved on the earth. You are skilled and tal­ented and young and bright and accred­ited. The world wishes it were you.”
  
  advice speech

• [1206.0629] DEMON: a Local-​​First Dis­cov­ery Method for Over­lap­ping Communities

  “Com­mu­nity dis­cov­ery in com­plex net­works is an inter­est­ing prob­lem with a num­ber of appli­ca­tions, espe­cially in the knowl­edge extrac­tion task in social and infor­ma­tion net­works. How­ever, many large net­works often lack a par­tic­u­lar com­mu­nity orga­ni­za­tion at a global level. In these cases, tra­di­tional graph par­ti­tion­ing algo­rithms fail to let the latent knowl­edge embed­ded in mod­u­lar struc­ture emerge, because they impose a top-​​down global view of a net­work. We pro­pose here a sim­ple local-​​first approach to com­mu­nity dis­cov­ery, able to unveil the mod­u­lar orga­ni­za­tion of real com­plex net­works. This is achieved by demo­c­ra­t­i­cally let­ting each node vote for the com­mu­ni­ties it sees sur­round­ing it in its lim­ited view of the global sys­tem, i.e. its ego neigh­bor­hood, using a label prop­a­ga­tion algo­rithm; finally, the local com­mu­ni­ties are merged into a global col­lec­tion. We tested this intu­ition against the state-​​of-​​the-​​art over­lap­ping and non-​​overlapping com­mu­nity dis­cov­ery meth­ods, and found that our new method clearly out­per­forms the oth­ers in the qual­ity of the obtained com­mu­ni­ties, eval­u­ated by using the extracted com­mu­ni­ties to pre­dict the meta­data about the nodes of sev­eral real world net­works. We also show how our method is deter­min­is­tic, fully incre­men­tal, and has a lim­ited time com­plex­ity, so that it can be used on web-​​scale real networks.”
  
  network-​​theory algo­rithms community-​​discovery sta­tis­tics expla­na­tion referral-​​networks

• [1206.0430] Con­ges­tion Games on Weighted Directed Graphs, with Appli­ca­tions to Spec­trum Sharing

  “With the advance of com­plex large-​​scale net­works, it is becom­ing increas­ingly impor­tant to under­stand how self­ish and spa­tially dis­trib­uted indi­vid­u­als will share net­work resources with­out cen­tral­ized coor­di­na­tions. In this paper, we intro­duce the graph­i­cal con­ges­tion game with weighted edges (GCGWE) as a gen­eral the­o­ret­i­cal model to study this prob­lem. In GCGWE, we view the play­ers as ver­tices in a weighted graph. The amount of neg­a­tive impact (e.g. con­ges­tion) caused by two close-​​by play­ers to each other is deter­mined by the weight of the edge link­ing them. The GCGWE uni­fies and sig­nif­i­cantly gen­er­al­izes sev­eral sim­pler mod­els con­sid­ered in the pre­vi­ous lit­er­a­ture, and is well suited for mod­el­ing a wide range of net­work­ing sce­nar­ios. One good exam­ple is to use the GCGWE to model spec­trum shar­ing in wire­less net­works, where we can prop­erly define the edge weights and pay­off func­tions to cap­ture the rather com­pli­cated inter­fer­ence rela­tion­ship between wire­less nodes. By iden­ti­fy­ing which GCG­WEs pos­sess pure Nash equi­lib­ria and the very desir­able finite improve­ment prop­erty, we gain insight into when spa­tially dis­trib­uted wire­less nodes will be able to self-​​organize into a mutu­ally accept­able resource allo­ca­tion. We also con­sider the effi­ciency of the pure Nash equi­lib­ria, and the com­pu­ta­tional com­plex­ity of find­ing them.”
  
  network-​​theory algo­rithms agent-​​based nudge-​​targets com­plex­ol­ogy

• [1206.0855] A Mixed Observ­abil­ity Markov Deci­sion Process Model for Musi­cal Pitch

  “Par­tially observ­able Markov deci­sion processes have been widely used to pro­vide mod­els for real-​​world deci­sion mak­ing prob­lems. In this paper, we will pro­vide a method in which a slightly dif­fer­ent ver­sion of them called Mixed observ­abil­ity Markov deci­sion process, MOMDP, is going to join with our prob­lem. Basi­cally, we aim at offer­ing a behav­ioural model for inter­ac­tion of intel­li­gent agents with musi­cal pitch envi­ron­ment and we will show that how MOMDP can shed some light on build­ing up a deci­sion mak­ing model for musi­cal pitch conveniently.”
  
  music machine-​​learning generative-​​art pattern-​​discovery nudge-​​targets

• [1206.0766] Why Opti­mal States Recruit Fewer Reac­tions in Meta­bolic Networks

  “The meta­bolic net­work of a liv­ing cell involves sev­eral hun­dreds or thou­sands of inter­con­nected bio­chem­i­cal reac­tions. Pre­vi­ous research has shown that under real­is­tic con­di­tions only a frac­tion of these reac­tions is con­cur­rently active in any given cell. This is par­tially deter­mined by nutri­ent avail­abil­ity, but is also strongly depen­dent on the meta­bolic func­tion and net­work struc­ture. Here, we estab­lish rig­or­ous bounds show­ing that the frac­tion of active reac­tions is smaller (rather than larger) in meta­bolic net­works evolved or engi­neered to opti­mize a spe­cific meta­bolic task, and we show that this is largely deter­mined by the pres­ence of ther­mo­dy­nam­i­cally irre­versible reac­tions in the net­work. We also show that the inac­ti­va­tion of a cer­tain num­ber of reac­tions deter­mined by irre­versibil­ity can gen­er­ate a cas­cade of sec­ondary reac­tion inac­ti­va­tions that prop­a­gates through the net­work. The math­e­mat­i­cal results are com­ple­mented with numer­i­cal sim­u­la­tions of the meta­bolic net­works of the bac­terium Escherichia coli and of human cells, which show, coun­ter­in­tu­itively, that even the max­i­miza­tion of the total reac­tion flux in the net­work leads to a reduced num­ber of active reactions.”
  
  network-​​theory biological-​​engineering metabolic-​​networks systems-​​biology engineering-​​design structural-​​biology

• It Evolved Into Birds: Ten Science-​​Fictional Thinkers On the Past and Future of Cyber­punk | Motherboard

  “But the ideas orig­i­nally behind that trope — now that’s the cool part. My friends who work in aero­space tell me the old guys who built the indus­try all grew up read­ing Hein­lein and Clarke, and went into aero­space to turn those crazy things they read as kids into prac­ti­cal real­i­ties as adults. Well, I work in super­com­put­ing, and I can assure you that this indus­try is full of young geniuses who grew up read­ing Gib­son, Vinge, and Rucker — and yes, me — and they went into this field to do the same thing. We don’t quite live in the world that cyber­punk fic­tion pre­dicted. But we live in the world that the kids who grew up read­ing cyber­punk fic­tion built, and that is a very cool thing indeed.”
  
  cyber­punk fic­tion genre ret­ro­spec­tive science-​​fiction cultural-​​norms