M.K. Homepage > Written > English

Surveys

• Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey
• Authors: M.K., Frédéric Magniez and Miklos Santha.
• Abstract
• Theoretical Aspects of Computer Science, Teheran, Iran, Springer-Verlag, LNCS 2292, 30-83, 2002.
• Preliminary version in E-CCC Technical Report number TR01-014, 2001.

Thesis

• Probabilistically Checkable Proofs and the Testing of Hadamard-like Codes
• Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, February 1996.
• Abstract
• Contents:
• Part I : Abstract, credits, acknowledgments, table of contents, introduction and chapter 1 (Linearity Testing)
• Part II : chapter 2 (Testing and the Theory of Weight Distribution of codes).
• Part III : chapter 3 (Alternation in Interaction), bibliography, appendix (Tightness of the Linearity Test Lower Bound (GF(2) case)).

Papers

• Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs
• Authors: M.K. and Martin Loebl
• Electronic Journal of Combinatorics 15(1):R135, 2008
• Adversarial Queuing Theory with Setups
• Authors: M.K., Mauricio Soto, and Christopher Thraves
• To appear in Theoretical Computer Science A, 2008
• On-Line Approximate String Matching with Bounded Errors
• Authors: M.K., Gonzalo Navarro, and Claudio Telha
• Preliminary version in Proceedings of the 19th Annual Symposium onn Computational Pattern Matching - CPM. Springer-Verlag, LNCS 5029, 130-142, 2008
• Strong Accumulators from Collision-Resistant Hashing
• Authors: Philippe Camacho, Alejandro Hevia, M.K., Roberto Opazo
• Preliminary version in Proceedings of the 11th International Conference in Information Security - ISC, Springer-Verlag. LNCS 5222, 471-486, 2008.
• A Concentration Bound for the Longest Increasing Subsequence of a Randomly Chosen Involution
• Authors: M.K.
• Discrete Applied Mathematics 154(13):1816-1823, 2006.
• Expected Length of the Longest Common Subsequence for Large Alphabets
• Authors: M.K., Martin Loebl and Jiri Matousek
• Abstract
• Advances in Mathematics, 197(2):480-498, 2005.
• Preliminary version in Proc. of the 6th Latin American Symposium on Theoretical Informatics - LATIN. Springer-Verlag, LNCS 2976, 302-311, April 2004. (For a version with proofs see ArXiv Technical Report math.CO/0308234, August 2003.)
• The Chilean Highway Problem
• Authors: M.K. and Alexander Russell
• Abstract
• Theoretical Computer Sciencie A, 326:329--342, 2004.
• Electronic Jury Voting Protocols
• Authors: M.K. and Alejandro Hevia.
• Abstract
• Theoretical Computer Science A, 321(1):73-94, 2004.
• Preliminary version in Proc. of the 5th Latin American Symposium on Theoretical Informatics - LATIN. Springer-Verlag, LNCS 2286, 415-429, 2002.
• Largest Planar Matching in Random Bipartite Graphs
• Authors: M.K. and Martin Loebl
• Abstract
• Random Structures and Algoritms 21(2):162--181, 2002..
  
• Preliminary version in KAM preprint series, Technical Report number 2000-482, July 2000.
• Approximate Error Relative to Input Size
• Authors: M.K., Frédéric Magniez and Miklos Santha .
• Abstract
• Journal of Computer and System Sciences, 66(2):371-392, 2003.
  
• Preliminary version in Proc. of the 31st ACM Symposium on Theory of Computing, 51-60, May 1999.
• Threshold Data Structures and Coding Theory
• Authors: Eric Bach and M.K.
• Abstract
• Theoretical Computer Science (Special issue in Honor of Manuel Blum's 60th Birthday) 235(1):3-23, 2000.
• Min-Max-Boundary Domain Decomposition
• Authors: M.K., Dan Spielman and Shang-Hua Teng .
• Abstract
• Theoretical Computer Science (Special issue Annual International Computing and Combinatorics Conference, COCOON'98) 261(2):253-266, 2001.
• Preliminary version in Proc. of the 4th Annual International Computing and Combinatorics Conference - COCOON, Springer-Verlag, LNCS 1449, 137-146, 1998.
• Strength of Two Data Encryption Standard Implementations under Timing Attacks
• Authors: Alejandro Hevia and M.K.,
• Abstract
• ACM Transactions on Information and System Security 2(4):416-437, 1999.
• Preliminary version in Proc. of the 3rd Latin American Symposium on Theoretical Informatics - LATIN, Springer-Verlag, LNCS 1380, 192-205, April 1998.
• Algebraic Testing and Weight Distribution of Dual Codes
• Author: M.K.
• Abstract
• Theoretical Computer Science, 299(1--3):81--106, 2003.
• Preliminary version in E-CCC Technical Report number TR97-010, 1997.
• Linearity Testing in Characteristic Two
• Authors: Mihir Bellare, Don Copperstmith, Johan Håstad, M.K. and Madhu Sudan .
• Abstract
• IEEE Transactions on Information Theory (Special Issue on Codes and Complexity), Part I, 42(6):1781-1795, 1997.
• Preliminary version in Proc. of the 36th IEEE Symposium on Foundations of Computer Science, 432-441, 1995.
• No Polynomial Bound for the Period of the Parallel Chip Firing Game on Graphs
• Authors: M.K., Ndoundam, M. Tchuente and Eric Goles.
• Theoretical Computer Science, 136(2):527-532, 1994.
• Alternation in Interaction
• Authors: M.K., Carsten Lund, Alexander Russell, Dan Spielman and Ravi Sundaram.
• Abstract
• Computational Complexity, 9(3-4):202-246, 2000.
• Preliminary version in Proc. of the 9th Annual Conference on Structure in Complexity Theory, 294-303, 1994.
• A Lower Bound on the Computational Complexity of the QR Decomposition on a Shared Memory SIMD computer
• Authors: Eric Goles and M.K.
• Parallel Computing, 18(3):345-354, 1992.
• One-dimensional Sand Piles, Cellular Automata and Related Models
• Authors: Eric Goles and M.K.
• Theoretical Computer Science 136(2):527-532, 1994