TDG
Scholar
Committed to research!
Version 1.7
Home

Bibliography

Writers

Journals

Conferences

Publishers
Help

News
Bibliography
Refine on click

Report

Share
More than 125 records were found in 0.719 seconds
Fetch

Report

Google
Parameterized Intractability of Even Set and Shortest Vector Problem from GapETH
Arnab Bhattacharyya
,
Suprovat Ghoshal
,
Karthik C. S.
,
Pasin Manurangsi
Electronic Colloquium on Computational Complexity (ECCC)
,
2557
,
2018
Fetch

Report

Google
Sampling lower bounds: boolean averagecase and permutations
Emanuele Viola
Electronic Colloquium on Computational Complexity (ECCC)
,
2560
,
2018
Fetch

Report

Google
Generalized comparison trees for pointlocation problems
Daniel M. Kane
,
Shachar Lovett
,
Shay Moran
Electronic Colloquium on Computational Complexity (ECCC)
,
2574
,
2018
Fetch

Report

Google
Edge Hop: A Framework to Show NPHardness of Combinatorial Games
Moritz Gobbert
Electronic Colloquium on Computational Complexity (ECCC)
,
2580
,
2018
Fetch

Report

Google
Hard satisfiable formulas for splittings by linear combinations
Dmitry Itsykson
,
Alexander Knop
Electronic Colloquium on Computational Complexity (ECCC)
,
24117
,
2017
Fetch

Report

Google
High Degree Sum of Squares Proofs, BienstockZuckerberg hierarchy and ChvatalGomory cuts
Monaldo Mastrolilli
Electronic Colloquium on Computational Complexity (ECCC)
,
24157
,
2017
Fetch

Report

Google
From Laconic ZeroKnowledge to PublicKey Cryptography
Itay Berman
,
Akshay Degwekar
,
Ron Rothblum
,
Prashant Nalini Vasudevan
Electronic Colloquium on Computational Complexity (ECCC)
,
24172
,
2017
Fetch

Report

Google
Worstcase to Averagecase reductions for subclasses of P
Oded Goldreich 0001
,
Guy N. Rothblum
Electronic Colloquium on Computational Complexity (ECCC)
,
24130
,
2017
Fetch

Report

Google
A Survey of Classes of Primitive Recursive Functions
Stephen A. Cook
,
Bruce M. Kapron
Electronic Colloquium on Computational Complexity (ECCC)
,
241
,
2017
Fetch

Report

Google
Some notes on two lower bound methods for communication complexity
Frantisek Duris
Electronic Colloquium on Computational Complexity (ECCC)
,
242
,
2017
Fetch

Report

Google
P=?NP
Scott Aaronson
Electronic Colloquium on Computational Complexity (ECCC)
,
244
,
2017
Fetch

Report

Google
Magic Adversaries Versus Individual Reduction: Science Wins Either Way
Yi Deng
Electronic Colloquium on Computational Complexity (ECCC)
,
243
,
2017
Fetch

Report

Google
An averagecase depth hierarchy theorem for higher depth
Johan Håstad
Electronic Colloquium on Computational Complexity (ECCC)
,
2341
,
2016
Fetch

Report

Google
Randomness Extraction in AC
^{0}
and with Small Locality
Kuan Cheng
,
Xin Li 0006
Electronic Colloquium on Computational Complexity (ECCC)
,
2318
,
2016
Fetch

Report

Google
The uniform distribution is complete with respect to testing identity to a fixed distribution
Oded Goldreich
Electronic Colloquium on Computational Complexity (ECCC)
,
2315
,
2016
Fetch

Report

Google
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling
Zachary Remscrim
Electronic Colloquium on Computational Complexity (ECCC)
,
2320
,
2016
Fetch

Report

Google
Pseudorandomness when the odds are against you
Sergei Artemenko
,
Russell Impagliazzo
,
Valentine Kabanets
,
Ronen Shaltiel
Electronic Colloquium on Computational Complexity (ECCC)
,
2337
,
2016
Fetch

Report

Google
Algorithms from Natural Lower Bounds
Marco L. Carmosino
,
Russell Impagliazzo
,
Valentine Kabanets
,
Antonina Kolokolova
Electronic Colloquium on Computational Complexity (ECCC)
,
238
,
2016
Fetch

