Avi Wigderson

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

A Direct Product Theorem.

[BibT_eX]

[DOI]

Russell Impagliazzo

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

1993

On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity.

[BibT_eX]

[DOI]

Rafi Heiman

Ilan Newman

Theor. Comput. Sci., 1993

Rounds in Communication Complexity Revisited.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom.

[BibT_eX]

[DOI]

Alexander A. Razborov

Inf. Process. Lett., 1993

Universal Traversal Sequences for Expander Graphs.

[BibT_eX]

[DOI]

Shlomo Hoory

Inf. Process. Lett., 1993

Combinatorial characterization of read-once formulae.

[BibT_eX]

[DOI]

Discret. Math., 1993

Constructing Small Sets that are Uniform in Arithmetic Progressions.

[BibT_eX]

[DOI]

Alexander A. Razborov

Endre Szemerédi

Comb. Probab. Comput., 1993

BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.

[BibT_eX]

[DOI]

Comput. Complex., 1993

Characterizing non-deterministic circuit size.

[BibT_eX]

[DOI]

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

One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge.

[BibT_eX]

[DOI]

Rafail Ostrovsky

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Deterministic Approximate Counting of Depth-2 Circuits.

[BibT_eX]

[DOI]

Michael Luby

Boban Velickovic

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

On Span Programs.

[BibT_eX]

[DOI]

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

1992

Monotone Circuits for Matching Require Linear Depth.

[BibT_eX]

[DOI]

J. ACM, 1992

Geometric medians.

[BibT_eX]

[DOI]

Joseph Gil

William L. Steiger

Discret. Math., 1992

The Complexity of Graph Connectivity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Quadratic Dynamical Systems (Preliminary Version)

[BibT_eX]

[DOI]

Yuri Rabinovich

Alistair Sinclair

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Undirected Connectivity in O(log ^1.5 n) Space

[BibT_eX]

[DOI]

Endre Szemerédi

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Non-deterministic Communication Complexity with Few Witness.

[BibT_eX]

[DOI]

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

1991

Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems.

[BibT_eX]

[DOI]

J. ACM, 1991

Linear-Size Constant-Depth Polylog-Treshold Circuits.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1991

Randomized VS. Deterministic Decision Tree Complexity for Read-Once Boolean Functions.

[BibT_eX]

[DOI]

Rafi Heiman

Comput. Complex., 1991

A Lower Bound on the Area of Permutation Layouts.

[BibT_eX]

[DOI]

Algorithmica, 1991

Self-Testing/Correcting for Polynomials and for Approximate Functions

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

An Analysis of a Simple Genetic Algorithm.

[BibT_eX]

Yuri Rabinovich

Proceedings of the 4th International Conference on Genetic Algorithms, 1991

Search Problems in the Decision Tree Model (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

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

[BibT_eX]

[DOI]

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

Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions.

[BibT_eX]

[DOI]

Rafi Heiman

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

1990

Monotone Circuits for Connectivity Require Super-Logarithmic Depth.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1990

Toward Understanding Exclusive Read.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

Linear Circuits over GF(2).

[BibT_eX]

[DOI]

Noga Alon

SIAM J. Comput., 1990

Not All Keys Can Be Hashed in Constant Time (Preliminary Version)

[BibT_eX]

[DOI]

Joseph Gil

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On the Power of Randomization in Online Algorithms (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Composition of the Universal Relation.

[BibT_eX]

[DOI]

Johan Håstad

Proceedings of the Advances In Computational Complexity Theory, 1990

Perfect Hashing, Graph Entropy, and Circuit Complexity.

[BibT_eX]

[DOI]

Ilan Newman

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

On Computations with Integer Division.

[BibT_eX]

[DOI]

Bettina Just

RAIRO Theor. Informatics Appl., 1989

Deterministic Simulation of Probabilistic Constant Depth Circuits.

[BibT_eX]

Miklós Ajtai

Adv. Comput. Res., 1989

Towards Understanding Exclusive Read.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract)

[BibT_eX]

[DOI]

Aviad Cohen

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Efficient Identification Schemes Using Two Prover Interactive Proofs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1989

Hardness vs. Randomness - A Survey (abstract).

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.

[BibT_eX]

[DOI]

Allan Borodin

Theor. Comput. Sci., 1988

The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)).

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1988

The Discrete Logarithm Hides O(log n) Bits.

[BibT_eX]

[DOI]

Douglas L. Long

SIAM J. Comput., 1988

Relations Between Concurrent-Write Models of Parallel Computation.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

The Complexity of Parallel Search.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

Rubber bands, convex embeddings and graph connectivity.

[BibT_eX]

[DOI]

Nathan Linial

László Lovász

Comb., 1988

Simulations Among Concurrent-Write PRAMs.

[BibT_eX]

[DOI]

Algorithmica, 1988

Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)

[BibT_eX]

[DOI]

Michael Ben-Or

Shafi Goldwasser

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

Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions

[BibT_eX]

[DOI]

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

Hardness vs. Randomness (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

The Complexity of Parallel Sorting.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

A Time-Space Tradeoff for Element Distinctness.

[BibT_eX]

[DOI]

Allan Borodin

SIAM J. Comput., 1987

How to share memory in a distributed system.

[BibT_eX]

[DOI]

J. ACM, 1987

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority

[BibT_eX]

[DOI]

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986

Constructing a perfect matching is in random NC.

[BibT_eX]

[DOI]

Comb., 1986

On Play by Means of Computing Machines.

[BibT_eX]

Nimrod Megiddo

Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

Proofs that Release Minimum Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees

[BibT_eX]

[DOI]

Michael E. Saks

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications

[BibT_eX]

[DOI]

Nathan Linial

László Lovász

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

On a Search Problem Related to Branch-and-Bound Procedures

[BibT_eX]

[DOI]

Michael E. Saks

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1986

1985

A Fast Parallel Algorithm for the Maximal Independent Set Problem

[BibT_eX]

[DOI]

J. ACM, October, 1985

Trade-Offs Between Depth and Width in Parallel Computation.

[BibT_eX]

[DOI]

Uzi Vishkin

SIAM J. Comput., 1985

Rectilinear Graphs and their Embeddings.

[BibT_eX]

[DOI]

Gopalakrishnan Vijayan

SIAM J. Comput., 1985

Are Search and Decision Problems Computationally Equivalent?

[BibT_eX]

[DOI]

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation

[BibT_eX]

[DOI]

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Complexity of Parallel Computation on Matroids

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)

[BibT_eX]

[DOI]

Miklós Ajtai

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Multi-Layer Grid Embeddings

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

How to Share Memory in a Distributed System (A Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Improving the Performance Guarantee for Approximate Graph Coloring

[BibT_eX]

[DOI]

J. ACM, October, 1983

Dynamic Parallel Memories

[BibT_eX]

[DOI]

Uzi Vishkin

Inf. Control., March, 1983

Succinct Representations of Graphs

[BibT_eX]

[DOI]

Hana Galperin

Inf. Control., March, 1983

How Discreet is the Discrete Log?

[BibT_eX]

[DOI]

Douglas L. Long

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version)

[BibT_eX]

[DOI]

Uzi Vishkin

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

A New Approximate Graph Coloring Algorithm

[BibT_eX]

[DOI]

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

On the Security of Multi-Party Protocols in Distributed Systems.

[BibT_eX]

[DOI]

Danny Dolev