M.K. Homepage > Written > English
Surveys
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
- The Chilean Highway Problem
- 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
- 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
To M.K.'s Homepage