Tag Archives: network-theory

Items of some interest:

Posted on by

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

  • [1206.6866] Sto­chas­tic Opti­mal Con­trol in Con­tin­u­ous Space-​​Time Multi-​​Agent Systems

    “Recently, a the­ory for sto­chas­tic opti­mal con­trol in non-​​linear dynam­i­cal sys­tems in con­tin­u­ous space-​​time has been devel­oped (Kap­pen, 2005). We apply this the­ory to col­lab­o­ra­tive multi-​​agent sys­tems. The agents evolve accord­ing to a given non-​​linear dynam­ics with addi­tive Wiener noise. Each agent can con­trol its own dynam­ics. The goal is to min­i­mize the accu­mu­lated joint cost, which con­sists of a state depen­dent term and a term that is qua­dratic in the con­trol. We focus on sys­tems of non-​​interacting agents that have to dis­trib­ute them­selves opti­mally over a num­ber of tar­gets, given a set of end-​​costs for the dif­fer­ent pos­si­ble agent-​​target com­bi­na­tions. We show that opti­mal con­trol is the com­bi­na­to­r­ial sum of inde­pen­dent single-​​agent single-​​target opti­mal con­trols weighted by a fac­tor pro­por­tional to the end-​​costs of the dif­fer­ent com­bi­na­tions. Thus, multi-​​agent con­trol is related to a stan­dard graph­i­cal model infer­ence prob­lem. The addi­tional com­pu­ta­tional cost com­pared to single-​​agent con­trol is expo­nen­tial in the tree-​​width of the graph spec­i­fy­ing the com­bi­na­to­r­ial sum times the num­ber of tar­gets. We illus­trate the result by sim­u­la­tions of sys­tems with up to 42 agents.”

    coor­di­na­tion agent-​​based emergent-​​design nudge-​​targets control-​​theory

  • [1205.6917] Robust self-​​triggered coor­di­na­tion with ternary controllers

    “This paper regards coor­di­na­tion of net­worked sys­tems, which is stud­ied in the frame­work of hybrid dynam­i­cal sys­tems. We design a coor­di­na­tion scheme which com­bines the use of ternary con­trollers with a self-​​triggered com­mu­ni­ca­tion pol­icy. The com­mu­ni­ca­tion pol­icy requires the agents to col­lect, at each sam­pling time, rel­a­tive mea­sure­ments of their neigh­bors’ states: the col­lected infor­ma­tion is then used to update the con­trol and deter­mine the fol­low­ing sam­pling time. We prove that the pro­posed scheme ensures finite-​​time con­ver­gence to a neigh­bor­hood of a con­sen­sus state. We then study the robust­ness of the pro­posed self-​​triggered coor­di­na­tion sys­tem with respect to skews in the agents’ local clocks, to delays, and to lim­ited pre­ci­sion in com­mu­ni­ca­tion. Fur­ther­more, we present two sig­nif­i­cant vari­a­tions of our scheme. First, we design a time-​​varying con­troller which asymp­tot­i­cally dri­ves the sys­tem to con­sen­sus. Sec­ond, we adapt our frame­work to a com­mu­ni­ca­tion model in which an agent does not poll all its neigh­bors simul­ta­ne­ously, but sin­gle neigh­bors instead. This com­mu­ni­ca­tion pol­icy actu­ally leads to a self-​​triggered “gos­sip” coor­di­na­tion system.”

    network-​​theory multi-​​agent-​​systems mechanism-​​design emergent-​​design consensus-​​systems nudge-​​targets algo­rithms

  • [1205.2607] Simulation-​​Based Game The­o­retic Analy­sis of Key­word Auc­tions with Low-​​Dimensional Bid­ding Strategies

    “We per­form a simulation-​​based analy­sis of key­word auc­tions mod­eled as one-​​shot games of incom­plete infor­ma­tion to study a series of mech­a­nism design ques­tions. Our first ques­tion addresses the degree to which incen­tive com­pat­i­bil­ity fails in gen­er­al­ized second-​​price (GSP) auc­tions. Our results sug­gest that sin­cere bid­ding in GSP auc­tions is a strik­ingly poor strat­egy and a poor pre­dic­tor of equi­lib­rium out­comes. We next show that the rank-​​by-​​revenue mech­a­nism is wel­fare opti­mal, cor­rob­o­rat­ing past results. Finally, we ana­lyze profit as a func­tion of auc­tion mech­a­nism under a series of alter­na­tive set­tings. Our con­clu­sions coin­cide with those of Lahaie and Pen­nock [2007] when val­ues and qual­ity scores are strongly pos­i­tively cor­re­lated: in such a case, rank-​​by-​​bid rules are clearly supe­rior. We diverge, how­ever, in show­ing that auc­tions that put lit­tle weight on qual­ity scores almost uni­ver­sally dom­i­nate the pure rank-​​by-​​revenue scheme.”

    game-​​theory agent-​​based sim­u­la­tion eco­nom­ics auc­tion nudge-​​targets

  • Graph­ing the his­tory of phi­los­o­phy « Drunks&Lampposts

    “Each philoso­pher is a node in the net­work and the lines between them (or edges in the ter­mi­nol­ogy of graph the­ory) rep­re­sents lines of influ­ence. The node and text are sized accord­ing to the num­ber of con­nec­tions (both in and out). The algo­rithm that visu­alises the graph also tends to put the bet­ter con­nected nodes in the cen­tre of the dia­gram so we see the most influ­en­tial philoso­phers, in large text, clus­tered in the cen­tre. It all seems about right with the major fig­ures in the west­ern philo­soph­i­cal tra­di­tion tak­ing the cen­tre stage. (I need to also add the direc­tion of influ­ence with a arrow head – some­thing I’ve not got round to yet.) A short­com­ing how­ever is that this eval­u­a­tion only takes into account direct lines of influ­ence. Indi­rect influ­ence via another per­son in the net­work does not enter into it. This prob­a­bly explains why Descartes is smaller than you’d think. It would also be bet­ter if the nodes were sized only by the num­ber of out­ward con­nec­tions although I think over­all the dif­fer­ences would be slight. I’ll get round to that.”

    visu­al­iza­tion philosopher-​​mining

  • [1206.3666] Unsu­per­vised adap­ta­tion of brain machine inter­face decoders

    “The per­for­mance of neural decoders can degrade over time due to non­sta­tion­ar­i­ties in the rela­tion­ship between neu­ronal activ­ity and behav­ior. In this case, brain-​​machine inter­faces (BMI) require adap­ta­tion of their decoders to main­tain high per­for­mance across time. One way to achieve this is by use of peri­od­i­cal cal­i­bra­tion phases, dur­ing which the BMI sys­tem (or an exter­nal human demon­stra­tor) instructs the user to per­form cer­tain move­ments or behav­iors. This approach has two dis­ad­van­tages: (i) cal­i­bra­tion phases inter­rupt the autonomous oper­a­tion of the BMI and (ii) between two cal­i­bra­tion phases the BMI per­for­mance might not be sta­ble but con­tin­u­ously decrease. A bet­ter alter­na­tive would be that the BMI decoder is able to con­tin­u­ously adapt in an unsu­per­vised man­ner dur­ing autonomous BMI oper­a­tion, i.e. with­out know­ing the move­ment inten­tions of the user. In the present arti­cle, we present an effi­cient method for such unsu­per­vised train­ing of BMI sys­tems for con­tin­u­ous move­ment con­trol. The pro­posed method uti­lizes a cost func­tion derived from neu­ronal record­ings, which guides a learn­ing algo­rithm to eval­u­ate the decod­ing para­me­ters. We ver­ify the per­for­mance of our adap­tive method by sim­u­lat­ing a BMI user with an opti­mal feed­back con­trol model and its inter­ac­tion with our adap­tive BMI decoder. The sim­u­la­tion results show that the cost func­tion and the algo­rithm yield fast and pre­cise tra­jec­to­ries towards tar­gets at ran­dom ori­en­ta­tions on a 2-​​dimensional com­puter screen. For ini­tially unknown and non-​​stationary tun­ing para­me­ters, our unsu­per­vised method is still able to gen­er­ate pre­cise tra­jec­to­ries and to keep its per­for­mance sta­ble in the long term. The algo­rithm can option­ally work also with neu­ronal error sig­nals instead or in con­junc­tion with the pro­posed unsu­per­vised adaptation.”

    FOR-​​SCIENCE brain-​​machine-​​interface user-​​interface adaptive-​​control emergent-​​design

  • [1206.3980] Visu­al­iz­ing Stream­ing Text Data with Dynamic Maps

    “The many end­less rivers of text now avail­able present a seri­ous chal­lenge in the task of glean­ing, ana­lyz­ing and dis­cov­er­ing use­ful infor­ma­tion. In this paper, we describe a method­ol­ogy for visu­al­iz­ing text streams in real time. The approach auto­mat­i­cally groups sim­i­lar mes­sages into “coun­tries,” with key­word sum­maries, using seman­tic analy­sis, graph clus­ter­ing and map gen­er­a­tion tech­niques. It han­dles the need for visual sta­bil­ity across time by dynamic graph lay­out and Pro­crustes pro­jec­tion tech­niques, enhanced with a novel sta­ble com­po­nent pack­ing algo­rithm. The result pro­vides a con­tin­u­ous, suc­cinct view of evolv­ing top­ics of inter­est. It can be used in pas­sive mode for overviews and sit­u­a­tional aware­ness, or as an inter­ac­tive data explo­ration tool. To make these ideas con­crete, we describe their appli­ca­tion to an online ser­vice called TwitterScope.”

    visu­al­iza­tion data algo­rithms user-​​experience

  • [1205.3352] Revis­it­ing the effect of exter­nal fields in Axelrod’s model of social dynamics

    “The study of the effects of spa­tially uni­form fields on the steady-​​state prop­er­ties of Axelrod’s model has yielded plenty of con­tro­ver­sial results. Here we re-​​examine the impact of this type of field for a selec­tion of para­me­ters such that the field-​​free steady state of the model is het­ero­ge­neous or mul­ti­cul­tural. Analy­ses of both one and two-​​dimensional ver­sions of Axelrod’s model indi­cate that, con­trary to pre­vi­ous claims in the lit­er­a­ture, the steady state remains het­ero­ge­neous regard­less of the value of the field strength. Turn­ing on the field leads to a dis­con­tin­u­ous decrease on the num­ber of cul­tural domains, which we argue is due to the insta­bil­ity of zero-​​field het­ero­ge­neous absorb­ing con­fig­u­ra­tions. We find, how­ever, that spa­tially nonuni­form fields that imple­ment a con­sen­sus rule among the neigh­bor­hood of the agents enforces homog­e­niza­tion. Although the over­all effects of the fields are essen­tially the same irre­spec­tive of the dimen­sion­al­ity of the model, we argue that the dimen­sion­al­ity has a sig­nif­i­cant impact on the sta­bil­ity of the field-​​free homo­ge­neous steady state.”

    com­plex­ol­ogy agent-​​based exter­nal­i­ties sim­u­la­tion evolutionary-​​economics nudge-​​targets

  • [1206.3421] Lin­ear Latent Vari­able Mod­els: The lava-​​package

    “An R pack­age for spec­i­fy­ing and esti­mat­ing lin­ear latent vari­able mod­els is pre­sented. The phi­los­o­phy of the imple­men­ta­tion is to sep­a­rate the model spec­i­fi­ca­tion from the actual data, which leads to a dynamic and easy way of mod­el­ing com­plex hier­ar­chi­cal struc­tures. Sev­eral advanced fea­tures are imple­mented includ­ing robust stan­dard errors for clus­tered cor­re­lated data, multi­group analy­ses, non-​​linear para­me­ter con­straints, infer­ence with incom­plete data, max­i­mum like­li­hood esti­ma­tion with cen­sored and binary obser­va­tions, and instru­men­tal vari­able esti­ma­tors. In addi­tion an exten­sive sim­u­la­tion inter­face cov­er­ing a broad range of non-​​linear gen­er­al­ized struc­tural equa­tion mod­els is described. The model and soft­ware are demon­strated in data of mea­sure­ments of the sero­tonin trans­porter in the human brain.”

    ontol­ogy sta­tis­tics algo­rithms R-​​language linear-​​models model-​​view-​​controller design-​​patterns

  • [1205.6129] The Miss­ing Mem­ris­tor: Novel Nan­otech­nol­ogy or rather new Case Study for the Phi­los­o­phy and Soci­ol­ogy of Science?

    “In 2008, it was widely announced that the miss­ing mem­ris­tor, a basic two-​​terminal elec­tri­cal cir­cuit ele­ment, had finally been dis­cov­ered. The mem­ris­tor is the fourth and last such cir­cuit ele­ment and thus com­pletes cir­cuit the­ory. Pre­dicted already in 1971, the even­tual dis­cov­ery of some­thing seem­ingly so basic needed almost 40 years. How­ever, this dis­cov­ery is doubted. The pre­dicted mem­ris­tor has no mate­r­ial mem­ory and is based on mag­netic flux, but the dis­cov­ered devices con­sti­tute ana­logue mem­ory stor­age that do not involve mag­net­ism. The per­son who orig­i­nally pro­posed the mem­ris­tor did not reject the dis­cov­ery but instead changed his mind about what a mem­ris­tor is. We briefly intro­duce the his­tory and then care­fully mem­ris­tance and the mem­ris­tor as such. We dis­cuss its sta­tus as a model rather than a device. We dis­cuss the dis­cov­ered devices, their sta­bil­ity, and how sta­bil­ity relates to the con­sis­tency of the the­o­ret­i­cal enti­ties. A thought exper­i­ment assumes a world with­out mag­net­ism. Induc­tors can­not exist there, but mem­ory resis­tors could still be con­structed. On the same grounds as the mem­ris­tor was his­tor­i­cally pre­dicted, an “induc­tor” could then be pre­dicted. Likely, some­body would also ‘dis­cover’ one. A ten­ta­tive soci­o­log­i­cal analy­sis com­pares to the flawed detec­tion of grav­i­ta­tional waves but comes to very dif­fer­ent conclusions.”

    symmetry-​​is-​​the-​​way-​​things-​​ought-​​to-​​be history-​​of-​​science technical-​​assumptions engineering-​​philosophy

  • [1205.2776] Trans­port on cou­pled spa­tial networks

    “Trans­port processes on spa­tial net­works are rep­re­sen­ta­tive of a broad class of real world sys­tems which, rather than being inde­pen­dent, are typ­i­cally inter­de­pen­dent. We pro­pose a mea­sure of util­ity to cap­ture key fea­tures that arise when such sys­tems are cou­pled together. The cou­pling is defined in a way that is not solely topo­log­i­cal, rely­ing on both the dis­tri­b­u­tion of sources and sinks, and the method of route assign­ment. Using a toy model, we explore rel­e­vant cases by sim­u­la­tion. For cer­tain para­me­ter val­ues, a pic­ture emerges of two regimes. The first occurs when the flows go from many sources to a small num­ber of sinks. In this case, net­work util­ity is largest when the cou­pling is at its max­i­mum and the aver­age short­est path is min­i­mized. The sec­ond regime arises when many sources cor­re­spond to many sinks. Here, the opti­mal cou­pling no longer cor­re­sponds to the min­i­mum aver­age short­est path, as the con­ges­tion of traf­fic must also be taken into account. More gen­er­ally, results indi­cate that cou­pled spa­tial sys­tems can give rise to behav­ior that relies sub­tly on the inter­play between the cou­pling and ran­dom­ness in the source-​​sink distribution.”

    nudge-​​targets network-​​theory emergent-​​design epi­demi­ol­ogy sim­u­la­tion

  • [1206.5849] Under­stand­ing the com­plex­ity of the L’evy-walk nature of human mobil­ity with a multi-​​scale cost/​benefit model

    “Prob­a­bil­ity dis­tri­b­u­tions of human dis­place­ments has been fit with expo­nen­tially trun­cated L’evy flights or fat tailed Pareto inverse power law prob­a­bil­ity dis­tri­b­u­tions. Thus, peo­ple usu­ally stay within a given loca­tion (for exam­ple, the city of res­i­dence), but with a non-​​vanishing fre­quency they visit nearby or far loca­tions too. Herein, we show that an impor­tant empir­i­cal dis­tri­b­u­tion of human dis­place­ments (range: from 1 to 1000 km) can be well fit by three con­sec­u­tive Pareto dis­tri­b­u­tions with sim­ple inte­ger expo­nents equal to 1, 2 and ($gtrap­prox$) 3. These three expo­nents cor­re­spond to three dis­place­ment range zones of about 1 km $less­sim Delta r less­sim$ 10 km, 10 km $less­sim Delta r less­sim$ 300 km and 300 km $less­sim Delta r less­sim $ 1000 km, respec­tively. These three zones can be geo­graph­i­cally and phys­i­cally well deter­mined as dis­place­ments within a city, vis­its to nearby cities that may occur within just one-​​day trips, and visit to far loca­tions that may require multi-​​days trips. The incre­men­tal inte­ger val­ues of the three expo­nents can be eas­ily explained with a three-​​scale mobil­ity cost/​benefit model for human dis­place­ments based on sim­ple geo­met­ri­cal con­strains. Essen­tially, peo­ple would divide the space into three major regions (close, medium and far dis­tances) and would assume that the travel ben­e­fits are randomly/​uniformly dis­trib­uted mostly only within spe­cific urban-​​like areas.”

    Levy-​​flights city-​​planning multiscale-​​phenomena self-​​similarity

  • [1206.7011] Ultra­thin Ter­a­hertz Pla­nar Lenses

    “Con­ven­tional opti­cal com­po­nents shape the wave­front of prop­a­gat­ing light by adjust­ing the opti­cal path length, which requires the use of rather thick lenses, espe­cially for the adjust­ment of ter­a­hertz (THz) radi­a­tion due to its long wave­length. Two ultra­thin THz pla­nar lenses were designed and fab­ri­cated based on inter­face phase mod­u­la­tion of antenna res­o­nance. The lens thick­nesses were extremely reduced to 100 nm, which is only 1⁄4000th of the illu­mi­nat­ing light wave­length. The focus­ing and imag­ing func­tions of the lenses were exper­i­men­tally demon­strated. The ultra­thin opti­cal com­po­nents described herein are a sig­nif­i­cant step toward the devel­op­ment of a micro-​​integrated THz system.”

    optics engineering-​​design nudge-​​targets

  • [1206.3789] Tree decom­po­si­tion and para­me­ter­ized algo­rithms for RNA structure-​​sequence align­ment includ­ing ter­tiary inter­ac­tions and pseudoknots

    “We present a gen­eral set­ting for structure-​​sequence com­par­i­son in a large class of RNA struc­tures that uni­fies and gen­er­al­izes a num­ber of recent works on spe­cific fam­i­lies on struc­tures. Our approach is based on tree decom­po­si­tion of struc­tures and gives rises to a gen­eral para­me­ter­ized algo­rithm, where the expo­nen­tial part of the com­plex­ity depends on the fam­ily of struc­tures. For each of the pre­vi­ously stud­ied fam­i­lies, our algo­rithm has the same com­plex­ity as the spe­cific algo­rithm that had been given before.”

    RNA structural-​​biology fold­ing bioin­for­mat­ics algo­rithms nudge-​​targets mod­el­ing

  • [1206.3403] Topo­log­i­cal Mea­sure Locat­ing the Effec­tive Crossover between Seg­re­ga­tion and Inte­gra­tion in a Mod­u­lar Network

    “Com­pu­ta­tional analy­sis of time-​​course data with an under­ly­ing causal struc­ture is needed in a vari­ety of domains, includ­ing neural spike trains, stock price move­ments, and gene expres­sion lev­els. How­ever, it can be chal­leng­ing to deter­mine from just the numer­i­cal time course data alone what is coor­di­nat­ing the vis­i­ble processes, to sep­a­rate the under­ly­ing prima facie causes into gen­uine and spu­ri­ous causes and to do so with a fea­si­ble com­pu­ta­tional com­plex­ity. For this pur­pose, we have been devel­op­ing a novel algo­rithm based on a frame­work that com­bines notions of causal­ity in phi­los­o­phy with algo­rith­mic approaches built on model check­ing and sta­tis­ti­cal tech­niques for mul­ti­ple hypothe­ses test­ing. The causal rela­tion­ships are described in terms of tem­po­ral logic for­mu­lae, refram­ing the infer­ence prob­lem in terms of model check­ing. The logic used, PCTL, allows descrip­tion of both the time between cause and effect and the prob­a­bil­ity of this rela­tion­ship being observed. We show that equipped with these causal for­mu­lae with their asso­ci­ated prob­a­bil­i­ties we may com­pute the aver­age impact a cause makes to its effect and then dis­cover sta­tis­ti­cally sig­nif­i­cant causes through the con­cepts of mul­ti­ple hypoth­e­sis test­ing (treat­ing each causal rela­tion­ship as a hypoth­e­sis), and false dis­cov­ery con­trol. By explor­ing a well-​​chosen fam­ily of poten­tially all sig­nif­i­cant hypothe­ses with rea­son­ably min­i­mal descrip­tion length, it is pos­si­ble to tame the algorithm’s com­pu­ta­tional com­plex­ity while explor­ing the nearly com­plete search-​​space of all prima facie causes. We have tested these ideas in a num­ber of domains and illus­trate them here with two examples.”

    time-​​series sta­tis­tics frame­work dynamical-​​systems to-​​read

  • [1206.5959] The Online Replace­ment Path Problem

    “We study a nat­ural online vari­ant of the replace­ment path prob­lem. The textit{replacement path prob­lem} asks to find for a given graph $G = (V,E)$, two des­ig­nated ver­tices $s,tin V$ and a short­est $s$-$t$ path $P$ in $G$, a textit{replacement path} $P_​e$ for every edge $e$ on the path $P$. The replace­ment path $P_​e$ is sim­ply a short­est $s$-$t$ path in the graph, which avoids the textit{failed} edge $e$. We adapt this prob­lem to deal with the nat­ural sce­nario, that the edge which failed is not known at the time of solu­tion imple­men­ta­tion. Instead, our prob­lem assumes that the iden­tity of the failed edge only becomes avail­able when the rout­ing mech­a­nism tries to cross the edge. This sit­u­a­tion is moti­vated by appli­ca­tions in dis­trib­uted net­works, where infor­ma­tion about recent changes in the net­work is only stored locally, and fault-​​tolerant opti­miza­tion, where an adver­sary tries to delay the dis­cov­ery of the mate­ri­al­ized sce­nario as much as pos­si­ble. Con­se­quently, we define the textit{online replace­ment path prob­lem}, which asks to find a nom­i­nal $s$-$t$ path $Q$ and detours $Q_​e$ for every edge on the path $Q$, such that the worst-​​case arrival time at the des­ti­na­tion is min­i­mized. Our main con­tri­bu­tion is a label set­ting algo­rithm, which solves the prob­lem in undi­rected graphs in time $O(m log n)$ and lin­ear space for all sources and a sin­gle des­ti­na­tion. We also present algo­rithms for exten­sions of the model to any bounded num­ber of failed edges.”

    operations-​​research plan­ning algo­rithms online-​​algorithms nudge-​​targets

  • [1206.6195] Par­rondo games with spa­tial depen­dence, II

    “…Again this sug­gests that the Par­rondo region (mu_​B is non­pos­i­tive and mu_[r,s] is pos­i­tive) has nonzero vol­ume in the limit. …”

    Parrondo-​​games game-​​theory counterintuitive-​​results sim­u­la­tion coop­er­a­tion

  • [1206.4648] Two-​​Manifold Prob­lems with Appli­ca­tions to Non­lin­ear Sys­tem Identification

    “Recently, there has been much inter­est in spec­tral approaches to learn­ing manifolds—so-called ker­nel eigen­map meth­ods. These meth­ods have had some suc­cesses, but their applic­a­bil­ity is lim­ited because they are not robust to noise. To address this lim­i­ta­tion, we look at two-​​manifold prob­lems, in which we simul­ta­ne­ously recon­struct two related man­i­folds, each rep­re­sent­ing a dif­fer­ent view of the same data. By solv­ing these inter­con­nected learn­ing prob­lems together, two-​​manifold algo­rithms are able to suc­ceed where a non-​​integrated approach would fail: each view allows us to sup­press noise in the other, reduc­ing bias. We pro­pose a class of algo­rithms for two-​​manifold prob­lems, based on spec­tral decom­po­si­tion of cross-​​covariance oper­a­tors in Hilbert space, and dis­cuss when two-​​manifold prob­lems are use­ful. Finally, we demon­strate that solv­ing a two-​​manifold prob­lem can aid in learn­ing a non­lin­ear dynam­i­cal sys­tem from lim­ited data.”

    sta­tis­tics inverse-​​problems system-​​identification algo­rithms nudge-​​targets bench­mark­ing

  • [1203.3367] Sto­chas­tic dif­fer­en­tial equa­tions for evo­lu­tion­ary dynam­ics with demo­graphic noise and mutations

    “We present a gen­eral frame­work to describe the evo­lu­tion­ary dynam­ics of an arbi­trary num­ber of types in finite pop­u­la­tions based on sto­chas­tic dif­fer­en­tial equa­tions (SDE). For large, but finite pop­u­la­tions this allows to include demo­graphic noise with­out requir­ing explicit sim­u­la­tions. Instead, the pop­u­la­tion size only rescales the ampli­tude of the noise. More­over, this frame­work admits the inclu­sion of muta­tions between dif­fer­ent types, pro­vided that muta­tion rates, $mu$, are not too small com­pared to the inverse pop­u­la­tion size 1/​N. This ensures that all types are almost always rep­re­sented in the pop­u­la­tion and that the occa­sional extinc­tion of one type does not result in an extended absence of that type. For $mu Nll1$ this lim­its the use of SDE’s, but in this case there are well estab­lished alter­na­tive approx­i­ma­tions based on time scale sep­a­ra­tion. We illus­trate our approach by a Rock-​​Scissors-​​Paper game with muta­tions, where we demon­strate excel­lent agree­ment with sim­u­la­tion based results for suf­fi­ciently large pop­u­la­tions. In the absence of muta­tions the excel­lent agree­ment extends to small pop­u­la­tion sizes.”

    finite-​​size-​​effects population-​​biology noise-​​in-​​design nudge-​​targets

  • [1206.5352] The Sub­word Com­plex­ity of k-​​Automatic Sequences is k-​​Synchronized

    “We show that the sub­word com­plex­ity func­tion p_​x (n), which counts the num­ber of dis­tinct fac­tors of length n of a k-​​automatic sequence x, is k-​​synchronized in the sense of Carpi. As an appli­ca­tion, we gen­er­al­ize recent results of Gold­stein. In con­trast, we show that func­tion which counts the num­ber of unbor­dered fac­tors of length n is not k-​​synchronized.”

    automata strings com­plex­ity nudge-​​targets

  • Con­vex hull algo­rithms — Wikipedia, the free encyclopedia

    “Com­put­ing the con­vex hull means that a non-​​ambiguous and effi­cient rep­re­sen­ta­tion of the required con­vex shape is con­structed. The com­plex­ity of the cor­re­spond­ing algo­rithms is usu­ally esti­mated in terms of n, the num­ber of input points, and h, the num­ber of points on the con­vex hull.”

    computational-​​geometry algo­rithms nudge-​​targets

  • [1205.6363] What Should Devel­op­ers Be Aware Of? An Empir­i­cal Study on the Direc­tives of API Documentation

    “Appli­ca­tion Pro­gram­ming Inter­faces (API) are exposed to devel­op­ers in order to reuse soft­ware libraries. API direc­tives are natural-​​language state­ments in API doc­u­men­ta­tion that make devel­op­ers aware of con­straints and guide­lines related to the usage of an API. This paper presents the design and the results of an empir­i­cal study on the direc­tives of API doc­u­men­ta­tion of object-​​oriented libraries. Its main con­tri­bu­tion is to pro­pose and exten­sively dis­cuss a tax­on­omy of 23 kinds of API directives.”

    digital-​​humanities doc­u­men­ta­tion text-​​mining software-​​development cultural-​​norms

  • Pub­li­ca­tions Avail­able Electronically

    God­fried T. Tou­s­saint, “The Erdos-​​Nagy the­o­rem and its ram­i­fi­ca­tions,” Proc. 11th Cana­dian Con­fer­ence on Com­pu­ta­tional Geom­e­try, Van­cou­ver, Canada, August 16–18 1999, pp. 9–12. Long ver­sion avail­able at: http://​www​.cs​.ubc​.ca/​c​o​n​f​e​r​e​n​c​e​s​/​C​CCG. Also: Tech­ni­cal Report No. SOCS-99.2, School of Com­puter Sci­ence, McGill Uni­ver­sity, June 18, 1999.

    nudge-​​targets geom­e­try genetic-​​programming-​​target low-​​hanging-​​fruit

  • Intro­duc­tion to Lam­ina Emer­gent Mech­a­nisms (LEMS) | Com­pli­ant Mechanisms

    “The fact that LEMs can be fab­ri­cated from pla­nar lay­ers influ­ences both what processes can be used for their man­u­fac­ture and what mate­ri­als may be used in their con­struc­tion. At the micro level, LEMS can be fab­ri­cated using single-​​layer MEMS fab­ri­ca­tion meth­ods and mate­ri­als, which offers sig­nif­i­cant cost and reli­a­bil­ity advan­tages. It also pro­vides oppor­tu­ni­ties for com­plex out-​​of-​​plane motion with only a sin­gle layer. At the macro level, man­u­fac­tur­ing processes used to make sta­tic struc­tures or com­po­nents for assem­bly can be used to cre­ate mech­a­nisms capa­ble of sophis­ti­cated motions and com­plex tasks. Example processes include stamp­ing, fine blank­ing, laser cut­ting, water jet cut­ting, plasma cut­ting, and wire elec­tri­cal dis­charge machin­ing (EDM). Some of these processes, such as stamp­ing, offer sig­nif­i­cant cost advan­tages for high-​​volume pro­duc­tion. Pla­nar fab­ri­ca­tion also allows the use of sheet goods to directly cre­ate mech­a­nisms. The use of low-​​cost, high-​​quality sheet goods has the poten­tial to dra­mat­i­cally reduce cost for high-​​volume pro­duc­tion. It also makes pos­si­ble the next char­ac­ter­is­tic: flat ini­tial state.”

    man­u­fac­tur­ing engineering-​​design fab­ri­ca­tion nudge-​​targets

