Search results for "CCC"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
1	Neeraj Kayal, Chandan Saha 0001	On the Sum of Square Roots of Polynomials and Related Problems.	CCC	2011	DBLP DOI BibTeX RDF
1	Shachar Lovett, Emanuele Viola	Bounded-Depth Circuits Cannot Sample Good Codes.	CCC	2011	DBLP DOI BibTeX RDF
1	Thomas Watson 0001	Pseudorandom Generators for Combinatorial Checkerboards.	CCC	2011	DBLP DOI BibTeX RDF
1	Xin Li 0006	A New Approach to Affine Extractors and Dispersers.	CCC	2011	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami	Linear-Algebraic List Decoding of Folded Reed-Solomon Codes.	CCC	2011	DBLP DOI BibTeX RDF
1	Yuichi Yoshida	Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs.	CCC	2011	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan 0001	Symmetric LDPC Codes are not Necessarily Locally Testable.	CCC	2011	DBLP DOI BibTeX RDF
1	Arkadev Chattopadhyay, Shachar Lovett	Linear Systems over Finite Abelian Groups.	CCC	2011	DBLP DOI BibTeX RDF
1	Paul Beame, Widad Machmouchi	Making Branching Programs Oblivious Requires Superlogarithmic Overhead.	CCC	2011	DBLP DOI BibTeX RDF
1	Andrew Drucker	Improved Direct Product Theorems for Randomized Query Complexity.	CCC	2011	DBLP DOI BibTeX RDF
1	Zohar Shay Karnin, Yuval Rabani, Amir Shpilka	Explicit Dimension Reduction and Its Applications.	CCC	2011	DBLP DOI BibTeX RDF
1	Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland	Symmetry-Assisted Adversaries for Quantum State Generation.	CCC	2011	DBLP DOI BibTeX RDF
1	Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii	Exact Threshold Circuits.	CCC	2010	DBLP DOI BibTeX RDF	Exact Threshold Functions, Boolean Circuits, Threshold Functions
1	Thanh Minh Hoang	On the Matching Problem for Special Graph Classes.	CCC	2010	DBLP DOI BibTeX RDF	NC-computations, Perfect matchings, maximum matchings
1	Oded Regev 0001	The Learning with Errors Problem (Invited Survey).	CCC	2010	DBLP DOI BibTeX RDF	learning with errors, lattice-based cryptography
1	Ronen Shaltiel	Derandomized Parallel Repetition Theorems for Free Games.	CCC	2010	DBLP DOI BibTeX RDF	Derandomization, Randomness extractors, Parallel repetition
1	Zeev Dvir	On Matrix Rigidity and Locally Self-Correctable Codes.	CCC	2010	DBLP DOI BibTeX RDF	complexity, arithmetic circuits, matrices
1	Mohammad Mahmoody, David Xiao	On the Power of Randomized Reductions and the Checkability of SAT.	CCC	2010	DBLP DOI BibTeX RDF	Colusure, Instance Checkers, Complexity, Randomization
1	Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan	A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions.	CCC	2010	DBLP DOI BibTeX RDF	Boolean function, regularity lemma, polynomial threshold function
1	Parikshit Gopalan, Ryan O'Donnell, Yi Wu 0002, David Zuckerman	Fooling Functions of Halfspaces under Product Distributions.	CCC	2010	DBLP DOI BibTeX RDF	Pseudorandness, complexity theory, halfspace
1	Alexandra Kolla	Spectral Algorithms for Unique Games.	CCC	2010	DBLP DOI BibTeX RDF
1	Matei David, Periklis A. Papakonstantinou	Trade-Off Lower Bounds for Stack Machines.	CCC	2010	DBLP DOI BibTeX RDF	AuxPDA, lower bound, streaming, communication complexity, stack, reversals, space bound
1	Dan Gutfreund, Akinori Kawachi	Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.	CCC	2010	DBLP DOI BibTeX RDF	Arthur-Merlin protocols, derandomization, circuit complexity, approximate counting
1	Luca Trevisan	The Program-Enumeration Bottleneck in Average-Case Complexity Theory.	CCC	2010	DBLP DOI BibTeX RDF	Universal Search, Average-case Complexity
1	Matt DeVos, Ariel Gabizon	Simple Affine Extractors Using Dimension Expansion.	CCC	2010	DBLP DOI BibTeX RDF	affine extractors, dimension expansion, derandomization, Extractors, pseudorandomness
1	Dániel Marx	Completely Inapproximable Monotone and Antimonotone Parameterized Problems.	CCC	2010	DBLP DOI BibTeX RDF	parameterized comlexity, approximation, fixed-parameter tractability, inapproximability
1	Eric Allender, Klaus-Jörn Lange	Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.	CCC	2010	DBLP DOI BibTeX RDF	Symmetric Computation, Auxiliary Pushdown Automata, LogCFL, Reversible Computation
1	Eric Blais, Ryan O'Donnell	Lower Bounds for Testing Function Isomorphism.	CCC	2010	DBLP DOI BibTeX RDF	lower bounds, Boolean functions, property testing
1	Ran Raz	Parallel Repetition of Two Prover Games (Invited Survey).	CCC	2010	DBLP DOI BibTeX RDF
1	Derrick Stolee, Chris Bourke, N. V. Vinodchandran	A Log-Space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources.	CCC	2010	DBLP DOI BibTeX RDF	acyclic digraph, logspace algorithm, planar graph, reachability
1	Irit Dinur, Or Meir	Derandomized Parallel Repetition of Structured PCPs.	CCC	2010	DBLP DOI BibTeX RDF	Low error, Direct Product Test, Derandomized Parallel Repetition, PCP, Direct Product, de-Bruijn
1	Subhash Khot	On the Unique Games Conjecture (Invited Survey).	CCC	2010	DBLP DOI BibTeX RDF
1	Jakob Nordström	On the Relative Strength of Pebbling and Resolution.	CCC	2010	DBLP DOI BibTeX RDF	pebbling formula, resolution, space, trade-off, proof complexity, pebble games
1	Iftach Haitner, Mohammad Mahmoody, David Xiao	A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP.	CCC	2010	DBLP DOI BibTeX RDF	sampling protocols, constant-round statistically hiding commitments, black-box lower bounds, collision-resistant hash functions
1	Julia Kempe, Oded Regev 0001	No Strong Parallel Repetition with Entangled and Non-signaling Provers.	CCC	2010	DBLP DOI BibTeX RDF	entangled two-prover games, unique games, parallel repetition
1	Pavel Hrubes, Avi Wigderson, Amir Yehudayoff	Relationless Completeness and Separations.	CCC	2010	DBLP DOI BibTeX RDF	Completeness, Separations, Algebraic complexity
1	Daniel M. Kane	The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions.	CCC	2010	DBLP DOI BibTeX RDF
1	Harry Buhrman, Lance Fortnow, Michal Koucký 0001, Bruno Loff	Derandomizing from Random Strings.	CCC	2010	DBLP DOI BibTeX RDF	Truth-table Reducibility, Kolmogorov Complexity, Derandomization
1	Russell Impagliazzo, Ryan Williams 0001	Communication Complexity with Synchronized Clocks.	CCC	2010	DBLP DOI BibTeX RDF	time-communication tradeoffs, lower bounds, communication complexity
1	Rahul Jain 0001, Hartmut Klauck	The Partition Bound for Classical Communication Complexity and Query Complexity.	CCC	2010	DBLP DOI BibTeX RDF	Partition Bound, Lower Bounds, Linear Programming, Communication Complexity, Query Complexity
1		Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010	CCC	2010	DBLP BibTeX RDF
1	Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan 0001, Michael Viderman	Locally Testable Codes Require Redundant Testers.	CCC	2009	DBLP DOI BibTeX RDF
1	Kristoffer Arnsfelt Hansen, Michal Koucký 0001	A New Characterization of ACC0 and Probabilistic CC0.	CCC	2009	DBLP DOI BibTeX RDF
1	Nitin Saxena 0001, C. Seshadhri 0001	An Almost Optimal Rank Bound for Depth-3 Identities.	CCC	2009	DBLP DOI BibTeX RDF
1	Pavel Hrubes, Iddo Tzameret	The Proof Complexity of Polynomial Identities.	CCC	2009	DBLP DOI BibTeX RDF
1	Neeraj Kayal	The Complexity of the Annihilating Polynomial.	CCC	2009	DBLP DOI BibTeX RDF
1	Guy N. Rothblum, Salil P. Vadhan	Are PCPs Inherent in Efficient Arguments?	CCC	2009	DBLP DOI BibTeX RDF
1	Troy Lee, Adi Shraibman	An Approximation Algorithm for Approximation Rank.	CCC	2009	DBLP DOI BibTeX RDF
1	Zeev Dvir	Extractors for Varieties.	CCC	2009	DBLP DOI BibTeX RDF
1	Per Austrin, Subhash Khot, Muli Safra	Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.	CCC	2009	DBLP DOI BibTeX RDF
1	Troy Lee, Gideon Schechtman, Adi Shraibman	Lower Bounds on Quantum Multiparty Communication Complexity.	CCC	2009	DBLP DOI BibTeX RDF
1	Mark Braverman	Poly-logarithmic Independence Fools AC0 Circuits.	CCC	2009	DBLP DOI BibTeX RDF
1	Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan	Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.	CCC	2009	DBLP DOI BibTeX RDF
1	Andrew Drucker	Multitask Efficiencies in the Decision Tree Model.	CCC	2009	DBLP DOI BibTeX RDF
1	Ronen Shaltiel	Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma.	CCC	2009	DBLP DOI BibTeX RDF
1	Zohar Shay Karnin, Amir Shpilka	Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in.	CCC	2009	DBLP DOI BibTeX RDF
1	Parikshit Gopalan, Shachar Lovett, Amir Shpilka	On the Complexity of Boolean Functions in Different Characteristics.	CCC	2009	DBLP DOI BibTeX RDF
1	Kazuyuki Amano	k-Subgraph Isomorphism on AC0 Circuits.	CCC	2009	DBLP DOI BibTeX RDF
1	Pascal Koiran, Sylvain Perifel	A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent.	CCC	2009	DBLP DOI BibTeX RDF
1	Luis Filipe Coelho Antunes, Lance Fortnow	Worst-Case Running Times for Average-Case Algorithms.	CCC	2009	DBLP DOI BibTeX RDF
1	Ilias Diakonikolas, Rocco A. Servedio	Improved Approximation of Linear Threshold Functions.	CCC	2009	DBLP DOI BibTeX RDF
1	Nikos Leonardos, Michael E. Saks	Lower Bounds on the Randomized Communication Complexity of Read-Once Functions.	CCC	2009	DBLP DOI BibTeX RDF
1	Anup Rao 0001	Extractors for Low-Weight Affine Sources.	CCC	2009	DBLP DOI BibTeX RDF
1	Adam R. Day	Increasing the Gap between Descriptional Complexity and Algorithmic Probability.	CCC	2009	DBLP DOI BibTeX RDF
1	Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto	Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies.	CCC	2009	DBLP DOI BibTeX RDF
1		Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009	CCC	2009	DBLP BibTeX RDF
1	Manindra Agrawal, Osamu Watanabe 0001	One-Way Functions and the Berman-Hartmanis Conjecture.	CCC	2009	DBLP DOI BibTeX RDF
1	Scott Aaronson	Quantum Copy-Protection and Quantum Money.	CCC	2009	DBLP DOI BibTeX RDF
1	Lance Fortnow, Rahul Santhanam, Ryan Williams 0001	Fixed-Polynomial Size Circuit Bounds.	CCC	2009	DBLP DOI BibTeX RDF
1	T. S. Jayram, Swastik Kopparty, Prasad Raghavendra	On the Communication Complexity of Read-Once AC^0 Formulae.	CCC	2009	DBLP DOI BibTeX RDF
1	Richard Královic	Infinite vs. Finite Space-Bounded Randomized Computations.	CCC	2009	DBLP DOI BibTeX RDF
1	Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran	Every Permutation CSP of arity 3 is Approximation Resistant.	CCC	2009	DBLP DOI BibTeX RDF
1	Akitoshi Kawamura	Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete.	CCC	2009	DBLP DOI BibTeX RDF
1	Rahul Jain 0001, Hartmut Klauck	New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques.	CCC	2009	DBLP DOI BibTeX RDF
1	Rahul Jain 0001, John Watrous	Parallel Approximation of Non-interactive Zero-sum Quantum Games.	CCC	2009	DBLP DOI BibTeX RDF
1	Joshua Brody	The Maximum Communication Complexity of Multi-Party Pointer Jumping.	CCC	2009	DBLP DOI BibTeX RDF
1	Joshua Brody, Amit Chakrabarti	A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences.	CCC	2009	DBLP DOI BibTeX RDF
1	David Xiao	On Basing ZK ≠ BPP on the Hardness of PAC Learning.	CCC	2009	DBLP DOI BibTeX RDF
1	Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner	Planar Graph Isomorphism is in Log-Space.	CCC	2009	DBLP DOI BibTeX RDF
1	Nati Linial, Adi Shraibman	Learning Complexity vs. Communication Complexity.	CCC	2008	DBLP DOI BibTeX RDF	large margin classifiers, communication complexity, discrepancy, rigidity
1	Erik D. Demaine, Robert A. Hearn	Constraint Logic: A Uniform Framework for Modeling Computation as Games.	CCC	2008	DBLP DOI BibTeX RDF	games, undecidability, hardness
1	Elena Grigorescu, Tali Kaufman, Madhu Sudan 0001	2-Transitivity Is Insufficient for Local Testability.	CCC	2008	DBLP DOI BibTeX RDF	error correcting codes, property testing, sublinear time algorithms
1	Zeev Dvir, Amir Shpilka	Towards Dimension Expanders over Finite Fields.	CCC	2008	DBLP DOI BibTeX RDF	Cayley graphs, expanders, explicit constructions
1	Troy Lee, Adi Shraibman	Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model.	CCC	2008	DBLP DOI BibTeX RDF	multiparty communication complexity, disjointness, lower bounds
1	Emanuele Viola	The Sum of d Small-Bias Generators Fools Polynomials of Degree d.	CCC	2008	DBLP DOI BibTeX RDF
1	Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun 0001, Andrew Chi-Chih Yao	Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems.	CCC	2008	DBLP DOI BibTeX RDF	multi-prover interactive proof systems, quantum nonlocality, Tsirelson inequality, entanglement
1	Parikshit Gopalan, Venkatesan Guruswami	Hardness Amplification within NP against Deterministic Algorithms.	CCC	2008	DBLP DOI BibTeX RDF	Hardness Amplication, Error-Correcting Codes, Derandomization, NP
1	Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, Stephanie Wehner	The Quantum Moment Problem and Bounds on Entangled Multi-prover Games.	CCC	2008	DBLP DOI BibTeX RDF	quantum entanglement, nonlocal games, multi-prover interactive proof systems
1	Harry Buhrman, Michal Koucký 0001, Nikolai K. Vereshchagin	Randomised Individual Communication Complexity.	CCC	2008	DBLP DOI BibTeX RDF	individual communication complexity, Kolmogorov complexity, rounds, randomized protocols
1	Alexander A. Sherstov	Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions.	CCC	2008	DBLP DOI BibTeX RDF	Approximate inclusion/exclusion, approximate degree of Boolean functions, linear-programming duality, Chebyshev polynomials
1	Kord Eickmeyer, Martin Grohe, Magdalena Grüber	Approximation of Natural W[P]-Complete Minimisation Problems Is Hard.	CCC	2008	DBLP DOI BibTeX RDF	derandomisation, parameterized complexity, inapproximability
1	Richard Chang 0001, Suresh Purini	Amplifying ZPP^SAT[1] and the Two Queries Problem.	CCC	2008	DBLP DOI BibTeX RDF	ZPP, amplification, bounded queries
1	Swastik Kopparty, Sergey Yekhanin	Detecting Rational Points on Hypersurfaces over Finite Fields.	CCC	2008	DBLP DOI BibTeX RDF	Chevalley-Warning Theorem, Lang-Weil Theorem, Nonsingular Spaces of Matrices, Polynomial Identity Testing
1	Kiran S. Kedlaya, Sergey Yekhanin	Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers.	CCC	2008	DBLP DOI BibTeX RDF	Locally decodable codes, Mersenne primes
1	Dmitry Gavinsky, Pavel Pudlák	Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity.	CCC	2008	DBLP DOI BibTeX RDF	separation of communication classes, communication complexity, quantum communication
1	Harry Buhrman, John M. Hitchcock	NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly.	CCC	2008	DBLP DOI BibTeX RDF	hard sets, polynomial advice, instance complexity
1		Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA	CCC	2008	DBLP BibTeX RDF
1	Ran Raz, Amir Yehudayoff	Lower Bounds and Separations for Constant Depth Multilinear Circuits.	CCC	2008	DBLP DOI BibTeX RDF	Constant Depth, Lower Bounds, Separations, Arithmetic Circuits
1	Per Austrin, Elchanan Mossel	Approximation Resistant Predicates from Pairwise Independence.	CCC	2008	DBLP DOI BibTeX RDF	Max k-CSP, Approximation Resistance, Pairwise Independence, Unique Games Conjecture
1	Alexander A. Sherstov	Communication Complexity under Product and Nonproduct Distributions.	CCC	2008	DBLP DOI BibTeX RDF	Randomized/distributional communication complexity, product/nonproduct distributions, Yao's Minimax Principle

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