Search results for "CCC"

Hits ?▲	Authors	Title	Venue	Year	Link
1		IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014	CCC	2014	DBLP BibTeX RDF
1	Ryan Williams 0001	Algorithms for Circuits and Circuits for Algorithms.	CCC	2014	DBLP DOI BibTeX RDF
1	Swastik Kopparty, Shubhangi Saraf, Amir Shpilka	Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.	CCC	2014	DBLP DOI BibTeX RDF
1	James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan 0002	On the Power of Symmetric LP and SDP Relaxations.	CCC	2014	DBLP DOI BibTeX RDF
1	Karl Wimmer	Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates.	CCC	2014	DBLP DOI BibTeX RDF
1	Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz	AM with Multiple Merlins.	CCC	2014	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Chaoping Xing	Hitting Sets for Low-Degree Polynomials with Optimal Density.	CCC	2014	DBLP DOI BibTeX RDF
1	Aleksandrs Belovs	Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound.	CCC	2014	DBLP DOI BibTeX RDF
1	Arturs Backurs, Mohammad Bavarian	On the Sum of L1 Influences.	CCC	2014	DBLP DOI BibTeX RDF
1	Rahul Jain 0001, Attila Pereszlényi, Penghui Yao	A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions.	CCC	2014	DBLP DOI BibTeX RDF
1	Anindya De, Ilias Diakonikolas, Rocco A. Servedio	Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.	CCC	2014	DBLP DOI BibTeX RDF
1	Albert Atserias, Massimo Lauria, Jakob Nordström	Narrow Proofs May Be Maximally Long.	CCC	2014	DBLP DOI BibTeX RDF
1	Bruno Bauwens, Marius Zimand	Linear List-Approximation for Short Programs (or the Power of a Few Random Bits).	CCC	2014	DBLP DOI BibTeX RDF
1	Simon Straub, Thomas Thierauf, Fabian Wagner	Counting the Number of Perfect Matchings in K5-Free Graphs.	CCC	2014	DBLP DOI BibTeX RDF
1	Aleksandrs Belovs, Ansis Rosmanis	On the Power of Non-adaptive Learning Graphs.	CCC	2013	DBLP DOI BibTeX RDF
1	Andris Ambainis, Ronald de Wolf	How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?	CCC	2013	DBLP DOI BibTeX RDF
1	Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira	Constructing Hard Functions Using Learning Algorithms.	CCC	2013	DBLP DOI BibTeX RDF
1	Patrick M. Hayden, Kevin Milner, Mark M. Wilde	Two-Message Quantum Interactive Proofs and the Quantum Separability Problem.	CCC	2013	DBLP DOI BibTeX RDF
1	Albert Atserias, Moritz Müller, Sergi Oliva	Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle.	CCC	2013	DBLP DOI BibTeX RDF
1	Siu Man Chan	Just a Pebble Game.	CCC	2013	DBLP DOI BibTeX RDF
1	Luca Trevisan, Tongke Xue	A Derandomized Switching Lemma and an Improved Derandomization of AC0.	CCC	2013	DBLP DOI BibTeX RDF
1	John P. Steinberger	The Distinguishability of Product Distributions by Read-Once Branching Programs.	CCC	2013	DBLP DOI BibTeX RDF
1	Sepp Hartung, André Nichterlein	On the Parameterized and Approximation Hardness of Metric Dimension.	CCC	2013	DBLP DOI BibTeX RDF
1	Sushant Sachdeva, Rishi Saket	Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover.	CCC	2013	DBLP DOI BibTeX RDF
1	Rahul Santhanam, Ryan Williams 0001	On Medium-Uniformity and Circuit Lower Bounds.	CCC	2013	DBLP DOI BibTeX RDF
1	Justin Gilmer, Michael E. Saks, Srikanth Srinivasan 0001	Composition Limits and Separating Examples for Some Boolean Function Complexity Measures.	CCC	2013	DBLP DOI BibTeX RDF
1	Daniel M. Kane	The Correct Exponent for the Gotsman-Linial Conjecture.	CCC	2013	DBLP DOI BibTeX RDF
1	Noga Alon, Gil Cohen	On Rigid Matrices and U-polynomials.	CCC	2013	DBLP DOI BibTeX RDF
1	Ankit Gupta 0001, Neeraj Kayal, Youming Qiao	Random Arithmetic Formulas Can Be Reconstructed Efficiently.	CCC	2013	DBLP DOI BibTeX RDF
1	Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang	Shared Randomness and Quantum Communication in the Multi-party Model.	CCC	2013	DBLP DOI BibTeX RDF
1	Michael Viderman	Strong LTCs with Inverse Polylogarithmic Rate and Soundness.	CCC	2013	DBLP DOI BibTeX RDF
1	Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand	Short Lists with Short Programs in Short Time.	CCC	2013	DBLP DOI BibTeX RDF
1	Ankit Gupta 0001, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi	Approaching the Chasm at Depth Four.	CCC	2013	DBLP DOI BibTeX RDF
1		Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013	CCC	2013	DBLP BibTeX RDF
1	Eric Blais, Li-Yang Tan	Approximating Boolean Functions with Depth-2 Circuits.	CCC	2013	DBLP DOI BibTeX RDF
1	Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, Chris Peikert	On the Lattice Smoothing Parameter Problem.	CCC	2013	DBLP DOI BibTeX RDF
1	Madhur Tulsiani, Pratik Worah	LS+ Lower Bounds from Pairwise Independence.	CCC	2013	DBLP DOI BibTeX RDF
1	Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe 0001	An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability.	CCC	2013	DBLP DOI BibTeX RDF
1	Irit Dinur, Gillat Kol	Covering CSPs.	CCC	2013	DBLP DOI BibTeX RDF
1	Yasuhiro Takahashi, Seiichiro Tani	Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits.	CCC	2013	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Krzysztof Onak	Superlinear Lower Bounds for Multipass Graph Processing.	CCC	2013	DBLP DOI BibTeX RDF
1	Pavel Hrubes, Amir Yehudayoff	Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting.	CCC	2013	DBLP DOI BibTeX RDF
1	Joshua Brody, Harry Buhrman, Michal Koucký 0001, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin	Towards a Reverse Newman's Theorem in Interactive Information Complexity.	CCC	2013	DBLP DOI BibTeX RDF
1	Oded Regev 0001, Thomas Vidick	Quantum XOR Games.	CCC	2013	DBLP DOI BibTeX RDF
1	Gil Cohen, Ran Raz, Gil Segev 0001	Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification.	CCC	2012	DBLP DOI BibTeX RDF
1	Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe 0001	Is Valiant-Vazirani's Isolation Probability Improvable?	CCC	2012	DBLP DOI BibTeX RDF
1	Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Ilan Orlov	Share Conversion and Private Information Retrieval.	CCC	2012	DBLP DOI BibTeX RDF
1	Dmitry Gavinsky	Quantum Money with Classical Verification.	CCC	2012	DBLP DOI BibTeX RDF
1	Joshua A. Grochow	Matrix Isomorphism of Matrix Lie Algebras.	CCC	2012	DBLP DOI BibTeX RDF
1	Guy Moshkovitz	Complexity Lower Bounds through Balanced Graph Properties.	CCC	2012	DBLP DOI BibTeX RDF
1	André Chailloux, Or Sattath	The Complexity of the Separable Hamiltonian Problem.	CCC	2012	DBLP DOI BibTeX RDF
1	Chi-Jen Lu	Hitting Set Generators for Sparse Polynomials over Any Finite Fields.	CCC	2012	DBLP DOI BibTeX RDF
1	Samuel R. Buss, Ryan Williams 0001	Limits on Alternation-Trading Proofs for Time-Space Lower Bounds.	CCC	2012	DBLP DOI BibTeX RDF
1	Prasad Raghavendra, David Steurer, Madhur Tulsiani	Reductions between Expansion Problems.	CCC	2012	DBLP DOI BibTeX RDF
1	Amnon Ta-Shma, Christopher Umans	Better Condensers and New Extractors from Parvaresh-Vardy Codes.	CCC	2012	DBLP DOI BibTeX RDF
1	Per Austrin, Johan Håstad	On the Usefulness of Predicates.	CCC	2012	DBLP DOI BibTeX RDF
1	Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký 0001, Toniann Pitassi	The Hardness of Being Private.	CCC	2012	DBLP DOI BibTeX RDF
1	Noga Alon, Amir Shpilka, Christopher Umans	On Sunflowers and Matrix Multiplication.	CCC	2012	DBLP DOI BibTeX RDF
1	Sourav Chakraborty 0001, Eldar Fischer, David García-Soriano, Arie Matsliah	Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching.	CCC	2012	DBLP DOI BibTeX RDF
1	Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan 0001	Pseudorandom Generators for Read-Once ACC^0.	CCC	2012	DBLP DOI BibTeX RDF
1	Troy Lee, Jérémie Roland	A Strong Direct Product Theorem for Quantum Query Complexity.	CCC	2012	DBLP DOI BibTeX RDF
1	Sangxia Huang, Pinyan Lu	A Dichotomy for Real Weighted Holant Problems.	CCC	2012	DBLP DOI BibTeX RDF
1	Andrew Drucker	Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators.	CCC	2012	DBLP DOI BibTeX RDF
1	Baris Aydinlioglu, Dieter van Melkebeek	Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games.	CCC	2012	DBLP DOI BibTeX RDF
1	Gus Gutoski, Xiaodi Wu	Parallel Approximation of Min-max Problems with Applications to Classical and Quantum Zero-Sum Games.	CCC	2012	DBLP DOI BibTeX RDF
1	Toniann Pitassi	Communication Complexity and Information Complexity: Foundations and New Directions.	CCC	2012	DBLP DOI BibTeX RDF
1	Paul Beame, Russell Impagliazzo, Srikanth Srinivasan 0001	Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT.	CCC	2012	DBLP DOI BibTeX RDF
1	Yuichi Yoshida	Testing List H-homomorphisms.	CCC	2012	DBLP DOI BibTeX RDF
1	Peter Bürgisser	Prospects for Geometric Complexity Theory.	CCC	2012	DBLP DOI BibTeX RDF
1		Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012	CCC	2012	DBLP BibTeX RDF
1	Derrick Stolee, N. V. Vinodchandran	Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs.	CCC	2012	DBLP DOI BibTeX RDF
1	Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh 0001, Magnus Wahlström	On Problems as Hard as CNF-SAT.	CCC	2012	DBLP DOI BibTeX RDF
1	Elena Grigorescu, Chris Peikert	List Decoding Barnes-Wall Lattices.	CCC	2012	DBLP DOI BibTeX RDF
1	Parikshit Gopalan, Raghu Meka, Omer Reingold	DNF Sparsification and a Faster Deterministic Counting Algorithm.	CCC	2012	DBLP DOI BibTeX RDF
1	Or Meir	Combinatorial PCPs with Short Proofs.	CCC	2012	DBLP DOI BibTeX RDF
1	Kazuhisa Seto, Suguru Tamaki	A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis.	CCC	2012	DBLP DOI BibTeX RDF
1	Ran Raz, Ricky Rosen	A Strong Parallel Repetition Theorem for Projection Games on Expanders.	CCC	2012	DBLP DOI BibTeX RDF
1	Guy Kindler, Ryan O'Donnell	Gaussian Noise Sensitivity and Fourier Tails.	CCC	2012	DBLP DOI BibTeX RDF
1	Markus Bläser, Bekhan Chokaev	Algebras of Minimal Multiplicative Complexity.	CCC	2012	DBLP DOI BibTeX RDF
1	Richard J. Lipton, Ryan Williams 0001	Amplifying Circuit Lower Bounds against Polynomial Time with Applications.	CCC	2012	DBLP DOI BibTeX RDF
1	Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Ron-Zewi	Space Complexity in Polynomial Calculus.	CCC	2012	DBLP DOI BibTeX RDF
1	Xin Li 0006	Improved Constructions of Three Source Extractors.	CCC	2011	DBLP DOI BibTeX RDF
1	Daniel M. Kane	k-Independent Gaussians Fool Polynomial Threshold Functions.	CCC	2011	DBLP DOI BibTeX RDF
1	Boris Alexeev, Michael A. Forbes 0001, Jacob Tsimerman	Tensor Rank: Some Lower and Upper Bounds.	CCC	2011	DBLP DOI BibTeX RDF
1	Harry Buhrman, Oded Regev 0001, Giannicola Scarpa, Ronald de Wolf	Near-Optimal and Explicit Bell Inequality Violations.	CCC	2011	DBLP DOI BibTeX RDF
1		Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011	CCC	2011	DBLP BibTeX RDF
1	Jin-yi Cai, Xi Chen 0001, Pinyan Lu	Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.	CCC	2011	DBLP DOI BibTeX RDF
1	Shubhangi Saraf, Sergey Yekhanin	Noisy Interpolation of Sparse Polynomials, and Applications.	CCC	2011	DBLP DOI BibTeX RDF
1	Ryan O'Donnell, Yi Wu 0002, Yuan Zhou 0007	Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups.	CCC	2011	DBLP DOI BibTeX RDF
1	Amir Shpilka, Avishay Tal	On the Minimal Fourier Degree of Symmetric Boolean Functions.	CCC	2011	DBLP DOI BibTeX RDF
1	Sevag Gharibian, Julia Kempe	Approximation Algorithms for QMA-Complete Problems.	CCC	2011	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson, Michael Viderman	Towards Lower Bounds on Locally Testable Codes via Density Arguments.	CCC	2011	DBLP DOI BibTeX RDF
1	Hartmut Klauck	On Arthur Merlin Games in Communication Complexity.	CCC	2011	DBLP DOI BibTeX RDF
1	Russell Impagliazzo	Relativized Separations of Worst-Case and Average-Case Complexities for NP.	CCC	2011	DBLP DOI BibTeX RDF
1	Eric Blais, Joshua Brody, Kevin Matulef	Property Testing Lower Bounds via Communication Complexity.	CCC	2011	DBLP DOI BibTeX RDF
1	Anindya De	Pseudorandomness for Permutation and Regular Branching Programs.	CCC	2011	DBLP DOI BibTeX RDF
1	Ryan Williams 0001	Non-uniform ACC Circuit Lower Bounds.	CCC	2011	DBLP DOI BibTeX RDF
1	Marius Zimand	Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors.	CCC	2011	DBLP DOI BibTeX RDF
1	Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich	Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.	CCC	2011	DBLP DOI BibTeX RDF
1	Lorenzo Carlucci, Nicola Galesi, Massimo Lauria	Paris-Harrington Tautologies.	CCC	2011	DBLP DOI BibTeX RDF

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