default search action
Electronic Colloquium on Computational Complexity, 1995
Volume TR95, 1995
- Amos Beimel, Anna Gál, Mike Paterson:
Lower Bounds for Monotone Span Programs. - Detlef Sieling:
New Lower Bounds and Hierarchy Results for Restricted Branching Programs. - Marek Karpinski, Alexander Zelikovsky:
1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems. - Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk:
Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs. - Maciej Liskiewicz, Rüdiger Reischuk:
The Sublogarithmic Alternating Space World. - Kenneth W. Regan, D. Sivakumar, Jin-yi Cai:
Pseudorandom Generators, Measure Theory, and Natural Proofs. - Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, Walter Kern:
The Nucleon of Cooperative Games and an Algorithm for Matching Games. - Nader H. Bshouty:
Exact Learning Boolean Functions via the Monotone Theory. - Matthias Krause:
A Note on Realizing Iterated Multiplication by Small Depth Threshold Circuits. - Pavel Pudlák, Jirí Sgall:
An Upper Bound for a Communication Game Related to Time-Space Tradeoffs. - Roman Bacik, Sanjeev Mahajan:
Semidefinite Programming and its Applications to NP Problems. - Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, Walter Kern:
On the Complexity of Testing Membership in the Core of min-Cost Spanning Tree Games. - Oleg Verbitsky:
The Parallel Repetition Conjecture for Trees is True. - Ulrich Faigle, Walter Kern, Martin Streng:
Note On the Computational Complexity of j-Radii of Polytopes in Rn. - Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon:
Oracles and Queries That Are Sufficient for Exact Learning. - Ulrich Faigle, Sándor P. Fekete, Winfried Hochstättler, Walter Kern:
On Approximately Fair Cost Allocation in Euclidean TSP Games. - Claudia Bertram-Kretzberg, Thomas Hofmeister:
Multiple Product Modulo Arbitrary Numbers. - Jay Belanger, Jie Wang:
Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions. - Jin-yi Cai, Alan L. Selman:
Average Time Complexity Classes. - William Hurwood:
Dynamic Fault Diagnosis. - Marek Karpinski, Rutger Verbeek:
On Randomized Versus Deterministic Computation. - Marek Karpinski, Wojciech Rytter, Ayumi Shinohara:
Pattern-Matching for Strings with Short Descriptions. - Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. - Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCP and Non-Approximability - Towards Tight Results. - Günter Hotz, Gero Vierke, Björn Schieffer:
Analytic Machines. - Claus-Peter Schnorr, Horst Helmut Hörner:
Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction. - Frederic Green:
Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate. - Eric Allender, Martin Strauss:
Measure on P: Robustness of the Notion. - Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. - Marek Karpinski, Alexander Zelikovsky:
New Approximation Algorithms for the Steiner Tree Problems. - Dorit Dor, Uri Zwick:
Selecting the Median. - Nader H. Bshouty, Christino Tamon:
On the Fourier spectrum of Monotone Functions. - Richard Beigel, David Eppstein:
3-Coloring in time O(1.3446n): A no-MIS Algorithm. - Christoph Meinel, Stephan Waack:
Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems. - Richard Beigel:
Closure Properties of GapP and #P. - Richard Beigel, William I. Gasarch, Efim B. Kinber:
Frequency Computation and Bounded Queries. - Richard Beigel, Howard Straubing:
The Power of Local Self-Reductions. - Joe Kilian, Erez Petrank:
An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions. - Tomoyuki Yamakami:
Polynomial Time Samplable Distributions. - Uri Zwick, Mike Paterson:
The Complexity of Mean Payoff Games on Graphs. - Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
Optimal Bounds for the Approximation of Boolean Functions and Some Applications. - Beate Bollig, Ingo Wegener:
Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams. - Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay:
Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. - Carsten Damm, Stasys Jukna, Jirí Sgall:
Some Bounds on Multiparty Communication Complexity of Pointer Jumping. - Moni Naor, Omer Reingold:
Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions. - Vince Grolmusz:
On the Power of Circuits with Gates of Low L1 Norms. - Martin Löbbing, Ingo Wegener:
The Number of Knight's Tours Equals 33,439,123,484,294 - Counting with Binary Decision Diagrams. - Helmut Veith:
Succinct Representation and Leaf Languages. - Anna Gál, Avi Wigderson:
Boolean Complexity Classes vs. Their Arithmetic Analogs. - Oded Goldreich, Noam Nisan, Avi Wigderson:
On Yao's XOR-Lemma. - Pascal Koiran:
VC Dimension in Circuit Complexity. - Douglas R. Stinson:
On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes. - Petr Slavík:
Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems. - Farid M. Ablayev, Marek Karpinski:
On the Power of Randomized Branching Programs. - Marek Karpinski, Angus Macintyre:
VC Dimension of Sigmoidal and General Pfaffian Networks. - Oded Goldreich:
Three XOR-Lemmas - An Exposition. - Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao:
An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX. - Amnon Ta-Shma:
On Extracting Randomness From Weak Random Sources. - Nader H. Bshouty:
The Monotone Theory for the PAC-Model. - Nader H. Bshouty:
A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries. - Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
Hitting Sets Derandomize BPP. - Amir M. Ben-Amram, Zvi Galil:
On Data Structure Tradeoffs and an Application to Union-Find. - Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky:
A Lower Bound for Randomized Algebraic Decision Trees.
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-11-14 22:39 CET 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: