default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 1996
Volume TR96, 1996
- Manindra Agrawal, Richard Beigel, Thomas Thierauf:
Modulo Information from Nonadaptive Queries to NP. - Manindra Agrawal, Eric Allender:
An Isomorphism Theorem for Circuit Complexity. - Alexei Y. Kitaev:
Quantum measurements and the Abelian Stabilizer Problem. - Shiva Chaudhuri, Jaikumar Radhakrishnan:
Deterministic Restrictions in Circuit Complexity. - Hans-Jörg Burtschick, Heribert Vollmer:
Lindstroem Quantifiers and Leaf Language Definability. - Bernd Borchert, Antoni Lozano:
Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept. - Miklós Ajtai:
Generating Hard Instances of Lattice Problems. - Francesco Bergadano, Nader H. Bshouty, Stefano Varricchio:
Learning Multivariate Polynomials from Substitution and Equivalence Queries. - Francesco Bergadano, Nader H. Bshouty, Christino Tamon, Stefano Varricchio:
On Learning Branching Programs and Small Depth Circuits. - Christoph Meinel, Anna Slobodová:
An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams. - Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith:
Sharply Bounded Alternation within P. - Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson:
Visual Cryptography for General Access Structures. - Mitsunori Ogihara:
The PL Hierarchy Collapses. - Mitsunori Ogihara:
Sparse Hard Sets for P Yields Space-Efficient Algorithms. - Edoardo Amaldi, Viggo Kann:
On the approximability of some NP-hard minimization problems for linear systems. - Andrea E. F. Clementi, Luca Trevisan:
Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints. - Christoph Meinel, Stephan Waack:
The "Log Rank" Conjecture for Modular Communication Complexity. - Oded Goldreich, Johan Håstad:
On the Message Complexity of Interactive Proof Systems. - Claus-Peter Schnorr:
Security of 2t-Root Identification and Signatures. - Carsten Rössner, Claus-Peter Schnorr:
An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension. - Yongge Wang:
NP-hard Sets Are Superterse unless NP Is Small. - Martin Sauerhoff, Ingo Wegener, Ralph Werchner:
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits. - Eric Allender:
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy. - Eric Allender, Robert Beals, Mitsunori Ogihara:
The complexity of matrix rank and feasible systems of linear equations. - Wolfgang Maass, Berthold Ruf:
The Computational Power of Spiking Neurons Depends on the Shape of the Postsynaptic Potentials. - Stasys Jukna:
Finite Limits and Monotone Computations. - Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman:
Computing Solutions Uniquely Collapses the Polynomial Hierarchy. - Sanjeev Khanna, Madhu Sudan:
The Optimization Complexity of Constraint Satisfaction Problems. - Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
Towards efficient constructions of hitting sets that derandomize BPP. - Meera Sitharam:
Approximation from linear spaces and applications to complexity. - Wolfgang Maass:
Networks of Spiking Neurons: The Third Generation of Neural Network Models. - Manindra Agrawal, Thomas Thierauf:
The Boolean Isomorphism Problem. - Bernd Borchert, Desh Ranjan, Frank Stephan:
On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions. - Vasken Bohossian, Jehoshua Bruck:
On Neural Networks with Minimal Weights. - Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
Probabilistic Type-2 Operators and "Almost"-Classes. - Petr Savický, Stanislav Zák:
A large lower bound for 1-branching programs. - Stasys Jukna, Alexander A. Razborov:
Neither Reading Few Bits Twice nor Reading Illegally Helps Much. - Michael A. Gibson, Jehoshua Bruck:
Efficient Digital to Analog Encoding. - Carme Àlvarez, Raymond Greenlaw:
A Compendium of Problems Complete for Symmetric Logarithmic Space. - Thomas Thierauf:
The Isomorphismproblem for One-Time-Only Branching Programs. - Oded Goldreich, Avi Wigderson:
On the Circuit Complexity of Perfect Hashing. - Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Collision-Free Hashing from Lattice Problems. - Edmund Ihler:
On polynomial time approximation schemes and approximation preserving reductions. - Yosi Ben-Asher, Ilan Newman:
Optimal Search in Trees. - Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe:
Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems. - Luca Trevisan:
On the Approximability of the Multi-dimensional Euclidean TSP. - Oded Goldreich, Shmuel Safra
:
A Combinatorial Consistency Lemma with application to the PCP Theorem. - Eric Allender, Klaus-Jörn Lange:
StUSPACE(log n) is Contained in DSPACE((log2n)/loglog n). - Per Enflo, Meera Sitharam:
Stable basis families and complexity lower bounds. - Petr Savický, Stanislav Zák:
A hierarchy for (1,+k)-branching programs with respect to k. - Richard Beigel, William I. Gasarch, Ming Li, Louxin Zhang:
Addition in log2n + O(1) Steps on Average: A Simple Analysis. - Martin Dietzfelbinger:
Gossiping and Broadcasting versus Computing Functions in Networks. - Yosi Ben-Asher, Ilan Newman:
Geometric Approach for Optimal Routing on Mesh with Buses. - Oded Goldreich:
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof. - Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
Hitting Properties of Hard Boolean Operators and their Consequences on BPP. - Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Public-Key Cryptosystems from Lattice Reduction Problems. - Oded Goldreich, Shafi Goldwasser, Dana Ron:
Property Testing and its connection to Learning and Approximation. - Dima Grigoriev, Marek Karpinski:
Randomized Omega(n2) Lower Bound for Knapsack. - Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz:
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes. - Bernd Borchert, Frank Stephan:
Looking for an Analogue of Rice's Theorem in Complexity Theory. - Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener:
Optimal attribute-efficient learning of disjunction, parity, and threshold functions. - Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. - Martin Dietzfelbinger:
The Linear-Array Problem in Communication Complexity Resolved. - Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint satisfaction: The approximability of minimization problems. - Miklós Ajtai, Cynthia Dwork:
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. - Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan:
Structure in Approximation Classes. - Oded Goldreich, Bernd Meyer:
Computational Indistinguishability - Algorithms vs. Circuits.
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-10-22 02:16 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