Report

Google
Further extensions of Clifford circuits and their classical simulation complexities
Dax Enshan Koh
Electronic Colloquium on Computational Complexity (ECCC)
,
234
,
2016
Fetch

Report

Google
Dependency Schemes in QBF Calculi: Semantics and Soundness
Olaf Beyersdorff
,
Joshua Blinkhorn
Electronic Colloquium on Computational Complexity (ECCC)
,
2328
,
2016
Fetch

Report

Google
Complexity of Constraint Satisfaction Problems over Finite Substsets of Natural Numbers
Titus Dose
Electronic Colloquium on Computational Complexity (ECCC)
,
2331
,
2016
Fetch

Report

Google
Identity Testing for constantwidth, and commutative, readonce oblivious ABPs
Rohit Gurjar
,
Arpita Korwar
,
Nitin Saxena
Electronic Colloquium on Computational Complexity (ECCC)
,
239
,
2016
Fetch

Report

Google
Extractors for Near Logarithmic MinEntropy
Gil Cohen
,
Leonard J. Schulman
Electronic Colloquium on Computational Complexity (ECCC)
,
2314
,
2016
Fetch

Report

Google
SolutionGraphs of Boolean Formulas and Isomorphism
Patrick Scharpfenecker
,
Jacobo Torán
Electronic Colloquium on Computational Complexity (ECCC)
,
2324
,
2016
Fetch

Report

Google
Circuit size lower bounds and #SAT upper bounds through a general framework
Alexander Golovnev
,
Alexander S. Kulikov
,
Alexander Smal
,
Suguru Tamaki
Electronic Colloquium on Computational Complexity (ECCC)
,
2322
,
2016
Fetch

Report

Google
A Note on Tolerant Testing with OneSided Error
Roei Tell
Electronic Colloquium on Computational Complexity (ECCC)
,
2332
,
2016
Fetch

Report

Google
Noisy population recovery in polynomial time
Anindya De
,
Michael E. Saks
,
Sijian Tang
Electronic Colloquium on Computational Complexity (ECCC)
,
2326
,
2016
Fetch

Report

Google
Universal Locally Testable Codes
Oded Goldreich
,
Tom Gur
Electronic Colloquium on Computational Complexity (ECCC)
,
2342
,
2016
Fetch

Report

Google
Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck
Eli BenSasson
,
Alessandro Chiesa
,
Ariel Gabizon
,
Michael Riabzev
,
Nicholas Spooner
Electronic Colloquium on Computational Complexity (ECCC)
,
2346
,
2016
Fetch

Report

Google
Bounds on the Kolmogorov complexity function for infinite words
Ludwig Staiger
Electronic Colloquium on Computational Complexity (ECCC)
,
2313
,
2016
Fetch

Report

Google
Spooky Interaction and its Discontents: Compilers for Succinct TwoMessage Argument Systems
Cynthia Dwork
,
Moni Naor
,
Guy N. Rothblum
Electronic Colloquium on Computational Complexity (ECCC)
,
2349
,
2016
Fetch

Report

Google
Lifting QBF Resolution Calculi to DQBF
Olaf Beyersdorff
,
Leroy Chew
,
Renate A. Schmidt
,
Martin Suda 0001
Electronic Colloquium on Computational Complexity (ECCC)
,
2348
,
2016
Fetch

Report

Google
QuasiLinear Size Zero Knowledge from LinearAlgebraic PCPs
Eli BenSasson
,
Alessandro Chiesa
,
Ariel Gabizon
,
Madars Virza
Electronic Colloquium on Computational Complexity (ECCC)
,
231
,
2016
Fetch

Report

Google
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
Michael A. Forbes
,
Mrinal Kumar
,
Ramprasad Saptharishi
Electronic Colloquium on Computational Complexity (ECCC)
,
2345
,
2016
Fetch

Report

Google
Explicit NonMalleable Extractors, MultiSource Extractors and Almost Optimal Privacy Amplification Protocols
Eshan Chattopadhyay
,
Xin Li 0006
Electronic Colloquium on Computational Complexity (ECCC)
,
2336
,
2016
Fetch

