Bibliography:

Some introductory (and brief) reviews relevant to the proposal
M. Mezard, Passing Messages between disciplines, Science 301, 685 (2003)
C.P. Gomes and B. Selman, Computer Science: Satisfied with Physics, Science 297, 784 (2002)
A.G. Percus, G. Istrate, C. Moore, Where statistical physics meets computation, in: Computational Complexity and Statistical Physics (Oxford University Press, New York, 2006), pp. 3-24.

General (Algorithms, Physics & related)
H.A. Bethe, Proc.Roy.Soc.London A, 150, 552 (1935)
H. A. Kramers, G. H. Wannier, Statistics of the Two-Dimensional Ferromagnet. Part II, Phys. Rev. 60, 263–276 (1941)
C.E. Shannon, Bell. Syst. Tech.J. 27, 379 (1948); 27, 623 (1948)
N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, Equations of state calculations by fast computing machines, Journal of Chemical Physics 21, 1087 (1953)
S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Science 220, 671 (1983)
W.J.Cook, W.H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley & Sons; 1 edition (November 12, 1997)
C.H. Papadimitriou & K. Steiglitz, Combinatorial Optimization : Algorithms and Complexity, Dover Pubns; (paperback, Unabridged edition, July 1998).
T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, (MIT York 1998)
A.K. Hartmann, H. Rieger, Optimization Algorithms in Physics, Wiley-VCH, 2002
D. MacKay, Information Theory, Inference, and Learning Algorithms (Cambridge 2003)
M. Mezard, A. Montanari, Frustrated Systems in Physics and Computation, (Oxford Press 2006)
J.S. Yedidia, W.T. Freeman, Y. Weiss, Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms, TR-2004-040

Algorithms for Wireless Sensor Networks
D. Son, B. Krishnamachari, J. Heidemann, Experimental Analysis of Concurrent Packet Transmissions in Low-Power Wireless Networks , USC-ISI Technical Report ISI-TR-2005-609, November 2005.
K. Whitehouse, A. Woo, F. Jiang, J. Polastre, D. Culler, Exploiting the capture effect for collision detection and recovery, Embedded Networked Sensors '02, Sydney, May 30-31, 2005.
X.-Y. Li, P.-J. Wan, O. Frieder, Coverage Problems in Wireless Ad-hoc Sensor Networks , IEEE Transactions for Computers 52 , 753 (2003).
B. Krishnamachari, D. Estrin, S. Wicker, The impact of Data Aggregation in wireless Sensor Networks , International Workshop on Distributed Event-Based Systems '02, Vienna, July 2002.
Z. Xiong, A.D. Liveris, and S. Cheng, IEEE Signal Processing Magazine, Sep. 2004, p.80.
National Research Council, Computer Science and Telecommunications Board. Embedded, Everywhere: A Research Agenda for Networked Systems of Embedded Computers , (National Academy Press, Washington, DC, 2001).
J. Stankovic, Research Challenges for Wireless Sensor Networks, ACM SIGBED Review, July 2004.
K. Akkaya, M. Younis, Ad Hoc Networks 3 , 325 (2005).
W. Ye, J. Heidemann, D. Estrin, Medium access control with coordinated adaptive sleeping for wireless sensor networks, IEEE/ACM Transactions on Networking 12 , 493 (2004).
S. Sichalou, L. Georgiadis, Computer Networks 43 , 351 (2003)

Community Detection
M. Girvan and M. E. J. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)
M. E. J. Newman, Fast algorithm for detecting community structure in networks , Phys. Rev. E 69, 066133 (2004)
M.E.J. Newman, Detecting community structure in networks, Eur.Phys. J. B 38 , 321 (2004)
M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004)
A. Clauset, M. E. J. Newman and C. Moore, Finding community structure in very large networks, Phys. Rev. E 70, 066111 (2004)
E. Ziv, M. Middendorf, C. Wiggins, Inferring Network Mechanisms: The Drosophila melanogaster Protein Interaction Network, PRE in press
G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society , Nature 435 , 814 (2005).

Graph Coloring & Satisfiability
M. Mezard, G. Parisi, M.A. Virasoro, Spin Glass theory and beyond, World Scientific, 1987
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Determining Computational Complexity from Characteristic 'Phase Transitions' , Nature 400, 133 (1999)
O.C. Martin, R. Monasson, and R. Zecchina, Statistical Mechanics Methods and Phase Transitions in Optimization Problems, Theoretical Computer Science 265, 3 (2001)
M. Mezard, G. Parisi, R. Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems, Science 297, 812 (2002)
A. K. Hartmann and H. Rieger, Optimization Algorithms in Physics, (Wiley-VCH, Berlin, 2002)
S. Cocco, R. Monasson, A. Montanari, G. Semerjian, Analyzing search algorithms with physical methods, Chapter in Computational Complexity and Statistical Physics, edited by A.G. Percus, G. Istrate, C. Moore (Oxford University Press, New York, 2006), pp. 63-105.
E. Clarke, A. Biere, R. Raimi, Y. Zhu, Bounded Model Checking Using Satisfiability Solving , Formal Methods in System Design 19 , 7 (2001).

