Maleq Khan

Publications

Please send mail if you'd like a copy of any of these. For ease of reference, papers are classified into categories depending on theory as well as applications.

Ph.D. Thesis

M. Khan. Distributed Approximation Algorithms for Minimum Spanning Trees and Other Related Problems with Applications to Wireless Ad hoc Networks, Ph.D. Thesis, Dept. of Computer Science, Purdue University, 2007. pdf

Jen-Yeu Chen. Distributed Randomized Algorithms for Robust Aggregate Computation in Wireless Sensor Networks, Ph.D. Thesis, School of Electrical and Computer Engineering, Purdue University, 2007. pdf

Probabilistic Analysis and Randomized Algorithms

G. Pandurangan and S. Jagannathan. A Simple Churn-Tolerant Structured Peer-to-Peer Scheme, submitted. pdf.

F. Xiong, G. Pandurangan, and C. Bailey-Kellogg. Contact Replacement for NMR Resonance Assignment, Bioinformatics , to appear. Conference version in The 16th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB), 2008.

G. Pandurangan and G. Park. Analysis of Randomized Protocols for Conflict-Free Distributed Access, Algorithmica, vol. 49, Number 2 / October, 2007. full text at journal website, pdf. Preliminary version in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2005.

M. Khan, G. Pandurangan, and V.S.A. Kumar. Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, to appear. pdf

T. Czajka and G. Pandurangan. Improved Random Graph Isomorphism, Journal of Discrete Algorithms, vol. 6, 85-92, 2008. pdf

G. Pandurangan and W. Szpankowski. A Universal Online Caching Algorithm based on Pattern Matching, Algorithmica, to appear. pdf. Preliminary version in Proceedings of the IEEE International Symposium on Information Theory (ISIT) 2005.

M. Khan, G. Pandurangan, and V.S.A. Kumar. A Simple Randomized Scheme for Constructing Low-Weight K-Connected Spanning Subgraphs with Applications to Distributed Algorithms, Theoretical Computer Science, vol. 385(1-3), 101-114, 2007. journal link pdf

G. Pandurangan. On a Simple Randomized Algorithm for Finding a 2-Factor in Sparse Graphs, Information Processing Letters, Volume 95, Issue 1 , 2005, 321-327. pdf

J. Chen, G. Pandurangan, and D. Xu. Robust Aggregates Computation in Wireless Sensor Networks: Distributed Randomized Algorithms and Analysis, to appear in IEEE Transactions on Parallel and Distributed Systems. pdf. Preliminary version in Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN), 2005.

S. Muthukrishnan and G. Pandurangan. The Bin-Covering Technique for Thresholding Random Geometric Graph Properties, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2005. (also as DIMACS Technical Report 2003-39, Nov. 2003) pdf

H. Kamichetty, C. Bailey-Kellogg, and G. Pandurangan. An Efficient Randomized Algorithm for Contact-Based NMR Backbone Resonance Assignment, Bioinformatics, 22(2), 2006, 172-180. abstract , pdf

G. Pandurangan and E. Upfal. Entropy-based Bounds for Online Algorithms, to appear in ACM Transactions on Algorithms. pdf Preliminary versions at the 38th Annual Conference on Information Sciences and Systems(CISS), Princeton University, NJ and in 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001.

G. Pandurangan, P. Raghavan, and E. Upfal. Building Low-Diameter Peer-to-Peer Networks, IEEE Journal on Selected Areas in Communications (JSAC), 21(6), Aug. 2003, 995-1002. postscript, pdf. Preliminary version in Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 2001.

G. Pandurangan and E. Upfal. Static and Dynamic Evaluation of QoS Properties, Journal of Interconnection Networks Vol. 1, No. 2 (2000), pp. 135-150. postscript, pdf. Preliminary version in Proceedings of the 31st ACM Symposium on Theory of Computing (STOC), 1999.

Distributed Computing and Algorithms

Y. Choi, M. Khan, V.S.A. Kumar, and G. Pandurangan. Energy-Efficient Distributed MST Construction: Tight Bounds and Algorithms, submitted. pdf.

M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar. Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings, in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 2008.

G. Pandurangan and M. Khan. Theory of Communication Networks, Algorithms and Theory of Computation Handbook, Second Edition, M.J. Atallah and M. Blanton (Editors), CRC Press, to appear. draft version.

V. Denchev and G. Pandurangan. Distributed Quantum Computing: A New Frontier in Distributed Systems or Science Fiction?, ACM SIGACT News, to appear. pdf

Y. Choi, M. Khan, V.S.A. Kumar, and G. Pandurangan. Energy-Optimal Distributed Algorithms for Minimum Spanning Trees, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008.

M. Khan and G. Pandurangan. A Fast Distributed Approximation Algorithm for Minimum Spanning Trees, Distributed Computing, vol. 20, 2008, 391-402, Invited paper. Journal link. pdf. Preliminary version in 20th International Symposium on Distributed Computing (DISC), 2006.