Report

Google
Structure of protocols for XOR functions
Kaave Hosseini
,
Shachar Lovett
Electronic Colloquium on Computational Complexity (ECCC)
,
2344
,
2016
Fetch

Report

Google
Understanding Gentzen and Frege systems for QBF
Olaf Beyersdorff
,
Ján Pich
Electronic Colloquium on Computational Complexity (ECCC)
,
2311
,
2016
Fetch

Report

Google
Noisy Population Recovery from Unknown Noise
Shachar Lovett
,
Jiapeng Zhang
Electronic Colloquium on Computational Complexity (ECCC)
,
2321
,
2016
Fetch

Report

Google
Affine Relativization: Unifying the Algebrization and Relativization Barriers
Baris Aydinlioglu
,
Eric Bach
Electronic Colloquium on Computational Complexity (ECCC)
,
2340
,
2016
Fetch

Report

Google
On the Computational Complexity of MaxSAT
Mohamed El Halaby
Electronic Colloquium on Computational Complexity (ECCC)
,
2334
,
2016
Fetch

Report

Google
On the Width of SemiAlgebraic Proofs and Algorithms
Alexander A. Razborov
Electronic Colloquium on Computational Complexity (ECCC)
,
2310
,
2016
Fetch

Report

Google
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory
Meena Mahajan
,
Nitin Saurabh
Electronic Colloquium on Computational Complexity (ECCC)
,
2338
,
2016
Fetch

Report

Google
Tribes Is Hard in the Message Passing Model
Sagnik Mukhopadhyay
Electronic Colloquium on Computational Complexity (ECCC)
,
2327
,
2016
Fetch

Report

Google
Limitations of Linear Programming Techniques for Bounded Color Matchings
Georgios Stamoulis
Electronic Colloquium on Computational Complexity (ECCC)
,
2317
,
2016
Fetch

Report

Google
Doubly infinite separation of quantum information and communication
ZiWen Liu
,
Christopher Perry
,
Yechao Zhu
,
Dax Enshan Koh
,
Scott Aaronson
Electronic Colloquium on Computational Complexity (ECCC)
,
2316
,
2016
Fetch

Report

Google
New hardness results for graph and hypergraph colorings
Joshua Brakensiek
,
Venkatesan Guruswami
Electronic Colloquium on Computational Complexity (ECCC)
,
2329
,
2016
Fetch

Report

Google
The Fourier structure of low degree polynomials
Shachar Lovett
Electronic Colloquium on Computational Complexity (ECCC)
,
2325
,
2016
Fetch

Report

Google
Pseudodeterministic Constructions in Subexponential Time
Igor Carboni Oliveira
,
Rahul Santhanam
Electronic Colloquium on Computational Complexity (ECCC)
,
23196
,
2016
Fetch

Report

Google
Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials
Christian Engels
,
B. V. Raghavendra Rao
,
Karteek Sreenivasaiah
Electronic Colloquium on Computational Complexity (ECCC)
,
23153
,
2016
Fetch

Report

Google
Robust Multiplicationbased Tests for ReedMuller Codes
Prahladh Harsha
,
Srikanth Srinivasan
Electronic Colloquium on Computational Complexity (ECCC)
,
23204
,
2016
Fetch

Report

Google
Robust sensitivity
Shachar Lovett
,
Jiapeng Zhang
Electronic Colloquium on Computational Complexity (ECCC)
,
23161
,
2016
Fetch

Report

Google
A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation
Jayadev Acharya
,
Hirakendu Das
,
Alon Orlitsky
,
Ananda Theertha Suresh
Electronic Colloquium on Computational Complexity (ECCC)
,
23186
,
2016
Fetch

Report

Google
Logical Induction
Scott Garrabrant
,
Tsvi BensonTilsen
,
Andrew Critch
,
Nate Soares
,
Jessica Taylor
Electronic Colloquium on Computational Complexity (ECCC)
,
23154
,
2016
Fetch

Report

Google
Preserving Randomness for Adaptive Algorithms
William M. Hoza
,
Adam R. Klivans
Electronic Colloquium on Computational Complexity (ECCC)
,
23172
,
2016
Fetch

