Mauricio Karchmer

According to our database, Mauricio Karchmer authored at least 17 papers between 1986 and 1995.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

1995

Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity.

Mauricio Karchmer, Ran Raz, Avi Wigderson

Comput. Complex., 1995

1994

Non-Deterministic Communication Complexity with Few Witnesses.

Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson

J. Comput. Syst. Sci., 1994

On Ultrafilters and NP.

Shai Ben-David, Mauricio Karchmer, Eyal Kushilevitz

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Combinatorial characterization of read-once formulae.

Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson

Discret. Math., 1993

Characterizing non-deterministic circuit size.

Mauricio Karchmer, Avi Wigderson

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On Span Programs.

Mauricio Karchmer, Avi Wigderson

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

On Proving Lower Bounds for Circuit Size.

Mauricio Karchmer

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Non-deterministic Communication Complexity with Few Witness.

Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

Fractional Covers and Communication Complexity.

Mauricio Karchmer, Eyal Kushilevitz, Noam Nisan

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity.

Mauricio Karchmer, Ran Raz, Avi Wigderson

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Linear Circuits over GF(2).

Noga Alon, Mauricio Karchmer, Avi Wigderson

SIAM J. Comput., 1990

1989

Bounds on Universal Sequences.

Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman

SIAM J. Comput., 1989

Communication complexity - a new approach to circuit depth.

Mauricio Karchmer

MIT Press, ISBN: 978-0-262-11143-0, 1989

1988

The complexity of computation & restricted machines (מרכבות חשובים ומכונות מגבלות.).

Mauricio Karchmer

PhD thesis, 1988

A Fast Parallel Algorithm to Color a Graph with Delta Colors.

Mauricio Karchmer, Joseph Naor

J. Algorithms, 1988

Monotone Circuits for Connectivity Require Super-logarithmic Depth

Mauricio Karchmer, Avi Wigderson

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1986

Two Time-Space Tradeoffs for Element Distinctness.

Mauricio Karchmer

Theor. Comput. Sci., 1986