Multi-Objective Shortest Path
A. Warburton, Approximation of Pareto Optima in Milti-Objective, Shortest-Path Problems , Operations Research 35 , 70 (1987).
C. ReVelle, J. Cohon, D. Shobrys, Simultaneous siting and routing in the disposal of hazardous wastes , Transportation Science 25 , 138 (1991).
D.H. Lorenz, D. Raz, A simple efficient approximation scheme for the restricted shortest path problem , Operations Research Letters 28 , 213 (2001).

Distributed Coding & Data Reconstruction
R.G. Gallager, Low density parity check codes (MIT PressCambridhe, MA, 1963); Information Theory and Reliable Communication (Wiley, New York, 1968)
A. Viterbi, Error bounds for convolutional codes and an asymptotically optimum decoding algorithm , IEEE Trans. Inf. Theory 13, 260 (1967)
C. Berrou, A. Glavieux, and P. Thitimajshima, in Proceedings of the 1993 International Conference Comm. (IEE, Piscataway, NJ, 1993), pp.1064-1070.
D.J.C. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inf. Theory 45, (2) 399-431 (1999)
J. Pearl, Probabilistic reasoning in intelligent systems: network of plausible inference (Kaufmann, San Francisco, 1988)
T.J. Richardson, R.L.Urbanke, The capacity of low-density parity-check codes under message-passing decoding, IEEE Trans. Inf. Theory 47 (2) 599-618 (2001)
A. Montanari, The glassy phase of Gallaher codes, Eur. Phys. J. B 23, 121-136 (2001)
C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, R.L. Urbanke. Finite-Length Analysis of Low-Density Parity-Check Codes on the binary Erasure Channel , IEEE Information Theory 48, 1570 (2002)
S. Franz, M. Leone, A. Montanari, F. Ricci-Tersenghi, Dynamics phase transition for decoding algorithms , Phys. Rev. E 66, 046120 (2002)
M. A. Neifeld, Y. Wu, Parallel image restoration with a two-dimensional likelihood-based algorithm, Applied Optics 41, 4812 (2002)
M. Marrow, J. K. Wolf, Iterative Detection of 2-Dimensional ISI Channels, ITW2003, Paris (p.p. 131-134)
O. Shental, A.J. Weiss, N. Shental, Y. Weiss, Generalized Belief Propagation Receiver for Near-Optimal Detection of Two-Dimensional Channels with Memory, preprint 2004
R. Koetter, P.O. Vontobel, Graph-covers and iterative decoding of finite length codes, Proc. 3rd International Symposium on Turbo Codes & Related Topics, Brest, France, p. 75-82, Sept. 1-5, 2003
M. Mezard, S. Ciliberti, R. Zecchina, Source coding with low density nonlinear nodes , preprint 2005.
D. Slepian, J.K. Wolf, Noiseless coding of correlated information sources, IEEE IT 19 , 471 (1973).
R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, Network Information Flow , IEEE IT 46, 1204 (2000).
Y. Wu, J.A. O'Sullivan, N.~Singla, R.S. Indeck, Iterative detection and decoding for separable two-dimensional intersymbol interference, IEEE Trans. on Magnetics 36 , 2176 (2003).
S. Halevy, et. al, Improved Bit-Stuffing Bounds on Two-Dimensional Constraints, IEEE IT 50 , 824 (2004).