Report

Google
Cube vs. Cube Low Degree Test
Amey Bhangale
,
Irit Dinur
,
Inbal Livni Navon
Electronic Colloquium on Computational Complexity (ECCC)
,
23205
,
2016
Fetch

Report

Google
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
Igor Carboni Oliveira
,
Rahul Santhanam
Electronic Colloquium on Computational Complexity (ECCC)
,
23197
,
2016
Fetch

Report

Google
Complete Derandomization of Identity Testing and Reconstruction of ReadOnce Formulas
Daniel Minahan
,
Ilya Volkovich
Electronic Colloquium on Computational Complexity (ECCC)
,
23171
,
2016
Fetch

Report

Google
NonMalleable Codes and Extractors for SmallDepth Circuits, and Affine Functions
Eshan Chattopadhyay
,
Xin Li 0006
Electronic Colloquium on Computational Complexity (ECCC)
,
23180
,
2016
Fetch

Report

Google
Linear Sketching over 𝔽
_{2}
Elchanan Mossel
,
Sampath Kannan
,
Grigory Yaroslavtsev
Electronic Colloquium on Computational Complexity (ECCC)
,
23174
,
2016
Fetch

Report

Google
A Characterization of ConstantSample Testable Properties
Eric Blais
,
Yuichi Yoshida
Electronic Colloquium on Computational Complexity (ECCC)
,
23201
,
2016
Fetch

Report

Google
The weakness of CTC qubits and the power of approximate counting
Ryan O'Donnell
,
A. C. Cem Say
Electronic Colloquium on Computational Complexity (ECCC)
,
23147
,
2016
Fetch

Report

Google
Lower Bounds for Elimination via Weak Regularity
Arkadev Chattopadhyay
,
Pavel Dvorák
,
Michal Koucký
,
Bruno Loff
,
Sagnik Mukhopadhyay
Electronic Colloquium on Computational Complexity (ECCC)
,
23165
,
2016
Fetch

Report

Google
AlmostPolynomial Ratio ETHHardness of Approximating Densest kSubgraph
Pasin Manurangsi
Electronic Colloquium on Computational Complexity (ECCC)
,
23195
,
2016
Fetch

Report

Google
Identity Testing for +Regular Noncommutative Arithmetic Circuits
Vikraman Arvind
,
Pushkar S. Joglekar
,
Partha Mukhopadhyay
,
Raja S
Electronic Colloquium on Computational Complexity (ECCC)
,
23193
,
2016
Fetch

Report

Google
Trading information complexity for error
Yuval Dagan
,
Yuval Filmus
,
Hamed Hatami
,
Yaqiao Li
Electronic Colloquium on Computational Complexity (ECCC)
,
23190
,
2016
Fetch

Report

Google
On Space and Depth in Resolution
Alexander A. Razborov
Electronic Colloquium on Computational Complexity (ECCC)
,
23184
,
2016
Fetch

Report

Google
Onesided error communication complexity of Gap Hamming Distance
Egor Klenin
,
Alexander Kozachinsky
Electronic Colloquium on Computational Complexity (ECCC)
,
23173
,
2016
Fetch

Report

Google
Communication Complexity of Statistical Distance
Thomas Watson 0001
Electronic Colloquium on Computational Complexity (ECCC)
,
23170
,
2016
Fetch

Report

Google
Supercritical SpaceWidth Tradeoffs for Resolution
Christoph Berkholz
,
Jakob Nordström
Electronic Colloquium on Computational Complexity (ECCC)
,
23203
,
2016
Fetch

Report

Google
Isolation Lemma for Directed Reachability and NL vs. L
Vaibhav Krishan
,
Nutan Limaye
Electronic Colloquium on Computational Complexity (ECCC)
,
23155
,
2016
Fetch

Report

Google
Improved Bounds for Quantified Derandomization of ConstantDepth Circuits and Polynomials
Roei Tell
Electronic Colloquium on Computational Complexity (ECCC)
,
23191
,
2016
Fetch

Report

