|
|
Venues (Conferences, Journals, ...)
|
|
GrowBag graphs for keyword ? (Num. hits/coverage)
Group by:
The graphs summarize 446 occurrences of 248 keywords
|
|
|
Results
Found 995 publication records. Showing 995 according to the selection in the facets
Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Jun Tarui, Tatsuie Tsukiji |
Learning DNF by Approximating Inclusion-Exclusion Formulae. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
Inclusion-exclusion formula, PAC Learning, DNF |
1 | Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". |
CCC |
1999 |
DBLP DOI BibTeX RDF |
Turing degrees, mutual information, Kolmogorov complexity |
1 | J. Maurice Rojas |
On the Complexity of Diophantine Geometry in Low Dimensions (Abstract). |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi |
Non-Automatizability of Bounded-Depth Frege Proofs. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
Frege proof systems, automatizability of proof systems, interpolation, proof complexity |
1 | Judy Goldsmith, Martin Mundhenk |
Complexity Issues in Markov Decision Processes. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Daniel A. Spielman |
Models of Computation in Coding Theory. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Birgit Jenner, Pierre McKenzie, Jacobo Torán |
A Note on the Hardness of Tree Isomorphism. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Lance Fortnow |
Two Queries. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | |
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998 |
CCC |
1998 |
DBLP BibTeX RDF |
|
1 | Harry Buhrman, Leen Torenvliet |
Randomness is Hard. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Hartmut Klauck |
Lower Bounds for Computation with Limited Nondeterminism. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Johannes Köbler, Wolfgang Lindner 0002 |
On the Resource Bounded Measure of P/poly. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Richard Beigel, Bin Fu |
Solving Intractable Problems with DNA Computing. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Giovanni Di Crescenzo, Russell Impagliazzo |
Proofs of Membership vs. Proofs of Knowledge. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Oded Goldreich 0001, Madhu Sudan 0001 |
Computational Indistinguishability: A Sample Hierarchy. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Eric Allender, Klaus Reinhardt |
Isolation, Matching, and Counting. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow, John D. Rogers |
Complexity Limitations on Quantum Computation. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Lance Fortnow, Thomas Thierauf |
Nonrelativizing Separations. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Rodney G. Downey, Lance Fortnow |
Uniformly Hard Languages. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Dieter van Melkebeek |
Hard Sets are Hard to Find. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Kenneth W. Regan, D. Sivakumar |
Probabilistic Martingales and BPTIME Classes. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Jack H. Lutz |
Resource-Bounded Measure. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Johannes Köbler, Jochen Messner |
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Manindra Agrawal, Thomas Thierauf |
The Satisfiability Problem for Probabilistic Ordered Branching Programs. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Wolfgang Lindner 0002, Rainer Schuler, Osamu Watanabe 0001 |
Resource Bounded Measure and Learnability. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | John Watrous |
Relationships Between Quantum and Classical Space-Bounded Complexity Classes. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Helmut Veith |
How to Encode a Logical Structure by an OBDD. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Jin-yi Cai, Ajay Nerurkar |
Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Amos Beimel, Anna Gál |
On Arithmetic Branching Programs. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Ran Raz, Gábor Tardos, Oleg Verbitsky 0001, Nikolai K. Vereshchagin |
Arthur-Merlin Games in Boolean Decision Trees. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | D. Sivakumar |
On Membership Comparable Sets. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Madhav V. Marathe, Harry B. Hunt III, Daniel J. Rosenkrantz, Richard Edwin Stearns |
Theory of Periodically Specified Problems: Complexity and Approximability. |
CCC |
1998 |
DBLP DOI BibTeX RDF |
|
1 | Jianer Chen, Donald K. Friesen, Hao Zheng |
Tight Bound on Johnson's Algoritihm for Max-SAT. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
optimization, approximation algorithm, maximum satisfiability, performance ratio |
1 | Harry Buhrman, Lance Fortnow, Leen Torenvliet |
Six Hypotheses in Search of a Theorem. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
|
1 | Richard Beigel, Alexis Maciel |
Upper and Lower Bounds for Some Depth-3 Circuit Classes. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
constant depth, majority gate, MOD gate, inner product mod 2, threshold circuit |
1 | Klaus Ambos-Spies, Levke Bentzien |
Separating NP-Completeness Notions under Strong Hypotheses. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
NP-completeness notions separation, strong hypotheses, NP-m-completeness, NP-T-completeness, bounded-query reducibilities, resource bounded Baire category concept, computational complexity, resource bounded measure |
1 | Christoph Karg |
LR(k) Testing is Average Case Complete. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
Average Case Complexity, Average Case Completeness |
1 | László Babai, Peter G. Kimmel |
Randomized Simultaneous Messages: Solution of a Problem of Yao in Communication Complexity. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
randomized simultaneous messages, two-player communication model, deterministic SM complexity, quadratic reduction, lower bound proof, computational complexity, communication complexity, linear algebra |
1 | Daniel Hammer, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Inequalities for Shannon entropies and Kolmogorov complexities. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
finite objects, Ingleton's inequality, Gacs-Korner's results, computational complexity, Kolmogorov complexities, Shannon entropies, linear inequalities |
1 | Stasys Jukna |
Finite Limits and Monotone Computations: The Lower Bounds Criterion. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
real gates, lower bounds, threshold gates, monotone circuits |
1 | Gábor Tardos, Uri Zwick |
The Communication Complexity of the Universal Relation. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
protocols, communication complexity |
1 | Allan Borodin, Ran El-Yaniv |
On Ranomization in Online Computation. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
randomized online algorithms, competitive performance, Yao Principle, game theory, randomization, minimization, randomised algorithms, online computation, maximization, paging algorithms |
1 | Sanjeev Khanna, Madhu Sudan 0001, Luca Trevisan |
Constraint Satisfaction: The Approximability of Minimization Problems. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
complete problems, computational classes, computational complexity, Approximation algorithms, combinatorial optimization |
1 | Joshua Berman, Arthur Drisko, François Lemieux, Cristopher Moore, Denis Thérien |
Circuits and Expressions with NOn-Associative Gates. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
non-associative gates, non-associative groupoid, polyabelian groupoids, arbitrary Boolean functions, NC/sup 1/-complete, CIRCUIT VALUE, Boolean functions, multiplication, P-complete, EXPRESSION EVALUATION |
1 | Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp |
Reversible Space Equals Deterministic Space. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
determinism, reversible computation, Complexity classes, space bounds |
1 | Christer Berg, Staffan Ulfberg |
A Lower Bound for Perceptrons and an Oracle Separation of the PPPH Hierarchy. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
oracle separation, PP/sup PH/ hierarchy, linear size boolean circuits, superpolynomial size perceptrons, lower bound, Boolean functions, perceptrons |
1 | |
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997 |
CCC |
1997 |
DBLP BibTeX RDF |
|
1 | Liming Cai, Jianer Chen, Johan Håstad |
Circuit Bottom Fan-in and Computational Power. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
computational complexity, lower bound, circuit complexity, alternating Turing machine |
1 | Bernd Borchert, Riccardo Silvestri |
The General Notion of a Dot-Operator. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
|
1 | Ulrich Hertrampf |
Acceptance by Transformation Monoids (with an Application to Local Self Reductions). |
CCC |
1997 |
DBLP DOI BibTeX RDF |
local self reduction, bottleneck machine, structural complexity |
1 | Richard Beigel, Bin Fu |
Circuits Over PP and PL. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
reduction, oracle, circuit, closure, PL, Boolean formula, AC, NC, PP |
1 | Rodney G. Downey, André Nies |
Undecidability Results for Low Complexity Degree Structures. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
undecidability results, low complexity degree structures, EXPTIME degrees, polynomial time Turing, many-one reducibility, coding method, ideal lattices, hyper-polynomial time classes, Boolean algebra, Boolean algebras |
1 | Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer 0001 |
Hyper-Polynomial Hierarchies and the NP-Jump. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
|
1 | Kenneth W. Regan |
Polynomial Vicinity Circuits and Nonlinear Lower Bounds. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
|
1 | Manindra Agrawal, Eric Allender, Samir Datta |
On TC0, AC0, and Arithmetic Circuits. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
TC/sup 0/, AC/sup 0/, function classes, constant-depth polynomial-size arithmetic circuits, unbounded fanin addition, multiplication gates, constant-depth arithmetic circuits, computational complexity, normal forms, arithmetic circuits, closure properties |
1 | Jack H. Lutz, Yong Zhao |
The Density of Weakly Complete Problems under Adaptive Reductions. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
dense languages, polynomial reductions, sparse languages, weak completeness, computational complexity, complexity classes, resource-bounded measure |
1 | Heribert Vollmer, Klaus W. Wagner |
On Operators of Higher Types. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
set operator vs. word operator, translational methods, oracle, Operator, interactive protocol, relativization |
1 | Pierluigi Crescenzi |
A Short Guide to Approximation Preserving Reductions. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
approximation preserving reductions, computational complexity, complexity, combinatorial optimization |
1 | Maren Hinrichs, Gerd Wechsung |
Time Bounded Frequency Computations. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
Frequency Computation, Hierarchy of frequency classes under polynomial time bounds, Complexity Theory |
1 | Janos Simon, Shi-Chun Tsai |
A Note on the Bottleneck Counting Argument. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
bottleneck counting method, lower bound, approximation method, Monotone circuit |
1 | Rainer Schuler |
A Note on Universal Distributions for Polynomial-Time Computable Distributions. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
|
1 | Vikraman Arvind, Jacobo Torán |
A Nonadaptive NC Checker for Permutation Group Intersection. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
nonadaptive queries, permutation groups, Program checking |
1 | Lance Fortnow |
Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
|
1 | Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov |
Complexity and Expressive Power of Logic Programming. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
computational complexity, Logic programming, resolution, constraint logic programming, unification, expressive power |
1 | Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer |
Nondeterministic NC1 Computation. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
nondeterministic Turing machine, leaf language, Computational complexity, circuit |
1 | Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers |
Inverting Onto Functions. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
function classes, total functions, nondeterministic Turing machines, unambiguous computation, Computational complexity, invertibility |
1 | Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer |
Complements of Multivalued Functions. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
multivalued functions, NPMV functions, coNPMV, complete functions, query hierarchy, functional analogue, Boolean hierarchy, computational complexity, complexity, multivalued logic, polynomial time hierarchy |
1 | Uriel Feige, Joe Kilian |
Zero Knowledge and the Chromatic Number. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
approximation algorithms, zero knowledge, chromatic number, probabilistically checkable proofs |
1 | Samuel R. Buss, Toniann Pitassi |
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
|
1 | Helmut Veith |
Succinct Representation, Leaf Languages, and Projection Reductions. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
leaf languages, quantifier-free reductions, computational complexity, descriptive complexity, succinct representation |
1 | Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney |
L-Printable Sets. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
printability, logspace, rankability, computational complexity |
1 | V. Vinay |
Hierarchies of Circuit Classes that are Closed under Complement. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Circuits, Complexity Theory, Complementation |
1 | Christos H. Papadimitriou |
The Complexity of Knowledge Representation. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
computational complexity, complexity, artificial intelligence, artificial intelligence, knowledge representation, knowledge representation, complexity theory, common-sense reasoning, common-sense reasoning |
1 | Pascal Koiran |
VC Dimension in Circuit Complexity. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
sigmoidal circuits, neural networks, circuit complexity, Vapnik-Chervonenkis dimension |
1 | Georg Gottlob |
Collapsing Oracle-Tape Hierarchies. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
tape, logspace, logarithmic space, machine model, complexity, query, oracle, circuit, Turing machine, generalized quantifier, relativization, bounded queries |
1 | Ian Barland, Phokion G. Kolaitis, Madhukar N. Thakur |
Integer Programming as a Framework for Optimization and Approximability. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
structural complexity theory, approximation algorithms, combinatorial optimization, Integer Programming |
1 | Manindra Agrawal, Eric Allender |
An Isomorphism Theorem for Circuit Complexity. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Complete Sets, Berman-Hartmanis Conjecture, NC1, AC0, NC0, projections, Circuit Complexity, uniformity, Isomorphisms |
1 | Uriel Feige, Oleg Verbitsky 0001 |
Error Reduction by Parallel Repetition - a Negative Result. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
error reduction, Interactive proofs, parallel repetition, forbidden subgraph |
1 | Manindra Agrawal, Vikraman Arvind |
A Note on Decision versus Search for Graph Automorphism. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Witness search, Graph Automorphisms |
1 | Eric Bach 0001, Anne Condon, Elton Glaser, Celena Tanguay |
DNA Models and Algorithms for NP-complete Problems. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
3Sat, 3-Coloring, Independent Set problem, DNA algorithms, genetic algorithms, computational complexity, search problems, DNA computing, DNA computation, NP-complete problems, search algorithms, NP-hard problems |
1 | Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik |
On Coherence, Random-self-reducibility, and Self-correction. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
self-correctability, random-self-reducibility, polynomial advice, adaptive versus nonadaptive oracle machines, Computational complexity, coherence, Kolmogorov complexity |
1 | Alan L. Selman |
Much Ado about Functions. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
multivalued functions, search functions, hierarchies, one-way functions, complexity classes |
1 | Rainer Schuler |
Truth-table Closure and Turing Closure of Average Polynomial Time have Different Measures in EXP. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
computational complexity, completeness, average-case analysis, resource-bounded measure |
1 | Steven Homer, Jin-Yi Cai (eds.) |
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996 |
CCC |
1996 |
DBLP BibTeX RDF |
|
1 | Yongge Wang |
The Law of the Iterated Logarithm for p-Random Sequences. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
The law of the iterated logarithm, computational complexity, randomness |
1 | Ming Li 0001, Paul M. B. Vitányi |
Reversible Simulation of Irreversible Computation. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Irreversible computation, Computational energy dissipation, Reversible simulation, Storage space versus Energy Tradeoffs, Reversible computation |
1 | Marcus Schäfer 0001 |
Deciding the Vapnik-Cervonenkis dimension is SigmaP3-complete. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
computational complexity, VC dimension |
1 | Clemens Lautemann, Thomas Schwentick, Iain A. Stewart |
On Positive P. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
monotone problems, polynomial time |
1 | Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng |
A Comparison of Weak Completeness Notions. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Weak Completeness, Measure, Genericity, Completeness |
1 | Ker-I Ko, Klaus Weihrauch |
On the Measure of Two-Dimensional Regions with Polynomial-Time computables Boundaries. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Lebesgue measure, two-dimensional region, polynomial-time computable boundary, interior region, polynomial-time computable, computational complexity, computability, computability, Turing machines |
1 | Michael E. Saks |
Randomization and Derandomization in Space_Bounded Computation. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
pseudorandom generators, Probabilistic computation, space-bounded computation |
1 | Kazuo Iwama, Chuzo Iwamoto |
Parallel Complexity Hierarchies Based on PRAMs and DLOGTIME-Uniform Circuits. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
circuit family, DLOGTIME-uniformity, parallel computation, PRAM, complexity hierarchy |
1 | Dieter van Melkebeek |
Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
computational complexity theory, sparse hard set problem for P |
1 | Ashish V. Naik, Alan L. Selman |
A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
P, p-selective, adaptive reductions, nonadaptive reductions, complexity classes, NP |
1 | Noam Nisan |
Extracting Randomness: How and Why A survey. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Randmoness, Computational Complexity, Derandomization, Expanders |
Displaying result #901 - #995 of 995 (100 per page; Change: ) Pages: [ <<][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][ 10] |
|