Our books, patent & publications relevant to the project:
BOOKs:
E. Ben-Naim, H. Frauenfelder, Z. Toroczkai, eds., Complex Networks, Lecture Notes in Physics 650 (Springer, Berlin, 2004).
A.G. Percus, G. Istrate, C. Moore, eds., Computational Complexity and Statistical Physics (Oxford University Press, New York, 2006).
PATENT:
M. Chertkov and I. Gabitov U.S. Patent 6701050, issued March 2, 2004: Methods and Optical Fibers that decrease pulse degradation resulting from random chromatic dispersion
PUBLICATIONS:
F. J. Alexander, A. L. Garcia, and D. M. Tartakovsky, Noise in Algorithm Refinement Methods, Computing in Science and Engineering to appear (2006).
F. J. Alexander, G. L. Eyink, and J. M. Restrepo, Accelerated Monte-Carlo for Optimal Estimation of Time Series, Journal of Statistical Physics, 2006 (to appear).
F. J. Alexander, B. M. Boghosian, R. C. Brower and S. R. Kimura, Fourier acceleration of Langevin molecular dynamics, Phys. Rev. E, (art. no. 066704) (2001).
F. J. Alexander and G. L. Eyink, Shape Dependent Thermodynamics and Non-Local Hydrodynamics in a Non-Gibbsian Steady-State of a Drift-Diffusion System, Phys. Rev. E 57, R6229 (1998).
F. J. Alexander and G. L. Eyink, Rayleigh-Ritz calculation of effective potential far from equilibrium, Phys. Rev. Lett. 78 , 1 (1997).
D. Achlioptas, A. Chtcherba, G. Istrate and C. Moore, The phase transition in NAE 3-SAT and 1-in-k SAT, In Proceedings of the 13'th ACM-SIAM Symposium on Discrete Algorithms (SODA'01).
D. Aldous and A.G. Percus, Scaling and universality in continuous length combinatorial optimization, Proceedings of the National Academy of Sciences 100, 11211-11215 (2003).
E. Ben-Naim, P.L. Krapivsky, and S.N Majumdar, Extremal Properties of Random Trees Phys. Rev. E 64, R035101 (2001).
E. Ben-Naim, P.L. Krapivsky, and S. Redner, Extremal Properties of Random Structures Lecture Notes in Physics 650, 211 (2004).
E. Ben-Naim and P.L. Krapivsky, Kinetic Theory of Random Graphs: from Paths to Cycles, Phys. Rev. E, in press (2005).
E. Ben-Naim and P.L. Krapivsky, Kinetic Theory of Random Graphs AIP Proceedings, in press (2005).
S. Boettcher and A.G. Percus, Optimization with extremal dynamics, Physical Review Letters 86, 5211 (2001).
S. Boettcher and A.G. Percus, Extremal optimization for graph partitioning, Physical Review E 64, 026114 (2001).
S. Boettcher and A.G. Percus, Nature's way of optimizing, Artificial Intelligence 119, 275 (2000)
S. Boettcher and A.G. Percus, Extremal optimization at the phase transition of the 3-coloring problem, Physical Review E 69, 066703 (2004).
D. Bokolamulla, A. Hansson, and T. Aulin, Low-complexity iterative detection based on limited bi-directional trellis search, accepted to IEE Proceedings - Communications, Jan. 2006.
V. Chernyak, M. Chertkov, I. Kolokolov, V. Lebedev, Probability of anomalously large Bit-Error-Rate in long haul optical transmission , Phys. Rev. E 68 , 066619 (2003).
V. Chernyak, M. Chertkov, I. Kolokolov, V. Lebedev, Extreme Outages due to Polarization Mode Dispersion , Optics. Lett. 28 , 2159 (2003).
V. Chernyak, M. Chertkov, I. Kolokolov, V. Lebedev, Compensation for Extreme Outages caused by Polarization Mode Dispersion and Amplifier noise, Optics. Express. 11 , 1607 (2003).
V. Chernyak, M. Chertkov, I. Kolokolov, V. Lebedev, Periodic and Quasi-Periodic Compensation Strategies of Extreme Outages caused by Polarization Mode Dispersion and Amplifier Noise , JETP Lett. 78, 198-201 (2003).
V. Chernyak, M. Chertkov, I. Gabitov, I. Kolokolov, V. Lebedev, PMD induced fluctuations of Bit-Error-Rate in optical fiber systems, Journal of Lightware Technology 22, 1155 (2004).
V. Chernyak, M. Chertkov, I. Kolokolov, A. Peleg, Outage probability for soliton transmission , Euro.Phys.Lett 66, 499 (2004).
V. Chernyak, M. Chertkov, M. Stepanov, B. Vasic, Error correction on a tree: An instanton approach, Phys.Rev.Lett. 93 , 198702-1 (2004).
A.I.Chernykh, M.G.Stepanov, Large negative velocity gradients in Burgers turbulence , Phys. Rev. E 64 026306 (2001).
M. Chertkov, Instanton for random advection , Phys. Rev. E 55 , 2722 (1997).
M. Chertkov, I. Gabitov, J. Moeser, Pulse confinement in optical fibers with random dispersion, Proceedings of National Academy of Science USA 98, 14208 (2001).
M. Chertkov, I. Gabitov, I.Kolokolov, V. Lebedev, Shedding and Interaction of Solitons in Imperfect Medium , Pis'ma v ZhETF 74, 391 (2001) [JETP Letters 74, 357 (2001)].
M. Chertkov, I. Gabitov, I.Kolokolov, V. Lebedev, Solitons in Optical Medium with Disorder and Anisotropy, Pis'ma v ZhETF 74, 608 (2001).
M. Chertkov, I. Gabitov, P. Lushnikov, J. Moeser, Z. Toroczkai Pinning method of pulse confinement in optical fiber with random dispersion, JOSA B 19, 2538 (2002).
M. Chertkov, Y. Chung, A. Dyachenko, I. Gabitov, I. Kolokolov, and V. Lebedev, Shedding and interaction of solitons in weakly disordered optical fibers, Phys.Rev.E. 67, 036615 (2003).
M. Chertkov, I. Gabitov, I. Kolokolov and T. Schafer Passive Compensation of Polarization Mode Dispersion via Periodic Control of Birefringent Disorder, JOSA B 21, 486 (2004).
M.Chertkov, V.Y. Chernyak, Loop Calculus in Statistical Physics and Information Science, submitted to Phys.Rev.E., cond-mat/0601487
M.Chertkov, V.Y. Chernyak, Loop series for discrete statistical models on graphs, submitted to JSTAT, cond-mat/0603189
M.Chertkov, M. Stepanov, Looping Linear Programming Decoding of LDPC codes, submitted to IEEE Transactions on Information Theory, cs.IT/0601113
G. L. Eyink, J. M. Restrepo and F. J. Alexander, A Statistical-Mechanical Approach to Data Assimilation for Nonlinear Dynamics: II. Evolution Approximations, submitted to Journal of Statistical Physics, (2005).
G. L. Eyink, J. M. Restrepo and F. J. Alexander, A Mean-field approximation in data assimilation for nonlinear dynamics, Physica D (to appear).
A. Hansson and T. Aulin, On antenna array receiver principles for space-time-selective Rayleigh fading channels, IEEE Transactions on Communications, 48, 648 (2000).
A. Hansson, K.M. Chugg, T. Aulin, On forward-adaptive versus forward/backward-adaptive SISO algorithms for Rayleigh fading channels, IEEE Communications Letters 5, 477 (2001).
A. Hansson and T. Aulin, Iterative diversity detection for correlated continuous-time Rayleigh fading channels, IEEE Transactions on Communications, 51, 240 (2003).
A. Hansson and T. Aulin, Generalized APP Detection of Continuous Phase Modulation over Unknown ISI Channels, IEEE Transactions on Communications, 53, 1615 (2005).
M. B. Hastings, T. C. Halsey, High-dimensional diffusive growth Europhysics Letters 55 679 (2001).
M. B. Hastings, Mean-Field and Anomalous Behavior on a Small-World Network, Phys. Rev. Lett. 91, 098701 (2003).
M. B. Hastings, Random Vibrational Networks and Renormalization Group, Phys. Rev. Lett. 90 , 148702 (2003).
M. B. Hastings, Community Detection as an Inference Problem, cond-mat/0604429
G. Istrate, Computational complexity and phase transitions, Proceedings of the Annual IEEE Conference on Computational Complexity, 104 (2000).
G. Istrate, Marathe M.V., S.S. Ravi, Adversarial models in evolutionary game dynamics, SIAM PROCEEDINGS SERIES, 719 (2001).
G. Istrate, The phase transition in random Horn satisfiability and its algorithmic implications, Random Structures & Algorithms 20 483 (2002).
G. Istrate, S. Boettcher, A.G. Percus, Spines of random constraint satisfaction problems: definition and connection with computational complexity, Annals of Mathematics and Artificial Intelligence 44, 353-372 (2005).
G. Istrate, A complete classification of theshold properties of of boolean random constraint satisfaction problems, to appear in Discrete Applied Mathematics, special issue on Typical Complexity and Phase Transitions, E. Kranakis and L. Kiroussis (editors).
G. Istrate, On the satisfiability of random k-Horn formulae, in "Graphs, Morphisms and Statistical Physics", P. Winkler and J. Nesetril (editors), pp. 113-136, AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 2004.
V. Krishnamurthy, M. Faloutsos, M. Chrobak, L. Lao, J.-H. Cui and A.G. Percus, Reducing large internet topologies for faster simulations, Proceedings of the 4th International IFIP-TC6 Networking Conference (NETWORKING 2005). Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2005), Vol. 3462, pp. 328-341.
A.Peleg, M. Chertkov, I. Gabitov Inelastic collisions of pulses in optical fibers, JOSA B 21, 18 (2004).
A. Peleg, M. Chertkov, I. Gabitov Inter-channel interaction of optical solitons, Phys. Rev. E 68, 026605 (2003).
M.G. Stepanov, V. Chernyak, M. Chertkov, B. Vasic, Diagnosis of weaknesses in error correction: a physics approach , Phys. Rev. Lett. 95, 228701 (2005), extended version is available at cond-mat/0506037
M.G. Stepanov and M. Chertkov, The error-floor of LDPC codes in the Laplacian channel, Proceedings of 43rd Allerton Conference (September 28-30, 2005, Allerton, IL), cs.IT/0507031
M.G. Stepanov and M. Chertkov, Instanton analysis of Low-Density-Parity-Check codes in the error-floor regime, cs.IT/0601070
D. Volk, M.G. Stepanov, Resampling methods for document clustering, cond-mat/0109006