Items of some interest:

Posted on by

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

  • Tar­get Expres­sion Exam­ples — Eureqa Formulize

    ‘The “Tar­get Expres­sion” in the field at the top of the Set Tar­get tab tells For­mulize what type of model to search for. By default, the tar­get expres­sion is an equa­tion where y (or, if there’s no y, what­ever vari­able is in col­umn A) is mod­eled as a func­tion of all other vari­ables. To edit the tar­get expres­sion, click on it, then make the desired alter­ations. Use the spe­cial func­tion f(…) to spec­ify the part of the equa­tion that For­mulize will attempt to fill in; For­mulize will search for the for­mula f(…) using the vari­ables you put inside the parentheses.’

    for­mulize eureqa genetic-​​programming symbolic-​​regression mod­el­ing doc­u­men­ta­tion

  • A New Solu­tion to the Puz­zle of Sim­plic­ity — PhilSci-​​Archive

    “Explain­ing the con­nec­tion, if any, between sim­plic­ity and truth is among the deep­est prob­lems fac­ing the phi­los­o­phy of sci­ence, sta­tis­tics, and machine learn­ing. Say that an effi­cient truth-​​finding method min­i­mizes worst-​​case costs en route to con­verg­ing to the true answer to a the­ory choice prob­lem. Let the costs con­sid­ered include the num­ber of times a false answer is selected, the num­ber of times opin­ion is reversed, and the times at which the rever­sals occur. It is demon­strated that (1)always choos­ing the sim­plest the­ory com­pat­i­ble with expe­ri­ence and (2) hang­ing onto it while it remains sim­plest is both nec­es­sary and suf­fi­cient for efficiency.”

    via:cshalizi occam’s-razor sim­plic­ity model-​​discovery expla­na­tion philosophy-​​of-​​science

  • [1206.4599] A Uni­fied Robust Clas­si­fi­ca­tion Model

    “A wide vari­ety of machine learn­ing algo­rithms such as sup­port vec­tor machine (SVM), min­i­max prob­a­bil­ity machine (MPM), and Fisher dis­crim­i­nant analy­sis (FDA), exist for binary clas­si­fi­ca­tion. The pur­pose of this paper is to pro­vide a uni­fied clas­si­fi­ca­tion model that includes the above mod­els through a robust opti­miza­tion approach. This uni­fied model has sev­eral ben­e­fits. One is that the exten­sions and improve­ments intended for SVM become applic­a­ble to MPM and FDA, and vice versa. Another ben­e­fit is to pro­vide the­o­ret­i­cal results to above learn­ing meth­ods at once by deal­ing with the uni­fied model. We give a sta­tis­ti­cal inter­pre­ta­tion of the uni­fied clas­si­fi­ca­tion model and pro­pose a non-​​convex opti­miza­tion algo­rithm that can be applied to non-​​convex vari­ants of exist­ing learn­ing methods.”

    clas­si­fi­ca­tion algo­rithms lumpers-​​and-​​spliters-​​sittin-​​in-​​a-​​tree

  • CUDA Down­loads | NVIDIA Devel­oper Zone

    This release of the CUDA Toolkit  enables devel­op­ment using GPUs using the Kepler archi­tec­ture, such as the GeForce GTX680. Fea­ture and func­tion­al­ity builds on the foun­da­tion of the CUDA 4.1 release which intro­duced: A new  LLVM-​​based CUDA com­piler 1000+ new image pro­cess­ing func­tions Redesigned Visual Pro­filer with auto­mated per­for­mance analy­sis and inte­grated expert guidance

    CUDA GPU pro­gram­ming library MacOS

  • [1206.2057] Fin­ish­ing Flows Quickly with Pre­emp­tive Scheduling

    “Today’s data cen­ters face extreme chal­lenges in pro­vid­ing low latency. How­ever, fair shar­ing, a prin­ci­ple com­monly adopted in cur­rent con­ges­tion con­trol pro­to­cols, is far from opti­mal for sat­is­fy­ing latency require­ments. We pro­pose Pre­emp­tive Dis­trib­uted Quick (PDQ) flow sched­ul­ing, a pro­to­col designed to com­plete flows quickly and meet flow dead­lines. PDQ enables flow pre­emp­tion to approx­i­mate a range of sched­ul­ing dis­ci­plines. For exam­ple, PDQ can emu­late a short­est job first algo­rithm to give pri­or­ity to the short flows by paus­ing the con­tend­ing flows. PDQ bor­rows ideas from cen­tral­ized sched­ul­ing dis­ci­plines and imple­ments them in a fully dis­trib­uted man­ner, mak­ing it scal­able to today’s data cen­ters. Fur­ther, we develop a mul­ti­path ver­sion of PDQ to exploit path diver­sity. Through exten­sive packet-​​level and flow-​​level sim­u­la­tion, we demon­strate that PDQ sig­nif­i­cantly out­per­forms TCP, RCP and D3 in data cen­ter envi­ron­ments. We fur­ther show that PDQ is sta­ble, resilient to packet loss, and pre­serves nearly all its per­for­mance gains even given inac­cu­rate flow information.”

    queuing-​​models engineering-​​design algo­rithms performance-​​measure nudge-​​targets

  • [1206.2216] Com­plex Sys­tems Sci­ence: Dreams of Uni­ver­sal­ity, Real­ity of Interdisciplinarity

    “Using a large data­base (~ 215 000 records) of rel­e­vant arti­cles, we empir­i­cally study the “com­plex sys­tems” field and its claims to find uni­ver­sal prin­ci­ples apply­ing to sys­tems in gen­eral. The study of ref­er­ences shared by the papers allows us to obtain a global point of view on the struc­ture of this highly inter­dis­ci­pli­nary field. We show that its over­all coher­ence does not arise from a uni­ver­sal the­ory but instead from com­pu­ta­tional tech­niques and fruit­ful adap­ta­tions of the idea of self-​​organization to spe­cific sys­tems. We also find that com­mu­ni­ca­tion between dif­fer­ent dis­ci­plines goes through spe­cific “trad­ing zones”, ie sub-​​communities that cre­ate an inter­face around spe­cific tools (a DNA microchip) or con­cepts (a network).”

    via:cshalizi com­plex­ol­ogy pro­fes­sion­al­iza­tion network-​​theory disappointed-​​by-​​lack-​​of-​​Abbott-​​ref citation-​​networks