Google
Computing Majority by Constant Depth Majority Circuits with Low Fanin Gates
Alexander S. Kulikov
,
Vladimir V. Podolskii
Electronic Colloquium on Computational Complexity (ECCC)
,
23158
,
2016
Fetch

Report

Google
Lower bounds for 2query LCCs over large alphabet
Arnab Bhattacharyya
,
Sivakanth Gopi
Electronic Colloquium on Computational Complexity (ECCC)
,
23189
,
2016
Fetch

Report

Google
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
Benjamin Rossman
Electronic Colloquium on Computational Complexity (ECCC)
,
23206
,
2016
Fetch

Report

Google
Linear Matroid Intersection is in quasiNC
Rohit Gurjar
,
Thomas Thierauf
Electronic Colloquium on Computational Complexity (ECCC)
,
23182
,
2016
Fetch

Report

Google
Multiplayer parallel repetition for expander games
Irit Dinur
,
Prahladh Harsha
,
Rakesh Venkat
,
Henry Yuen
Electronic Colloquium on Computational Complexity (ECCC)
,
23160
,
2016
Fetch

Report

Google
Deconstructing 1local expanders
Oded Goldreich
Electronic Colloquium on Computational Complexity (ECCC)
,
23152
,
2016
Fetch

Report

Google
NPHardness of ReedSolomon Decoding, and the ProuhetTarryEscott Problem
Venkata Gandikota
,
Badih Ghazi
,
Elena Grigorescu
Electronic Colloquium on Computational Complexity (ECCC)
,
23176
,
2016
Fetch

Report

Google
Computing Requires Larger Formulas than Approximating
Avishay Tal
Electronic Colloquium on Computational Complexity (ECCC)
,
23179
,
2016
Fetch

Report

Google
The Bipartite Formula Complexity of InnerProduct is Quadratic
Avishay Tal
Electronic Colloquium on Computational Complexity (ECCC)
,
23181
,
2016
Fetch

Report

Google
The Optimality of Correlated Sampling
Mohammad Bavarian
,
Badih Ghazi
,
Elad Haramaty
,
Pritish Kamath
,
Ronald L. Rivest
,
Madhu Sudan
Electronic Colloquium on Computational Complexity (ECCC)
,
23194
,
2016
Fetch

Report

Google
Towards a Proof of the 2to1 Games Conjecture?
Irit Dinur
,
Subhash Khot
,
Guy Kindler
,
Dor Minzer
,
Muli Safra
Electronic Colloquium on Computational Complexity (ECCC)
,
23198
,
2016
Fetch

Report

Google
Statistical Query Lower Bounds for Robust Estimation of Highdimensional Gaussians and Gaussian Mixtures
Ilias Diakonikolas
,
Daniel M. Kane
,
Alistair Stewart
Electronic Colloquium on Computational Complexity (ECCC)
,
23177
,
2016
Fetch

Report

Google
On Probabilistic Checking in Perfect Zero Knowledge
Eli BenSasson
,
Alessandro Chiesa
,
Michael A. Forbes
,
Ariel Gabizon
,
Michael Riabzev
,
Nicholas Spooner
Electronic Colloquium on Computational Complexity (ECCC)
,
23156
,
2016
Fetch

Report

Google
New Hardness Results for the Permanent Using Linear Optics
Daniel Grier
,
Luke Schaeffer
Electronic Colloquium on Computational Complexity (ECCC)
,
23159
,
2016
Fetch

Report

Google
A security analysis of Probabilistically Checkable Proofs
Eli BenSasson
,
Iddo Bentov
,
Ariel Gabizon
,
Michael Riabzev
Electronic Colloquium on Computational Complexity (ECCC)
,
23149
,
2016
Fetch

Report

Google
On QResolution and CDCL QBF Solving
Mikolas Janota
Electronic Colloquium on Computational Complexity (ECCC)
,
2343
,
2016
Fetch

Report

Google
Autoreducibility of NPComplete Sets
John M. Hitchcock
,
Hadi Shafei
Electronic Colloquium on Computational Complexity (ECCC)
,
2312
,
2016
Fetch

Report

Google
On the logspace shortest path problem
Boris Brimkov
,
Illya V. Hicks
Electronic Colloquium on Computational Complexity (ECCC)
,
233
,
2016
Fetch

