links for 2010-​​06-​​23

links for 2010-​​06-​​20

links for 2010-​​06-​​19

links for 2010-​​06-​​16

  • “Evo­lu­tion­ary adap­ta­tion is the process that increases the fit of a pop­u­la­tion to the fit­ness land­scape it inhab­its. As a con­se­quence, evo­lu­tion­ary dynam­ics is shaped, con­strained, and chan­neled, by that fit­ness land­scape. Much work has been expended to under­stand the evo­lu­tion­ary dynam­ics of adapt­ing pop­u­la­tions, but much less is known about the struc­ture of the land­scapes. Here, we study the global and local struc­ture of com­plex fit­ness land­scapes of inter­act­ing loci that describe pro­tein folds or sets of inter­act­ing genes form­ing path­ways or mod­ules. We find that in these land­scapes, high peaks are more likely to be found near other high peaks, cor­rob­o­rat­ing Kauffman’s “Mas­sif Cen­tral” hypoth­e­sis. We study the clus­ters of peaks as a func­tion of the rugged­ness of the land­scape and find that this clus­ter­ing allows peaks to form inter­con­nected networks.…”
  • “The feed-​​forward rela­tion­ship nat­u­rally observed in time-​​dependent processes and in a diverse num­ber of real sys­tems –such as some food-​​webs and elec­tronic and neural wiring– can be described in terms of so-​​called directed acyclic graphs (DAGs). An impor­tant ingre­di­ent of the analy­sis of such net­works is a proper com­par­i­son of their observed archi­tec­ture against an ensem­ble of ran­dom­ized graphs, thereby quan­ti­fy­ing the {\em ran­dom­ness} of the real sys­tems with respect to suit­able null mod­els. This approx­i­ma­tion is par­tic­u­larly rel­e­vant when the finite size and/​or large con­nec­tiv­ity of real sys­tems make inad­e­quate a com­par­i­son with the pre­dic­tions obtained from the so-​​called {\em con­fig­u­ra­tion model}. In this paper we ana­lyze four meth­ods of DAG ran­dom­iza­tion as defined by the desired com­bi­na­tion of topo­log­i­cal invari­ants (directed and undi­rected degree sequence and com­po­nent dis­tri­b­u­tions) aimed to be preserved.…”
  • “In this paper, we con­sider the prob­lem of block­ing mali­cious traf­fic on the Inter­net, via source-​​based fil­ter­ing. In par­tic­u­lar, we con­sider fil­ter­ing via access con­trol lists (ACLs): these are already avail­able at the routers today but are a scarce resource because they are stored in the expen­sive ternary con­tent address­able mem­ory (TCAM). Aggre­ga­tion (by fil­ter­ing source pre­fixes instead of indi­vid­ual IP addresses) helps reduce the num­ber of fil­ters, but comes also at the cost of block­ing legit­i­mate traf­fic orig­i­nat­ing from the fil­tered pre­fixes. We show how to opti­mally choose which source pre­fixes to fil­ter, for a vari­ety of real­is­tic attack sce­nar­ios and oper­a­tors’ poli­cies. In each sce­nario, we design opti­mal, yet com­pu­ta­tion­ally effi­cient, algo­rithms. Using logs from Dshield​.org, we eval­u­ate the algo­rithms and demon­strate that they bring sig­nif­i­cant ben­e­fit in practice.”
  • “We give an algo­rithm that com­putes the final state of cer­tain growth mod­els with­out com­put­ing all inter­me­di­ate states. Our tech­nique is based on a “least action prin­ci­ple” which char­ac­ter­izes the odome­ter func­tion of the growth process. Start­ing from an edu­cated guess for the odome­ter, we suc­ces­sively cor­rect under– and over­es­ti­mates and prov­ably arrive at the cor­rect final state. The degree of speedup depends on the accu­racy of the ini­tial guess.
    Deter­min­ing the size of the bound­ary fluc­tu­a­tions in inter­nal diffusion-​​limited aggre­ga­tion is a long-​​standing open prob­lem in sta­tis­ti­cal physics. As an appli­ca­tion of our method, we cal­cu­late the size of fluc­tu­a­tions over two orders of mag­ni­tude beyond pre­vi­ous sim­u­la­tions. Our data strongly sup­port the con­jec­ture that the fluc­tu­a­tions are log­a­rith­mic in the radius.”

links for 2010-​​06-​​13

  • “A new algo­rithm for recon­struct­ing a two dimen­sional object from a set of one dimen­sional pro­jected views is pre­sented that is both com­pu­ta­tion­ally exact and exper­i­men­tally prac­ti­cal. The algo­rithm has a com­pu­ta­tional com­plex­ity of O(n log2 n) with n = N^2 for an NxN image, is robust in the pres­ence of noise and pro­duces no arte­facts in the recon­struc­tion process, as is the case with con­ven­tional tomo­graphic meth­ods. The recon­struc­tion process is approx­i­ma­tion free because the object is assumed to be dis­crete and uti­lizes fully dis­crete Radon trans­forms. Noise in the pro­jec­tion data can be sup­pressed fur­ther by intro­duc­ing redun­dancy in the recon­struc­tion. The num­ber of pro­jec­tions required for exact recon­struc­tion and the response to noise can be con­trolled with­out com­pris­ing the dig­i­tal nature of the algorithm.…”
  • “This paper presents the design and analy­sis of par­al­lel approx­i­ma­tion algo­rithms for facility-​​location prob­lems, includ­ing $\NC$ and $\RNC$ algo­rithms for (met­ric) facil­ity loca­tion, $k$-center, $k$-median, and $k$-means. These prob­lems have received con­sid­er­able atten­tion dur­ing the past decades from the approx­i­ma­tion algo­rithms com­mu­nity, con­cen­trat­ing pri­mar­ily on improv­ing the approx­i­ma­tion guar­an­tees. In this paper, we ask, is it pos­si­ble to par­al­lelize some of the beau­ti­ful results from the sequen­tial setting?”