G. Pandurangan and S. Jagannathan. A Simple Churn-Tolerant Structured Peer-to-Peer Scheme, submitted. pdf.

J. Chen, G. Pandurangan, and D. Xu. Robust Aggregates Computation in Wireless Sensor Networks: Distributed Randomized Algorithms and Analysis, in IEEE Transactions on Parallel and Distributed Systems, 17(9), 2006. pdf. Preliminary version in Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN), 2005.

Real-World Networks, Peer-to-Peer (P2P) Networks, Ad hoc Wireless and Sensor Networks

Y. Choi, M. Khan, V.S.A. Kumar, and G. Pandurangan. Energy-Efficient Distributed MST Construction: Tight Bounds and Algorithms, submitted. pdf.

Y. Choi, M. Khan, V.S.A. Kumar, and G. Pandurangan. Energy-Optimal Distributed Algorithms for Minimum Spanning Trees, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008.

A. Ferrante, G. Pandurangan, and K. Park. On the Hardness of Optimization in Power-Law Graphs, Theoretical Computer Science, vol. 393, 2008, 220-230. pdf. Preliminary version in the 13th Annual International Computing and Combinatorics Conference (COCOON), 2007.

P. Drineas, A. Javed, M. Ismail, G. Pandurangan, R. Virrankoski, and A. Savvides. Distance Matrix Reconstruction from Incomplete Information for Sensor Network Localization, Third Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (SECON) , 2006. pdf

S. Jagannathan, G. Pandurangan, and S. Srinivasan. Query Protocols for Highly Resilient Peer-to-Peer Networks, 19th International Conference on Parallel and Distributed Computing Systems, 2006. pdf

M. Fouad, S. Fahmy, and G. Pandurangan. Latency-Sensitive Power Control for Wireless Ad Hoc Networks, in Proceedings of the 1st ACM International Workshop on QoS and Security for Wireless and Mobile Networks, 2005. pdf

M. Khan, G. Pandurangan, and B.Bhargava. Energy-Efficient Routing Schemes for Wireless Sensor Networks, Technical Report CSD TR 03-013, Dept. of Computer Science, Purdue University, 2003.

G. Pandurangan. Random Graphs in Peer-to-Peer Networks, 2nd Bertinoro Workshop on Random(ized) Graphs and Algorithms , Bertinoro, Italy, 2003; and 9th Seminar on the Analysis of Algorithms , San Miniato-Pisa, Italy, 2003. postscript, pdf

G. Pandurangan, P. Raghavan, and E. Upfal. Using PageRank to Characterize Web Structure, Internet Mathematics , 3(1), 2006, 1-20. postscript, pdf. Preliminary version in Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON), Singapore, LNCS 2387, Springer-Verlag , 330-339, 2002.

T. Dean, J. Hasic, T. Hoffman, G. Pandurangan, P. Raghavan, and E. Upfal. Dynamics, Information, and the Web Environment, DARPA Task Proceedings, Sante Fe, NM, April 2001.

G. Pandurangan. Protocols for Building Low-Diameter P2P Networks, in DIMACS Workshop on Internet and WWW Measurement, Mapping and Modeling, Rutgers University, NJ, 2002.

G. Pandurangan, P. Raghavan, and E. Upfal. Building P2P Networks with Good Topological Properties, manuscript, 2001. postscript, pdf

Computational Biology and Bioinformatics

H. Kamichetty, C. Bailey-Kellogg, and G. Pandurangan. An Efficient Randomized Algorithm for Contact-Based NMR Backbone Resonance Assignment, Bioinformatics, 22(2), 2006, 172-180. abstract , pdf

G. Pandurangan. A Random Graph Approach to Protein Structure Determination, DIMACS Workshop on Biomolecular Networks, DIMACS Center, Rutgers University, 2005.

C. Bailey-Kellog, S. Chainraj, and G. Pandurangan. A Random Graph Approach to NMR Sequential Assignment, Journal of Computational Biology, Vol. 12, No.6-7, 2005, 569-583. pdf. Preliminary version in 8th Annual International Conference on Research in Computational Biology (RECOMB), 2004.

G. Pandurangan and H. Ramesh. The Restriction Mapping Problem Revisited, Journal of Computer and System Sciences (special issue on Computational Biology), 65, 2002, 526-544 (invited paper). postscript, pdf

Dynamic Computer Processes

G. Pandurangan and S. Jagannathan. A Simple Churn-Tolerant Structured Peer-to-Peer Scheme, submitted. pdf.

G. Pandurangan. Stochastic Analyses of Dynamic Computer Processes, Ph.D. Dissertation, Brown University, May 2002.

M. Hauskrecht, G.Pandurangan, and E.Upfal. Computing Near-Optimal Strategies for Stochastic Investment Planning Problems, in Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI) 1999. postscript, pdf