Report

Google
Parallel repetition via fortification: analytic view and the quantum case
Mohammad Bavarian
,
Thomas Vidick
,
Henry Yuen
Electronic Colloquium on Computational Complexity (ECCC)
,
2347
,
2016
Fetch

Report

Google
Tight bounds for communication assisted agreement distillation
Venkatesan Guruswami
,
Jaikumar Radhakrishnan
Electronic Colloquium on Computational Complexity (ECCC)
,
2333
,
2016
Fetch

Report

Google
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
Irit Dinur
,
Or Meir
Electronic Colloquium on Computational Complexity (ECCC)
,
2335
,
2016
Fetch

Report

Google
Complexity Classification of TwoQubit Commuting Hamiltonians
Adam Bouland
,
Laura Mancinska
,
Xue Zhang
Electronic Colloquium on Computational Complexity (ECCC)
,
2339
,
2016
Fetch

Report

Google
Extension Variables in QBF Resolution
Olaf Beyersdorff
,
Leroy Chew
,
Mikolas Janota
Electronic Colloquium on Computational Complexity (ECCC)
,
235
,
2016
Fetch

Report

Google
Strong ETH Breaks With Merlin and Arthur: Short NonInteractive Proofs of Batch Evaluation
Ryan Williams 0001
Electronic Colloquium on Computational Complexity (ECCC)
,
232
,
2016
Fetch

Report

Google
Property Testing, PCP, andJuntas
Guy Kindler
Electronic Colloquium on Computational Complexity (ECCC)
,
237
,
2016
Fetch

Report

Google
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
Neeraj Kayal
,
Chandan Saha 0001
,
Sébastien Tavenas
Electronic Colloquium on Computational Complexity (ECCC)
,
236
,
2016
Fetch

Report

Google
NonMalleable Extractors with Logarithmic Seeds
Gil Cohen
Electronic Colloquium on Computational Complexity (ECCC)
,
2330
,
2016
Fetch

Report

Google
Amortized Dynamic CellProbe Lower Bounds from FourParty Communication
Omri Weinstein
,
Huacheng Yu
Electronic Colloquium on Computational Complexity (ECCC)
,
2354
,
2016
Fetch

Report

Google
Sumofsquares hierarchy lower bounds for symmetric formulations
Adam Kurpisz
,
Samuli Leppänen
,
Monaldo Mastrolilli
Electronic Colloquium on Computational Complexity (ECCC)
,
2379
,
2016
Fetch

Report

Google
Information Theoretically Secure Databases
Gregory Valiant
,
Paul Valiant
Electronic Colloquium on Computational Complexity (ECCC)
,
2378
,
2016
Fetch

Report

Google
A Note on Teaching for VC Classes
Xi Chen
,
Yu Cheng
,
Bo Tang
Electronic Colloquium on Computational Complexity (ECCC)
,
2365
,
2016
Fetch

Report

Google
On The Sensitivity Conjecture
Avishay Tal
Electronic Colloquium on Computational Complexity (ECCC)
,
2362
,
2016
Fetch

Report

Google
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
Pavel Hubácek
,
Eylon Yogev
Electronic Colloquium on Computational Complexity (ECCC)
,
2363
,
2016
Fetch

Report

Google
Exponential Lower Bounds for Monotone Span Programs
Stephen A. Cook
,
Toniann Pitassi
,
Robert Robere
,
Benjamin Rossman
Electronic Colloquium on Computational Complexity (ECCC)
,
2364
,
2016
Fetch

Report

Google
LowSensitivity Functions from Unambiguous Certificates
Shalev BenDavid
Electronic Colloquium on Computational Complexity (ECCC)
,
2384
,
2016
Fetch

Report

Google
Making the Most of Advice: New Correlation Breakers and Their Applications
Gil Cohen
Electronic Colloquium on Computational Complexity (ECCC)
,
2352
,
2016
Fetch

Report

Google
Characterization and Lower Bounds for Branching Program Size using Projective Dimension
Dinesh Krishnamoorthy 0001
,
Sajin Koroth
,
Jayalal Sarma
Electronic Colloquium on Computational Complexity (ECCC)
,
2376
,
2016
Fetch