Items of some interest:

Posted on by

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

  • [0912.1523] Deco­her­ence in Search Algorithms

    “Recently sev­eral quan­tum search algo­rithms based on quan­tum walks were pro­posed. Those algo­rithms dif­fer from Grover’s algo­rithm in many aspects. The goal is to find a marked ver­tex in a graph faster than clas­si­cal algo­rithms. Since the imple­men­ta­tion of those new algo­rithms in quan­tum com­put­ers or in other quan­tum devices is error-​​prone, it is impor­tant to ana­lyze their robust­ness under deco­her­ence. In this work we ana­lyze the impact of deco­her­ence on quan­tum search algo­rithms imple­mented on two-​​dimensional grids and on hypercubes.”

    quan­tums search-​​algorithms robust­ness nudge-​​targets

  • The Man­i­fest Des­tiny of Arti­fi­cial Intel­li­gence » Amer­i­can Scientist

    “Arti­fi­cial intel­li­gence began with an ambi­tious research agenda: To endow machines with some of the traits we value most highly in ourselves—the fac­ulty of rea­son, skill in solv­ing prob­lems, cre­ativ­ity, the capac­ity to learn from expe­ri­ence. Early results were promis­ing. Com­put­ers were pro­grammed to play check­ers and chess, to prove the­o­rems in geom­e­try, to solve anal­ogy puz­zles from IQ tests, to rec­og­nize let­ters of the alpha­bet. Mar­vin Min­sky, one of the pio­neers, declared in 1961: “We are on the thresh­old of an era that will be strongly influ­enced, and quite pos­si­bly dom­i­nated, by intel­li­gent problem-​​solving machines.””

    artificial-​​intelligence nudge-​​book cultural-​​assumptions degenerate-​​research-​​programmes

  • About « Digress​.it

    “Digress​.it is a Word­Press plu­gin that offers paragraph-​​level com­ment­ing in the mar­gins of a text. Digress​.it is geared toward in-​​depth dis­cus­sions of longer doc­u­ments: arti­cle, essay or even book-​​length.

    Blogs aren’t bad for hav­ing con­ver­sa­tions, but com­ments tend to get unwieldy, and can feel detached when the orig­i­nal post is long. To solve this, Digress​.it lets you run blog-​​style com­ment threads — digres­sions, if you will — off of indi­vid­ual para­graphs. To do this effi­ciently, we’ve re-​​imagined the con­ven­tional post-​​discussion hier­ar­chy of blogs, mov­ing the com­ment area from beneath the post to beside it (float­ing to the right) — hear­ken­ing back to the age-​​old prac­tice of scrib­bling in page mar­gins. We see great pos­si­bil­i­ties for edu­ca­tors, lit­er­ary groups, polit­i­cal or civic activists, legal schol­ars, and pretty much any­one who wants to do a com­mu­nal read­ing and encour­age discussion.”

    blog­ging social-​​media con­ver­sa­tion pub­lish­ing word­press

  • [1205.3676] Con­sen­sus of Multi-​​Agent Net­works in the Pres­ence of Adver­saries Using Only Local Information

    “This paper addresses the prob­lem of resilient con­sen­sus in the pres­ence of mis­be­hav­ing nodes. Although it is typ­i­cal to assume knowl­edge of at least some non­lo­cal infor­ma­tion when study­ing secure and fault-​​tolerant con­sen­sus algo­rithms, this assump­tion is not suit­able for large-​​scale dynamic net­works. To rem­edy this, we empha­size the use of local strate­gies to deal with resilience to secu­rity breaches. We study a con­sen­sus pro­to­col that uses only local infor­ma­tion and we con­sider worst-​​case secu­rity breaches, where the com­pro­mised nodes have full knowl­edge of the net­work and the inten­tions of the other nodes. We pro­vide nec­es­sary and suf­fi­cient con­di­tions for the nor­mal nodes to reach con­sen­sus despite the influ­ence of the mali­cious nodes under dif­fer­ent threat assump­tions. These con­di­tions are stated in terms of a novel graph-​​theoretic prop­erty referred to as net­work robustness.”

    agent-​​based game-​​theory network-​​theory social-​​dynamics nudge-​​targets algo­rithms

  • [1205.2604] The Infi­nite Latent Events Model

    “We present the Infi­nite Latent Events Model, a non­para­met­ric hier­ar­chi­cal Bayesian dis­tri­b­u­tion over infi­nite dimen­sional Dynamic Bayesian Net­works with binary state rep­re­sen­ta­tions and noisy-​​OR-​​like tran­si­tions. The dis­tri­b­u­tion can be used to learn struc­ture in dis­crete time­series data by simul­ta­ne­ously infer­ring a set of latent events, which events fired at each timestep, and how those events are causally linked. We illus­trate the model on a sound fac­tor­iza­tion task, a net­work topol­ogy iden­ti­fi­ca­tion task, and a video game task.”

    seems-​​familiar-​​somehow

  • Space­Funcs­Doc — OpenOpt

    “The fol­low­ing geom­e­try objects are imple­mented for now in Space­Funcs mod­ule:
    Point, Line, Line­Seg­ment, Cir­cle, Plane, Tri­an­gle, Poly­gon, Sphere, Poly­tope, Poly­he­dron, Tetra­he­dron. Some more are intended to be done in next Space­Funcs release.”

    geom­e­try nudge-​​targets numerical-​​methods libraries

  • GitHub does dot­files — dot​files​.github​.com

    “Why would I want my dot­files on GitHub?”

    system-​​administration Unix GitHub hints tuto­r­ial

  • [1205.4591] ForeCA: Fore­castable Com­po­nent Analysis

    “Blind source sep­a­ra­tion (BSS) tech­niques are often applied to mul­ti­vari­ate time series with the goal to obtain bet­ter fore­casts. But BSS and the need for bet­ter fore­casts are often treated sep­a­rately, in the sense that find­ing an opti­mally trans­formed (sub-)space has noth­ing to do with the aim to pre­dict well. Here I intro­duce Fore­castable Com­po­nent Analy­sis (ForeCA), a new BSS tech­nique for tem­po­rally depen­dent sig­nals that uses fore­casta­bil­ity as the explicit objec­tive in find­ing an opti­mal trans­for­ma­tion. It sep­a­rates the sig­nal into the fore­castable, $mathbf{F}$, and the orthog­o­nal white noise space, $mathbf{F}^{bot}$. Sim­u­la­tions and appli­ca­tions to finan­cial data show that ForeCA suc­cess­fully finds sig­nals that can be used to fore­cast. ForeCA there­fore auto­mat­i­cally dis­cov­ers infor­ma­tive struc­ture in mul­ti­vari­ate sig­nals. The R pack­age (this http URL) will be pub­licly avail­able on CRAN upon pub­li­ca­tion of the manuscript.”

    sta­tis­tics algo­rithms component-​​analysis pre­dic­tion

  • [1201.5597] The mate-​​in-​​n prob­lem of infi­nite chess is decidable

    “…The proof pro­ceeds by show­ing that the mate-​​in-​​n prob­lem is express­ible in what we call the first-​​order struc­ture of chess, which we prove (in the rel­e­vant frag­ment) is an auto­matic struc­ture, whose the­ory is there­fore decid­able. Indeed, it is defin­able in Pres­burger arith­metic. Unfor­tu­nately, this res­o­lu­tion of the mate-​​in-​​n prob­lem does not appear to set­tle the decid­abil­ity of the more gen­eral winning-​​position prob­lem, the prob­lem of deter­min­ing whether a des­ig­nated player has a win­ning strat­egy from a given posi­tion, since a posi­tion may admit a win­ning strat­egy with­out any bound on the num­ber of moves required. This issue is con­nected with trans­fi­nite game val­ues in infi­nite chess, and the exact value of the omega one of chess is not known.”

    mathematical-​​recreations game-​​theory proof­ing games unde­cid­abil­ity

  • [1203.5351] Activ­ity dri­ven mod­el­ing of dynamic networks

    “Net­work mod­el­ing plays a crit­i­cal role in iden­ti­fy­ing sta­tis­ti­cal reg­u­lar­i­ties and struc­tural prin­ci­ples com­mon to many sys­tems. The large major­ity of recent mod­el­ing approaches are con­nec­tiv­ity dri­ven. The struc­tural pat­terns of the net­work are at the basis of the mech­a­nisms rul­ing the net­work for­ma­tion. Con­nec­tiv­ity dri­ven mod­els nec­es­sar­ily pro­vide a time-​​aggregated rep­re­sen­ta­tion that may fail to describe the instan­ta­neous and fluc­tu­at­ing dynam­ics of many net­works. We address this chal­lenge by defin­ing the activ­ity poten­tial, a time invari­ant func­tion char­ac­ter­iz­ing the agents’ inter­ac­tions and con­struct­ing an activ­ity dri­ven model capa­ble of encod­ing the instan­ta­neous time descrip­tion of the net­work dynam­ics. The model pro­vides an expla­na­tion of struc­tural fea­tures such as the pres­ence of hubs, which sim­ply orig­i­nate from the het­ero­ge­neous activ­ity of agents. Within this frame­work, highly dynam­i­cal net­works can be described ana­lyt­i­cally, allow­ing a quan­ti­ta­tive dis­cus­sion of the biases induced by the time-​​aggregated rep­re­sen­ta­tions in the analy­sis of dynam­i­cal processes.”

    network-​​theory infer­ence sta­tis­tics com­plex­ol­ogy

