Search results for "CCC"

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

Publications at "CCC"( http://dblp.L3S.de/Venues/CCC )