Search results for "CCC"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
1	Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson	Randomness Conductors and Constant-Degree Lossless Expanders.	CCC	2002	DBLP DOI BibTeX RDF	expander graphs, extractors, condensers, graph products
1		Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002	CCC	2002	DBLP BibTeX RDF
1	Amit Deshpande 0001, Rahul Jain 0001, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam	Better Lower Bounds for Locally Decodable Codes.	CCC	2002	DBLP DOI BibTeX RDF	Second Moment Method, Probabilistically Checkable Proof Systems, Error Correcting Codes, Pseudorandom Generators, Private Information Retrieval
1	John Watrous	Arthur and Merlin in a Quantum World.	CCC	2002	DBLP DOI BibTeX RDF
1	Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel	Streaming Computation of Combinatorial Objects.	CCC	2002	DBLP DOI BibTeX RDF	error-correcting codes, extractors, dispersers, streaming computation, universal hash functions, online computation
1	Ian Agol, Joel Hass, William P. Thurston	3-MANIFOLD KNOT GENUS is NP-complete.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
1	Daniele Micciancio	Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection.	CCC	2002	DBLP DOI BibTeX RDF	worst-case/average-case connection, computational complexity, cryptography, hash functions, lattices
1	Christopher Umans	Pseudo-Random Generators for All Hardnesses.	CCC	2002	DBLP DOI BibTeX RDF	low-degree extension, hardness vs. randomness tradeoffs, pseudo-random generator
1	D. Sivakumar	Algorithmic Derandomization via Complexity Theory.	CCC	2002	DBLP DOI BibTeX RDF	Johnson-Lindenstrauss Lemma, Derandomization, randomized rounding
1	Paul Beame, Erik Vee	Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems.	CCC	2002	DBLP DOI BibTeX RDF
1	Jonas Holmerin	Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - ε.	CCC	2002	DBLP DOI BibTeX RDF
1	Uriel Feige	Relations between Average Case Complexity and Approximation Complexity.	CCC	2002	DBLP DOI BibTeX RDF	random 3sat, bipartite clique, bisection
1	Richard Chang 0001, Jon S. Squire	Bounded Query Functions with Limited Output Bits.	CCC	2001	DBLP DOI BibTeX RDF
1	Albert Atserias, Nicola Galesi, Pavel Pudlák	Monotone Simulations of Nonmonotone Proofs.	CCC	2001	DBLP DOI BibTeX RDF
1	Eric Allender, David A. Mix Barrington, William Hesse	Uniform Circuits for Division: Consequences and Problems.	CCC	2001	DBLP DOI BibTeX RDF
1	Amos Beimel, Yuval Ishai	On the Power of Nonlinear Secrect-Sharing.	CCC	2001	DBLP DOI BibTeX RDF
1	Larry J. Stockmeyer, Dharmendra S. Modha	Links Between Complexity Theory and Constrained Block Coding.	CCC	2001	DBLP DOI BibTeX RDF
1	Andrei A. Muchnik, Nikolai K. Vereshchagin	Logical Operations and Kolmogorov Complexity II.	CCC	2001	DBLP DOI BibTeX RDF
1	Harry Buhrman, Ronald de Wolf	Communication Complexity Lower Bounds by Polynomials.	CCC	2001	DBLP DOI BibTeX RDF
1	Rahul Santhanam	On Separators, Segregators and Time versus Space.	CCC	2001	DBLP DOI BibTeX RDF
1	Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann 0001, Frank Stephan 0001	Hausdorff Dimension in Exponential Time.	CCC	2001	DBLP DOI BibTeX RDF
1	Jack Jie Dai	A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure.	CCC	2001	DBLP DOI BibTeX RDF
1	Manindra Agrawal	Towards Uniform AC0 - Isomorphisms.	CCC	2001	DBLP DOI BibTeX RDF
1	Elchanan Mossel, Christopher Umans	On the Complexity of Approximating the VC Dimension.	CCC	2001	DBLP DOI BibTeX RDF
1	Aduri Pavan, Alan L. Selman	Separation of NP-Completeness Notions.	CCC	2001	DBLP DOI BibTeX RDF
1	Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf	Quantum Algorithms for Element Distinctness.	CCC	2001	DBLP DOI BibTeX RDF
1	Beate Bollig, Martin Sauerhoff, Ingo Wegener	On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs.	CCC	2001	DBLP DOI BibTeX RDF	Computational complexity, lower bounds, approximations, binary decision diagrams, branching programs
1		Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001	CCC	2001	DBLP BibTeX RDF
1	Amir Shpilka	Affine Projections of Symmetric Polynomials.	CCC	2001	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson, Nicola Galesi	Space Complexity of Random Formulae in Resolution.	CCC	2001	DBLP DOI BibTeX RDF
1	Rocco A. Servedio, Steven J. Gortler	Quantum versus Classical Learnability.	CCC	2001	DBLP DOI BibTeX RDF
1	Lance Fortnow	Comparing Notions of Full Derandomization.	CCC	2001	DBLP DOI BibTeX RDF
1	Jürgen Forster	A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity.	CCC	2001	DBLP DOI BibTeX RDF
1	Paul Beame, Russell Impagliazzo, Ashish Sabharwal	Resolution Complexity of Independent Sets in Random Graphs.	CCC	2001	DBLP DOI BibTeX RDF
1	Luis Antunes 0002, Lance Fortnow, Dieter van Melkebeek	Computational Depth.	CCC	2001	DBLP DOI BibTeX RDF
1	Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy, V. Vinay	Time-Space Tradeoffs in the Counting Hierarchy.	CCC	2001	DBLP DOI BibTeX RDF
1	Stefan S. Dantchev, Søren Riis	Tree Resolution Proofs of the Weak Pigeon-Hole Principle.	CCC	2001	DBLP DOI BibTeX RDF
1	Johan Håstad, Avi Wigderson	Simple Analysis of Graph Tests for Linearity and PCP.	CCC	2001	DBLP DOI BibTeX RDF	graph test, pseudorandomness, PCP, Linearity testing, iterated test
1	Péter Gács	Quantum Algorithmic Entropy.	CCC	2001	DBLP DOI BibTeX RDF
1	Ronen Shaltiel	Towards Proving Strong Direct Product Theorems.	CCC	2001	DBLP DOI BibTeX RDF
1	Noga Alon, Richard Beigel	Lower Bounds for Approximations by Low Degree Polynomials Over Zm.	CCC	2001	DBLP DOI BibTeX RDF
1	Michal Koucký 0001	Universal Traversal Sequences with Backtracking.	CCC	2001	DBLP DOI BibTeX RDF
1	Russell Impagliazzo, Valentine Kabanets, Avi Wigderson	In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.	CCC	2001	DBLP DOI BibTeX RDF
1	Iannis Tourlakis	Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines.	CCC	2000	DBLP DOI BibTeX RDF
1	Oliver Kullmann	An Application of Matroid Theory to the SAT Problem.	CCC	2000	DBLP DOI BibTeX RDF
1	Pavol Duris, Juraj Hromkovic, Katsushi Inoue	A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition.	CCC	2000	DBLP DOI BibTeX RDF	Las Vegas randomization, two-dimensional finite automata, nondeterminism
1	Jack H. Lutz	Dimension in Complexity Classes.	CCC	2000	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Sanjeev Khanna	On the Hardness of 4-Coloring a 3-Colorable Graph.	CCC	2000	DBLP DOI BibTeX RDF	Graph Coloring, Hardness of approximation, PCP
1	Gabriel Istrate	Computational Complexity and Phase Transitions.	CCC	2000	DBLP DOI BibTeX RDF
1	Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin	Combinatorial Interpretation of Kolmogorov Complexity.	CCC	2000	DBLP DOI BibTeX RDF	algorithmic information theory, combinatorial inequalities, Kolmogorov complexity
1	Carsten Damm, Markus Holzer 0001, Pierre McKenzie	The Complexity of Tensor Calculus.	CCC	2000	DBLP DOI BibTeX RDF
1	Nikolai K. Vereshchagin, Michael V. Vyugin	Independent Minimum Length Programs to Translate between Given Strings.	CCC	2000	DBLP DOI BibTeX RDF
1	Harry Buhrman, Sophie Laplante, Peter Bro Miltersen	New Bounds for the Language Compression Problem.	CCC	2000	DBLP DOI BibTeX RDF
1	Frederic Green, Steven Homer, Chris Pollett	On the Complexity of Quantum ACC.	CCC	2000	DBLP DOI BibTeX RDF
1	Marcus Schaefer 0001	Deciding the K-Dimension is PSPACE-Complete.	CCC	2000	DBLP DOI BibTeX RDF	computational complexity, learning theory, PSPACE
1	Ronald de Wolf	Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity.	CCC	2000	DBLP DOI BibTeX RDF	non-deterministic computation, Quantum computing, communication complexity, query complexity
1	André Berthiaume, Wim van Dam, Sophie Laplante	Quantum Kolmogorov Complexity.	CCC	2000	DBLP DOI BibTeX RDF	data compression, information theory, quantum computation, Kolmogorov complexity, quantum information theory
1	Oliver Giel	BP(L(f)1+epsilon).	CCC	2000	DBLP DOI BibTeX RDF
1	Lance Fortnow, Dieter van Melkebeek	Time-Space Tradeoffs for Nondeterministic Computation.	CCC	2000	DBLP DOI BibTeX RDF	Satisfiability, Time-space tradeoffs
1	Ketan Mulmuley, Pradyut Shah	A Lower Bound for the Shortest Path Problem.	CCC	2000	DBLP DOI BibTeX RDF	parallel, lower bound, shortest path problem
1		Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000	CCC	2000	DBLP BibTeX RDF
1	Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet	The Communication Complexity of Enumeration, Elimination, and Selection.	CCC	2000	DBLP DOI BibTeX RDF
1	Jeff Kahn 0001, Michael E. Saks, Cliff Smyth 0001	A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture.	CCC	2000	DBLP DOI BibTeX RDF	Reimer's inequality, van den Berg-Kesten conjecture, Rudich's conjecture
1	Paul M. B. Vitányi	Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State.	CCC	2000	DBLP DOI BibTeX RDF
1	Luca Trevisan	A Survey of Optimal PCP Characterizations of NP.	CCC	2000	DBLP DOI BibTeX RDF
1	Andrei A. Voronenko	On the Complexity of the Monotonicity Verification.	CCC	2000	DBLP DOI BibTeX RDF
1	George Karakostas, Richard J. Lipton, Anastasios Viglas	On the Complexity of Intersecting Finite State Automata.	CCC	2000	DBLP DOI BibTeX RDF
1	Thanh Minh Hoang, Thomas Thierauf	The Complexity of Verifying the Characteristic Polynomial and Testing Similarity.	CCC	2000	DBLP DOI BibTeX RDF
1	David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie	On the Complexity of Some Problems on Groups Input as Multiplication Tables.	CCC	2000	DBLP DOI BibTeX RDF	logic, circuit complexity, group membership, integer arithmetic
1	Ke Yang	Integer Circuit Evaluation is PSPACE-Complete.	CCC	2000	DBLP DOI BibTeX RDF	Integer Circuit, Chinese Remainder Theorem, PSPACE
1	Richard Cleve	The Query Complexity of Order-Finding.	CCC	2000	DBLP DOI BibTeX RDF
1	Andreas Jakoby, Rüdiger Reischuk	Average Case Complexity of Unbounded Fanin Circuits.	CCC	2000	DBLP DOI BibTeX RDF
1	Valentine Kabanets	Easiness Assumptions and Hardness Tests: Trading Time for Zero Error.	CCC	2000	DBLP DOI BibTeX RDF	probabilistic complexity classes, uniform setting, derandomization
1	Marcus Schaefer 0001	Graph Ramsey Theory and the Polynomial Hierarchy (Abstract).	CCC	1999	DBLP DOI BibTeX RDF
1	Jack Jie Dai, Jack H. Lutz	Query Order and NP-Completeness.	CCC	1999	DBLP DOI BibTeX RDF	query order, resource-bounded genericity, computational complexity, NP-completeness, complexity classes, resource-bounded measure
1	Jin-yi Cai	Some Recent Progress on the Complexity of Lattice Problems.	CCC	1999	DBLP DOI BibTeX RDF
1	Tao Jiang 0001, Ming Li 0001, Paul M. B. Vitányi	The Expected Size of Heilbronn's Triangles.	CCC	1999	DBLP DOI BibTeX RDF
1	Ziv Bar-Yossef, Oded Goldreich 0001, Avi Wigderson	Deterministic Amplification of Space-Bounded Probabilistic Algorithms.	CCC	1999	DBLP DOI BibTeX RDF	space bounded randomized computation, deterministic amplification, expander graphs
1	Eric Allender, Michael E. Saks, Igor E. Shparlinski	A Lower Bound for Primality.	CCC	1999	DBLP DOI BibTeX RDF	Circuit Complexity Lower Bounds, Primality, Square-Free Numbers, GCD
1	Jin-yi Cai	Applications of a New Transference Theorem to Ajtai's Connection Factor.	CCC	1999	DBLP DOI BibTeX RDF	Transference theorems, Lattices, Public-key cryptosystem, Average-case complexity, Harmonic analysis, Shortest vector problem
1	Harry Buhrman, Leen Torenvliet	Complicated Complementations.	CCC	1999	DBLP DOI BibTeX RDF	Oracles, Kolmogorov Complexity, Complexity Classes, Simplicity, Polynomial Hierarchy, Immunity
1	David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum	On Monotone Planar Circuits.	CCC	1999	DBLP DOI BibTeX RDF
1	Mikael Goldmann, Alexander Russell	The Complexity of Solving Equations over Finite Groups.	CCC	1999	DBLP DOI BibTeX RDF
1	Ravi Kumar 0001, D. Sivakumar 0001	Proofs, Codes, and Polynomial-Time Reducibilities.	CCC	1999	DBLP DOI BibTeX RDF	reducibilities, proof systems, partial solutions
1	Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi	Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).	CCC	1999	DBLP DOI BibTeX RDF	counting principles, graph tautologies, algebraic proof systems, binomial proofs, Nullstellensatz proofs, polynomial calculus proofs, propositional logic, Proof complexity
1	John Watrous	Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity.	CCC	1999	DBLP DOI BibTeX RDF	quantum computation, graph connectivity, space-bounded computation
1	Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank	Computing from Partial Solutions.	CCC	1999	DBLP DOI BibTeX RDF	Robust proofs, erasure correction, erasure-resilient reductions, fault tolerant computations, NP-Hardness
1	Oded Goldreich 0001, Salil P. Vadhan	Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK.	CCC	1999	DBLP DOI BibTeX RDF	Statistical Zero-Knowledge Proofs, Universal Hashing, Arthur-Merlin Games
1	László Babai, Sophie Laplante	Stronger Separations for Random-Self-Reducibility, Rounds, and Advice.	CCC	1999	DBLP DOI BibTeX RDF
1	Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh 0001	The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract).	CCC	1999	DBLP DOI BibTeX RDF	pointer chasing, entropy, Communication complexity
1	Ravi Kumar 0001, D. Sivakumar 0001	A Note on the Shortest Lattice Vector Problem.	CCC	1999	DBLP DOI BibTeX RDF	shortest lattice vector, NP-completness, uniqueness
1	Richard Beigel, Alexis Maciel	Circuit Lower Bounds Collapse Relativized Complexity Classes.	CCC	1999	DBLP DOI BibTeX RDF	relativized computation, Booleand circuits, oracles, complexity theory
1	Amir Shpilka, Avi Wigderson	Depth-3 Arithmetic Formulae over Fields of Characteristic Zero.	CCC	1999	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson, Avi Wigderson	Short Proofs Are Narrow - Resolution Made Simple (Abstract).	CCC	1999	DBLP DOI BibTeX RDF
1	Madhu Sudan 0001, Luca Trevisan, Salil P. Vadhan	Pseudorandom Generators without the XOR Lemma (Abstract).	CCC	1999	DBLP DOI BibTeX RDF	polynomial reconstruct ion, Pseudorandom generators, extractors, list-decoding
1	Harry Buhrman, Wim van Dam	Quantum Bounded Query Complexity.	CCC	1999	DBLP DOI BibTeX RDF	query limited reductions, quantum computation, structural complexity
1	Avi Wigderson	De-Randomizing BPP: The State of the Art.	CCC	1999	DBLP DOI BibTeX RDF
1	Richard Beigel	Gaps in Bounded Query Hierarchies.	CCC	1999	DBLP DOI BibTeX RDF	complexity, separation, collapse, bounded queries
1	Russell Impagliazzo, Ramamohan Paturi	Complexity of k-SAT.	CCC	1999	DBLP DOI BibTeX RDF	NP-completeness, Satisfiability, Reductions, Complexity Theory
1		Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999	CCC	1999	DBLP BibTeX RDF

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