Search results for "CCC"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
1	Sourav Chakraborty 0001	On the Sensitivity of Cyclically-Invariant Boolean Functions.	CCC	2005	DBLP DOI BibTeX RDF
1	Bill Rosgen	On the Hardness of Distinguishing Mixed-State Quantum Computations.	CCC	2005	DBLP DOI BibTeX RDF
1	Amos Beimel, Enav Weinreb	Monotone Circuits for Weighted Threshold Functions.	CCC	2005	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan	Short PCPs Verifiable in Polylogarithmic Time.	CCC	2005	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Subhash Khot	Hardness of Max 3SAT with No Mixed Clauses.	CCC	2005	DBLP DOI BibTeX RDF
1	Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan	Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.	CCC	2005	DBLP DOI BibTeX RDF
1	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	Computationally Private Randomizing Polynomials and Their Applications.	CCC	2005	DBLP DOI BibTeX RDF
1	Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma	If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances.	CCC	2005	DBLP DOI BibTeX RDF
1	Lance Fortnow, Adam R. Klivans	NP with Small Advice.	CCC	2005	DBLP DOI BibTeX RDF
1	Emanuele Viola	Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates.	CCC	2005	DBLP DOI BibTeX RDF
1	Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu	On the Complexity of Hardness Amplification.	CCC	2005	DBLP DOI BibTeX RDF
1	Shuchi Chawla 0001, Robert Krauthgamer, Ravi Kumar 0001, Yuval Rabani, D. Sivakumar 0001	On the Hardness of Approximating Multicut and Sparsest-Cut.	CCC	2005	DBLP DOI BibTeX RDF
1	Josh Buresh-Oppenheim, Tsuyoshi Morioka	Relativized NP Search Problems and Propositional Proof Systems.	CCC	2004	DBLP DOI BibTeX RDF
1	Scott Aaronson	Limitations of Quantum Advice and One-Way Communication.	CCC	2004	DBLP DOI BibTeX RDF
1	Andrej Bogdanov, Luca Trevisan	Lower Bounds for Testing Bipartiteness in Dense Graphs.	CCC	2004	DBLP DOI BibTeX RDF
1	Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton	Polynomials That Sign Represent Parity and Descartes Rule of Signs.	CCC	2004	DBLP DOI BibTeX RDF
1		19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA	CCC	2004	DBLP BibTeX RDF
1	Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig	Multiparty Quantum Coin Flipping.	CCC	2004	DBLP DOI BibTeX RDF
1	Klaus-Jörn Lange	Some Results on Majority Quantifiers over Words.	CCC	2004	DBLP DOI BibTeX RDF
1	Hoeteck Wee	On Pseudoentropy versus Compressibility.	CCC	2004	DBLP DOI BibTeX RDF
1	Nicola Galesi, Neil Thapen	The Complexity of Treelike Systems over lamda-Local Formulae.	CCC	2004	DBLP DOI BibTeX RDF
1	Chris Marriott, John Watrous	Quantum Arthur-Merlin Games.	CCC	2004	DBLP DOI BibTeX RDF
1	Vikraman Arvind, Jacobo Torán	Solvable Group Isomorphism.	CCC	2004	DBLP DOI BibTeX RDF
1	John M. Hitchcock, N. V. Vinodchandran	Dimension, Entropy Rates, and Compression.	CCC	2004	DBLP DOI BibTeX RDF
1	John M. Hitchcock	Small Spans in Scaled Dimension.	CCC	2004	DBLP DOI BibTeX RDF
1	Sophie Laplante, Frédéric Magniez	Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments.	CCC	2004	DBLP DOI BibTeX RDF
1	Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, Ge Xia	Tight Lower Bounds for Certain Parameterized NP-Hard Problems.	CCC	2004	DBLP DOI BibTeX RDF
1	Xiaoming Sun 0001, Andrew Chi-Chih Yao, Shengyu Zhang	Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?	CCC	2004	DBLP DOI BibTeX RDF
1	Andris Ambainis, Ke Yang 0005	Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information.	CCC	2004	DBLP DOI BibTeX RDF
1	Alan L. Selman, Samik Sengupta	Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy.	CCC	2004	DBLP DOI BibTeX RDF
1	Ilan Newman	Computing in Fault Tolerance Broadcast Networks.	CCC	2004	DBLP DOI BibTeX RDF
1	Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta	Properties of NP-Complete Sets.	CCC	2004	DBLP DOI BibTeX RDF
1	Dániel Marx	Parameterized Complexity of Constraint Satisfaction Problems.	CCC	2004	DBLP DOI BibTeX RDF
1	Harry Buhrman, Troy Lee, Dieter van Melkebeek	Language Compression and Pseudorandom Generators.	CCC	2004	DBLP DOI BibTeX RDF
1	Harry Buhrman, Leen Torenvliet	Separating Complexity Classes Using Structural Properties.	CCC	2004	DBLP DOI BibTeX RDF
1	Ran Raz, Amir Shpilka	Deterministic Polynomial Identity Testing in Non-Commutative Models.	CCC	2004	DBLP DOI BibTeX RDF
1	Ran Raz, Amir Shpilka	On the Power of Quantum Proofs.	CCC	2004	DBLP DOI BibTeX RDF
1	Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous	Consequences and Limits of Nonlocal Strategies.	CCC	2004	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Daniele Micciancio, Oded Regev 0001	The Complexity of the Covering Radius Problem on Lattices and Codes.	CCC	2004	DBLP DOI BibTeX RDF
1	Vikraman Arvind, T. C. Vijayaraghavan	Abelian Permutation Group Problems and Logspace Counting Classes.	CCC	2004	DBLP DOI BibTeX RDF
1	Luca Trevisan, Salil P. Vadhan, David Zuckerman	Compression of Samplable Sources.	CCC	2004	DBLP DOI BibTeX RDF
1	Christian Glaßer, Alan L. Selman, Samik Sengupta	Reductions between Disjoint NP-Pairs.	CCC	2004	DBLP DOI BibTeX RDF
1	John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran	Partial Bi-immunity and NP-Completeness.	CCC	2004	DBLP DOI BibTeX RDF
1	Manindra Agrawal	On Derandomizing Tests for Certain Polynomial Identities.	CCC	2003	DBLP DOI BibTeX RDF
1	Emanuele Viola	Hardness vs. Randomness within Alternating Time.	CCC	2003	DBLP DOI BibTeX RDF
1	Navin Goyal, Michael E. Saks, Srinivasan Venkatesh 0001	Optimal Separation of EROW and CROWPRAMs.	CCC	2003	DBLP DOI BibTeX RDF
1	Howard Barnum, Michael E. Saks, Mario Szegedy	Quantum query complexity and semi-definite programming.	CCC	2003	DBLP DOI BibTeX RDF
1	Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi	The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.	CCC	2003	DBLP DOI BibTeX RDF
1	Richard Beigel, Lance Fortnow	Are Cook and Karp Ever the Same?	CCC	2003	DBLP DOI BibTeX RDF
1	Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang	Disjoint NP-Pairs.	CCC	2003	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami	List Decoding with Side Information.	CCC	2003	DBLP DOI BibTeX RDF
1	Andrei E. Romashchenko	Extracting the Mutual Information for a Triple of Binary Strings.	CCC	2003	DBLP DOI BibTeX RDF
1	Wolfgang Merkle	The complexity of stochastic sequences.	CCC	2003	DBLP DOI BibTeX RDF
1	Ke Yang, Avrim Blum	On Statistical Query Sampling and NMR Quantum Computing.	CCC	2003	DBLP DOI BibTeX RDF
1	Albert Atserias, Víctor Dalmau	A Combinatorial Characterization of Resolution Width.	CCC	2003	DBLP DOI BibTeX RDF
1	Oded Regev 0001	Improved Inapproximability of Lattice and Coding Problems with Preprocessing.	CCC	2003	DBLP DOI BibTeX RDF
1	Yijia Chen, Jörg Flum, Martin Grohe	Bounded Nondeterminism and Alternation in Parameterized Complexity Theory.	CCC	2003	DBLP DOI BibTeX RDF
1	Johan Håstad	Inapproximability Some history and some open problems.	CCC	2003	DBLP DOI BibTeX RDF
1		18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark	CCC	2003	DBLP BibTeX RDF
1	Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma	Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games.	CCC	2003	DBLP DOI BibTeX RDF
1	Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind	Memoization and DPLL: Formula Caching Proof Systems.	CCC	2003	DBLP DOI BibTeX RDF
1	Russell Impagliazzo, Philippe Moser	A zero one law for RP.	CCC	2003	DBLP DOI BibTeX RDF
1	Lance Fortnow, Aduri Pavan, Samik Sengupta	Proving SAT does not have Small Circuits with an Application to the Two.	CCC	2003	DBLP DOI BibTeX RDF
1	Ryan O'Donnell, Rocco A. Servedio	Extremal properties of polynomial threshold functions.	CCC	2003	DBLP DOI BibTeX RDF
1	Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel	Universal Languages and the Power of Diagonalization.	CCC	2003	DBLP DOI BibTeX RDF
1	Rahul Santhanam, Dieter van Melkebeek	Holographic Proofs and Derandomization.	CCC	2003	DBLP DOI BibTeX RDF
1	Amit Chakrabarti, Subhash Khot, Xiaodong Sun	Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness.	CCC	2003	DBLP DOI BibTeX RDF
1	Hartmut Klauck	Rectangle Size Bounds and Threshold Covers in Communication Complexity.	CCC	2003	DBLP DOI BibTeX RDF
1	Pranab Sen	Lower bounds for predecessor searching in the cell probe model.	CCC	2003	DBLP DOI BibTeX RDF
1	Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy	Derandomization and Distinguishing Complexity.	CCC	2003	DBLP DOI BibTeX RDF
1	Detlef Sieling	Minimization of Decision Trees Is Hard to Approximate.	CCC	2003	DBLP DOI BibTeX RDF
1	Subhash Khot, Oded Regev 0001	Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.	CCC	2003	DBLP DOI BibTeX RDF
1	Jonas Holmerin, Subhash Khot	A Strong Inapproximability Gap for a Generalization of Minimum Bisection.	CCC	2003	DBLP DOI BibTeX RDF
1	Scott Aaronson	Quantum Certificate Complexity.	CCC	2003	DBLP DOI BibTeX RDF
1	Lars Engebretsen, Jonas Holmerin	Three-Query PCPs with Perfect Completeness over non-Boolean Domains.	CCC	2003	DBLP DOI BibTeX RDF
1	Ryan O'Donnell	Hardness Amplification within NP.	CCC	2002	DBLP DOI BibTeX RDF
1	Frederic Green	The Correlation Between Parity and Quadratic Polynomials Mod 3.	CCC	2002	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson	Hard Examples for Bounded Depth Frege.	CCC	2002	DBLP DOI BibTeX RDF
1	Uriel Feige, Daniele Micciancio	The Inapproximability of Lattice and Coding Problems with Preprocessing.	CCC	2002	DBLP DOI BibTeX RDF
1	Miklós Ajtai, Ravi Kumar 0001, D. Sivakumar 0001	Sampling Short Lattice Vectors and the Closest Lattice Vector Problem.	CCC	2002	DBLP DOI BibTeX RDF	SVP, CVP, Lattice, shortest vector problem, closest vector problem
1	Manindra Agrawal	Pseudo-Random Generators and Structure of Complete Degrees.	CCC	2002	DBLP DOI BibTeX RDF	Completeness, Reductions, Pseudo-random Generators
1	Peter Winkler 0001	Rapid Mixing.	CCC	2002	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Madhu Sudan 0001	Decoding Concatenated Codes using Soft Information.	CCC	2002	DBLP DOI BibTeX RDF
1	Ashwin Nayak 0001, Julia Salzman	On Communication over an Entanglement-Assisted Quantum Channel.	CCC	2002	DBLP DOI BibTeX RDF
1	Alexander A. Razborov	Resolution Lower Bounds for Perfect Matching Principles.	CCC	2002	DBLP DOI BibTeX RDF	Matching Principles, Resolution, Proof Complexity, Pigeonhole principle
1	Subhash Khot	On the Power of Unique 2-Prover 1-Round Games.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
1	Eldar Fischer, Ilan Newman	Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable.	CCC	2002	DBLP DOI BibTeX RDF
1	Philipp Woelfel	On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism.	CCC	2002	DBLP DOI BibTeX RDF	Lower Bounds, BDDs, Nondeterminism, Branching Programs, Integer Multiplication
1	Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar 0001, Ronitt Rubinfeld	The Complexity of Approximating the Entropy.	CCC	2002	DBLP DOI BibTeX RDF	entropy approximation, black-box distribution, monotone distribution, entropy, sample complexity
1	Roy Meshulam, Avi Wigderson	Expanders from Symmetric Codes.	CCC	2002	DBLP DOI BibTeX RDF
1	Oded Goldreich 0001, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan	Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval.	CCC	2002	DBLP DOI BibTeX RDF	Error Correcting Codes, Linear Codes, Private Information Retrieval
1	Ran Raz	Resolution Lower Bounds for the Weak Pigeonhole Principle.	CCC	2002	DBLP DOI BibTeX RDF
1	Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar 0001, D. Sivakumar 0001	Information Theory Methods in Communication Complexity.	CCC	2002	DBLP DOI BibTeX RDF	Fano's inequality, Maximum Likelihood Estimate Principle, Information Theory, Communication complexity
1	Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio	Learnability beyond AC0.	CCC	2002	DBLP DOI BibTeX RDF
1	Lance Fortnow	The History of Complexity.	CCC	2002	DBLP DOI BibTeX RDF	Computational Complexity, History of Computing
1	Andris Ambainis, Adam D. Smith, Ke Yang 0005	Extracting Quantum Entanglement.	CCC	2002	DBLP DOI BibTeX RDF	Entanglement Purification, General Error Models, Purity-Testing, Quantum Cryptography
1	Markus Bläser	Algebras of Minimal Rank over Perfect Fields.	CCC	2002	DBLP DOI BibTeX RDF	algebras of minimal rank, multiplication, bilinear complexity
1	Luca Trevisan, Salil P. Vadhan	Pseudorandomness and Average-Case Complexity via Uniform Reductions.	CCC	2002	DBLP DOI BibTeX RDF
1	Boaz Barak, Oded Goldreich 0001	Universal Arguments and their Applications.	CCC	2002	DBLP DOI BibTeX RDF	Probabilistic proof systems, computationally-sound proof systems, zero-knowledge proof systems, probabilistic checkable proofs (PCP), collision-free hashing, witness indistinguishable proof systems, error-correcting codes, proofs of knowledge
1	Stefan S. Dantchev	Resolution Width-Size Trade-offs for the Pigeon-Hole Principle.	CCC	2002	DBLP DOI BibTeX RDF	Pigeon-Hole Principle, Width-Size trade-off, Resolution, Propositional Proof Complexity

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