Report

Google
Pebbling Meets Coloring : Reversible Pebble Game On Trees
Balagopal Komarath
,
Jayalal Sarma
,
Saurabh Sawlani
Electronic Colloquium on Computational Complexity (ECCC)
,
2367
,
2016
Fetch

Report

Google
A parallel repetition theorem for all entangled games
Henry Yuen
Electronic Colloquium on Computational Complexity (ECCC)
,
2360
,
2016
Fetch

Report

Google
A New Approach for Testing Properties of Discrete Distributions
Ilias Diakonikolas
,
Daniel M. Kane
Electronic Colloquium on Computational Complexity (ECCC)
,
2374
,
2016
Fetch

Report

Google
Improved concrete efficiency and security analysis of ReedSolomon PCPPs
Eli BenSasson
,
Iddo Bentov
,
Ariel Gabizon
,
Michael Riabzev
Electronic Colloquium on Computational Complexity (ECCC)
,
2373
,
2016
Fetch

Report

Google
Orthogonal Vectors is hard for firstorder properties on sparse graphs
Jiawei Gao
,
Russell Impagliazzo
Electronic Colloquium on Computational Complexity (ECCC)
,
2353
,
2016
Fetch

Report

Google
Fast Pseudorandom Functions Based on Expander Graphs
Benny Applebaum
,
Pavel Raykov
Electronic Colloquium on Computational Complexity (ECCC)
,
2382
,
2016
Fetch

Report

Google
Degree and Sensitivity: tails of two distributions
Parikshit Gopalan
,
Rocco A. Servedio
,
Avishay Tal
,
Avi Wigderson
Electronic Colloquium on Computational Complexity (ECCC)
,
2369
,
2016
Fetch

Report

Google
Derandomizing Chernoff Bound with Union Bound with an Application to
k
wise Independent Sets
Nader H. Bshouty
Electronic Colloquium on Computational Complexity (ECCC)
,
2383
,
2016
Fetch

Report

Google
On Emulating Interactive Proofs with Public Coins
Oded Goldreich
,
Maya Leshkowitz
Electronic Colloquium on Computational Complexity (ECCC)
,
2366
,
2016
Fetch

Report

Google
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu
,
Aleksandrs Belovs
,
Shalev BenDavid
,
Mika Göös
,
Rahul Jain 0001
,
Robin Kothari
,
Troy Lee
,
Miklos Santha
Electronic Colloquium on Computational Complexity (ECCC)
,
2372
,
2016
Fetch

Report

Google
On the Communication Complexity of Approximate Fixed Points
Tim Roughgarden
,
Omri Weinstein
Electronic Colloquium on Computational Complexity (ECCC)
,
2355
,
2016
Fetch

Report

Google
On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances
Shafi Goldwasser
,
Dhiraj Holden
Electronic Colloquium on Computational Complexity (ECCC)
,
2356
,
2016
Fetch

Report

Google
Can PPAD Hardness be Based on Standard Cryptographic Assumptions?
Alon Rosen
,
Gil Segev
,
Ido Shahaf
Electronic Colloquium on Computational Complexity (ECCC)
,
2359
,
2016
Fetch

Report

Google
ConstantRound Interactive Proofs for Delegating Computation
Omer Reingold
,
Ron Rothblum
,
Guy N. Rothblum
Electronic Colloquium on Computational Complexity (ECCC)
,
2361
,
2016
Fetch

Report

Google
On Polynomial Approximations to AC
^{0}
Srikanth Srinivasan
Electronic Colloquium on Computational Complexity (ECCC)
,
2368
,
2016
Fetch

Report

Google
Total space in Resolution is at least width squared
Ilario Bonacina
Electronic Colloquium on Computational Complexity (ECCC)
,
2357
,
2016
Fetch

Report

Google
Reducing testing affine spaces to testing linearity
Oded Goldreich
Electronic Colloquium on Computational Complexity (ECCC)
,
2380
,
2016
Fetch

Report

Google
Compressing interactive communication under product distributions
Alexander A. Sherstov
Electronic Colloquium on Computational Complexity (ECCC)
,
2381
,
2016