Items of some interest:

Posted on by

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

Items of some interest:

Posted on by

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

  • Jonathan Lethem’s ‘Neote­nous Aes­thetic” — Mis­ter Bit — Wired​.it

    ‘Dur­ing the brief, but very inter­est­ing Q&A ses­sion, Lethem argued that inter­net cul­ture brought the “closet into the open”, that is, it gave ephemera, triv­i­al­i­ties, and every­day activ­i­ties “A new kind of vis­i­bil­ity”. “Peo­ple have always been pro­duc­ing weird stuff and have always been engag­ing in arcane activ­i­ties,” Lethem remarked. “What is really new is the fact the now we can see it. We can see it all. We can quan­tify what we do — or not do — online.” Lethem men­tioned the uncanny abil­ity to track, in real time, “how many books I am not sell­ing on Ama­zon”. “Real­ity has acquired a new level of mea­sur­a­bil­ity”. “The activ­i­ties we per­form in our dig­i­tal age are not nec­es­sar­ily new. What is new is that. We. Can. See. Them. All.”.’

    one-​​measures-​​a-​​circle inter­per­me­ation access local­ism

  • Sex, Oil, and Video­tape | Mother Jones

    “Loom­ing over Saylor’s con­fronta­tion with Bolen­baugh was the EPA’s Sep­tem­ber 27 cleanup dead­line, and it appears that Enbridge and its con­trac­tors were feel­ing the pres­sure as it drew near. In early Sep­tem­ber, after the Michi­gan Mes­sen­ger pub­lished its exposé on the use of undoc­u­mented work­ers by Hall­mark Indus­trial, another group of work­ers employed by a dif­fer­ent Enbridge con­trac­tor came for­ward with detailed sto­ries of how they had been instructed to con­ceal oil at the same site. Work­ers would land on an island, they said, remove all veg­e­ta­tion, and then lay out absorbent pom-​​poms, all per EPA reg­u­la­tions. But once the top layer of oil was absorbed, they were instructed to rake dirt over the area to make it appear as though it had been dug out. One worker described his super­vi­sor show­ing him the process step-​​by-​​step, con­clud­ing with sprin­kling a thin layer of dirt on top. “He said, ‘There, now they can’t see it. It is clean,’” the worker told the Mes­sen­ger. Another worker described being told to cover pock­ets of oil with leaves and sticks. As a last step, such areas were cor­doned off with cau­tion tape.”

    oil­spill Kala­ma­zoo local whistle­blower

  • [1204.4200] Dis­crete Dynam­i­cal Genetic Pro­gram­ming in XCS

    “A num­ber of rep­re­sen­ta­tion schemes have been pre­sented for use within Learn­ing Clas­si­fier Sys­tems, rang­ing from binary encod­ings to neural net­works. This paper presents results from an inves­ti­ga­tion into using a dis­crete dynam­i­cal sys­tem rep­re­sen­ta­tion within the XCS Learn­ing Clas­si­fier Sys­tem. In par­tic­u­lar, asyn­chro­nous ran­dom Boolean net­works are used to rep­re­sent the tra­di­tional condition-​​action pro­duc­tion sys­tem rules. It is shown pos­si­ble to use self-​​adaptive, open-​​ended evo­lu­tion to design an ensem­ble of such dis­crete dynam­i­cal sys­tems within XCS to solve a num­ber of well-​​known test problems.”

    genetic-​​programming learning-​​classifier-​​systems representation-​​theory design-​​patterns boolean-​​networks nudge-​​targets nice

  • Why Is Darwin’s Tan­gled Bank Tan­gled? : 13.7: Cos­mos And Cul­ture : NPR

    Sad to hear him still phras­ing this sim­ple truth so obscurely: Not “Because, on the scale of mol­e­c­u­lar bind­ing site recog­ni­tion, say a few tens of angstroms in length, height and width and sev­eral other fea­tures such as polar­ity, van-​​der-​​Waal forces, and so on, there are far fewer effec­tively dif­fer­ent mol­e­c­u­lar shapes than there are kinds of mol­e­cules.“ … but “Because there are fewer sto­ries than there are facts.”

    oh-​​stu pragmatism-it-ain’t philosophy-​​of-​​science

  • Math Notes | Futil­ity Closet

    So for finite sequences of dig­its, which sequences are such that the most right-​​truncated sub­strings are prime? Which are such that the most right-​​repeating exten­sions are prime?

    nudge-​​targets number-​​theory indirect-​​link

  • Home — Scal­able and Mod­u­lar Archi­tec­ture for CSS

    “I’ve been ana­lyz­ing my process (and the process of those around me) and fig­ur­ing out how best to struc­ture code for projects on a larger scale. What I’ve found is a process that works equally well for sites small and large. Learn how to struc­ture your CSS to allow for flex­i­bil­ity and main­tain­abil­ity as your project and your team grows.”

    css tuto­r­ial best-​​practices graphic-​​design via-​​trek

  • [1204.3678] Crowd Mem­ory: Learn­ing in the Collective

    “Crowd algo­rithms often assume work­ers are inex­pe­ri­enced and thus fail to adapt as work­ers in the crowd learn a task. These assump­tions fun­da­men­tally limit the types of tasks that sys­tems based on such algo­rithms can han­dle. This paper explores how the crowd learns and remem­bers over time in the con­text of human com­pu­ta­tion, and how more real­is­tic assump­tions of worker expe­ri­ence may be used when design­ing new sys­tems. We first demon­strate that the crowd can recall infor­ma­tion over time and dis­cuss pos­si­ble impli­ca­tions of crowd mem­ory in the design of crowd algo­rithms. We then explore crowd learn­ing dur­ing a con­tin­u­ous con­trol task. Recent sys­tems are able to dis­guise dynamic groups of work­ers as crowd agents to sup­port con­tin­u­ous tasks, but have not yet con­sid­ered how such agents are able to learn over time. We show, using a real-​​time gam­ing set­ting, that crowd agents can learn over time, and ‘remem­ber’ by pass­ing strate­gies from one gen­er­a­tion of work­ers to the next, despite high turnover rates in the work­ers com­pris­ing them. We con­clude with a dis­cus­sion of future research direc­tions for crowd mem­ory and learning.”

    crowd­sourc­ing learn­ing agent-​​based collective-​​intelligence mem­ory nudge-​​targets

  • [0911.1582] Manip­u­lat­ing Tour­na­ments in Cup and Round Robin Competitions

    “In sports com­pe­ti­tions, teams can manip­u­late the result by, for instance, throw­ing games. We show that we can decide how to manip­u­late round robin and cup com­pe­ti­tions, two of the most pop­u­lar types of sport­ing com­pe­ti­tions in poly­no­mial time. In addi­tion, we show that find­ing the min­i­mal num­ber of games that need to be thrown to manip­u­late the result can also be deter­mined in poly­no­mial time. Finally, we show that there are sev­eral dif­fer­ent vari­a­tions of stan­dard cup com­pe­ti­tions where manip­u­la­tion remains polynomial.”

    algo­rithms eco­nom­ics game-​​theory nudge-​​targets

  • Intro­duc­ing the Jour­nal of Dig­i­tal Human­i­ties — ProfHacker — The Chron­i­cle of Higher Education

    “If the con­tents of the inau­gural issue—which range from an essay argu­ing that human­ists need to under­stand and inter­pret quan­ti­ta­tive data to a review of the Word­Seer text analy­sis tool—fall out­side your usual schol­arly domain, then cer­tainly the journal’s edi­to­r­ial and pub­lish­ing appa­ra­tus will piqué your interest. As Dan Cohen explained in a sep­a­rate blog post, the jour­nal oper­ates under the model of catch­ing the good—of find­ing sub­stan­tive and valu­able dig­i­tal human­i­ties work “in what­ever for­mat, and wher­ever, it exists.” Blogs, pod­casts, Twit­ter con­ver­sa­tions, slideshows, and so on, these are all venues in which sig­nif­i­cant and, though I hate to use such an ungainly word, impact­ful work is being done. The reg­u­lar and guest edi­tors “catch” this work, and then pro­vide lay­ers of eval­u­a­tion and review before it appears in JDH.”

    digital-​​humanities jour­nal to-​​read two-​​cultures-​​only-​​one-​​of-​​which-​​can-​​write

  • [1005.4159] The Com­plex­ity of Manip­u­lat­ing $k$-Approval Elections

    “An impor­tant prob­lem in com­pu­ta­tional social choice the­ory is the com­plex­ity of unde­sir­able behav­ior among agents, such as con­trol, manip­u­la­tion, and bribery in elec­tion sys­tems. These kinds of vot­ing strate­gies are often tempt­ing at the indi­vid­ual level but dis­as­trous for the agents as a whole. Cre­at­ing elec­tion sys­tems where the deter­mi­na­tion of such strate­gies is dif­fi­cult is thus an impor­tant goal. …”

    vot­ing game-​​theory design-​​patterns mechanism-​​design nudge-​​targets

  • [0903.1147] Tetravex is NP-​​complete

    “Tetravex is a widely played one per­son com­puter game in which you are given $n^2$ unit tiles, each edge of which is labelled with a num­ber. The objec­tive is to place each tile within a $n$ by $n$ square such that all neigh­bour­ing edges are labelled with an iden­ti­cal num­ber. Unfor­tu­nately, play­ing Tetravex is com­pu­ta­tion­ally hard. More pre­cisely, we prove that decid­ing if there is a tiling of the Tetravex board is NP-​​complete. Decid­ing where to place the tiles is there­fore NP-​​hard. This may help to explain why Tetravex is a good puz­zle. This result com­pli­ments a num­ber of sim­i­lar results for one per­son games involv­ing tiling. For exam­ple, NP-​​completeness results have been shown for: the offline ver­sion of Tetris, KPlumber (which involves rotat­ing tiles con­tain­ing draw­ings of pipes to make a con­nected net­work), and short­est slid­ing puz­zle prob­lems. It raises a num­ber of open ques­tions. For exam­ple, is the infi­nite ver­sion Turing-​​complete? How do we gen­er­ate Tetravex prob­lems which are truly puz­zling as ran­dom NP-​​complete prob­lems are often sur­pris­ing easy to solve? Can we observe phase tran­si­tion behav­iour? What about the com­plex­ity of the prob­lem when it is guar­an­teed to have an unique solu­tion? How do we gen­er­ate puz­zles with unique solutions?”

    mathematical-​​recreations computational-​​complexity algo­rithms nudge-​​targets

  • [1204.4286] Fair Allo­ca­tion With­out Trade

    “We con­sider the age-​​old prob­lem of allo­cat­ing items among dif­fer­ent agents in a way that is effi­cient and fair. Two papers, by Dolev et al. and Ghodsi et al., have recently stud­ied this prob­lem in the con­text of com­puter sys­tems. Both papers had sim­i­lar mod­els for agent pref­er­ences, but advo­cated dif­fer­ent notions of fair­ness. We for­mal­ize both fair­ness notions in eco­nomic terms, extend­ing them to apply to a larger fam­ily of util­i­ties. Not­ing that in set­tings with such util­i­ties effi­ciency is eas­ily achieved in mul­ti­ple ways, we study notions of fair­ness as cri­te­ria for choos­ing between dif­fer­ent effi­cient allo­ca­tions. Our tech­ni­cal results are algo­rithms for find­ing fair allo­ca­tions cor­re­spond­ing to two fair­ness notions: Regard­ing the notion sug­gested by Ghodsi et al., we present a polynomial-​​time algo­rithm that com­putes an allo­ca­tion for a gen­eral class of fair­ness notions, in which their notion is included. For the other, sug­gested by Dolev et al., we show that a com­pet­i­tive mar­ket equi­lib­rium achieves the desired notion of fair­ness, thereby obtain­ing a polynomial-​​time algo­rithm that com­putes such a fair allo­ca­tion and solv­ing the main open prob­lem raised by Dolev et al.”

    eco­nom­ics game-​​theory fair­ness algo­rithms phi­los­o­phy design-​​patterns

  • Why is Esti­mat­ing so Hard? | 8th Light

    “It turns out that we don’t know the pro­ce­dure. We haven’t got any clue to just how dif­fi­cult the pro­ce­dure is. We aren’t com­put­ers. We don’t fol­low pro­ce­dures. And so com­par­ing the com­plex­ity of the man­ual task, to the com­plex­ity of the pro­ce­dure is invalid. This is one of the rea­sons that esti­mates are so hard, and why we get them wrong so often. We look at a task that seems easy and esti­mate it on that basis, only to find that writ­ing down the pro­ce­dure is actu­ally quite intri­cate. We blow the esti­mate because we esti­mate the wrong thing.”

    esti­ma­tion agile-​​practices philosophy-​​of-​​engineering man­age­ment self-​​definition plan­ning

  • [1204.4374] Higher Order City Voronoi Diagrams

    “We inves­ti­gate higher-​​order Voronoi dia­grams in the city met­ric. This met­ric is induced by quick­est paths in the L1 met­ric in the pres­ence of an accel­er­at­ing trans­porta­tion net­work of axis-​​parallel line segments. …”

    computational-​​geometry algo­rithms voronoi-​​diagrams diver­sity network-​​theory nudge-​​targets

  • Topic mod­el­ing made just sim­ple enough. | The Stone and the Shell

    “Com­puter sci­en­tists make LDA seem com­pli­cated because they care about prov­ing that their algo­rithms work. And the proof is indeed brain-​​squashingly hard. But the prac­tice of topic mod­el­ing makes good sense on its own, with­out proof, and does not require you to spend even a sec­ond think­ing about “Dirich­let dis­tri­b­u­tions.” When the math is approached in a prac­ti­cal way, I think human­ists will find it easy, intu­itive, and empow­er­ing. This post focuses on LDA as short­hand for a broader fam­ily of “prob­a­bilis­tic” tech­niques. I’m going to ask how they work, what they’re for, and what their lim­its are.”

    text-​​processing clas­si­fi­ca­tion algo­rithms lovely two-​​cultures-​​only-​​one-​​of-​​which-​​can-​​write

  • Math­e­mati­cians are Giraffe Hunters by Barry Mazur | berfrois

    “No won­der life (i.e., the thing that my once 10-​​year old niece referred to as “the thing that isn’t fair”) comes to us as a fil­i­gree of ash sto­ries. Walk­ing down the street past a cou­ple in con­ver­sa­tion, an over­heard mor­pheme, a mere glance at a wrongly but­toned rain­coat, sparks a nar­ra­tive in our imag­i­na­tion. Ask any ques­tion begin­ning with “why?” and the answer will surely be a story, or it will be embed­ded in a story. Or, at the very least, it will offer a tempt­ing thread for some story that you your­self will hold onto, embell­ish even, as you try to absorb the answer. We inter­po­late between such frag­ments. This is, for many of us, sim­ply the way we think. What about the “why ques­tions” in sci­ence, in logic, in math­e­mat­ics? We should acknowl­edge how they are often “what ques­tions” or “how ques­tions” in dis­guise. Or how they slide down into such ques­tions, as the ever-​​elusive, ever-​​illusory quest for an X that actu­ally causes a Y dis­solves. Some of the more sat­is­fy­ing answers to sci­en­tific “why” ques­tions involves deft rephras­ing. “Why is the sky blue?” is replaced by the ques­tion “what is the func­tion that describes scat­ter­ing ampli­tude as depen­dent on wave-​​length”?”

    math­e­mat­ics philosophy-​​of-​​mathematics sto­ry­telling prag­ma­tism theory-​​and-​​practice-​​sitting-​​in-​​a-​​tree what-​​is-​​it-​​good-​​for-​​hunh