All reports in year 2014:

__
TR14-001
| 4th January 2014
__

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka#### Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

__
TR14-002
| 8th January 2014
__

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar#### Direct Sum Testing

Revisions: 1

__
TR14-003
| 10th January 2014
__

Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka#### Testing Equivalence of Polynomials under Shifts

Revisions: 2
,
Comments: 1

__
TR14-004
| 30th November 2013
__

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty#### On $r$-Simple $k$-Path

__
TR14-005
| 14th January 2014
__

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan#### An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

__
TR14-006
| 16th January 2014
__

Venkatesan Guruswami, Euiwoong Lee#### Inapproximability of Feedback Vertex Set for Bounded Length Cycles

Revisions: 1

__
TR14-007
| 17th January 2014
__

Mark Braverman, Klim Efremenko#### List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

__
TR14-008
| 20th January 2014
__

Vinodchandran Variyam#### Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.

__
TR14-009
| 21st January 2014
__

Alexander A. Sherstov#### Breaking the Minsky-Papert Barrier for Constant-Depth Circuits

__
TR14-010
| 23rd January 2014
__

Jean Bourgain, Zeev Dvir, Ethan Leeman#### Affine extractors over large fields with exponential error

__
TR14-011
| 22nd January 2014
__

Dmitry Gavinsky, Pavel Pudlak#### Partition Expanders

__
TR14-012
| 27th January 2014
__

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz#### AM with Multiple Merlins

Revisions: 1

__
TR14-013
| 30th January 2014
__

Mark Braverman, Kanika Pasricha#### The computational hardness of pricing compound options

__
TR14-014
| 28th January 2014
__

Olaf Beyersdorff, Leroy Chew#### The Complexity of Theorem Proving in Circumscription and Minimal Entailment

__
TR14-015
| 24th January 2014
__

Jack H. Lutz, Neil Lutz#### Lines Missing Every Random Point

Revisions: 1

__
TR14-016
| 16th January 2014
__

Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz#### The Complexity of Debate Checking

__
TR14-017
| 9th February 2014
__

Eli Ben-Sasson, Emanuele Viola#### Short PCPs with projection queries

__
TR14-018
| 13th February 2014
__

Arnab Bhattacharyya#### Polynomial decompositions in polynomial time

__
TR14-019
| 14th February 2014
__

Parikshit Gopalan, Amir Yehudayoff#### Inequalities and tail bounds for elementary symmetric polynomials

__
TR14-020
| 18th February 2014
__

Pavel Hrubes, Anup Rao#### Circuits with Medium Fan-In

Revisions: 1

__
TR14-021
| 18th February 2014
__

Clement Canonne, Ronitt Rubinfeld#### Testing probability distributions underlying aggregated data

__
TR14-022
| 19th February 2014
__

Shay Moran, Makrand Sinha, Amir Yehudayoff#### Fooling Pairs in Randomized Communication Complexity

Revisions: 1

__
TR14-023
| 19th February 2014
__

Gil Cohen, Anat Ganor, Ran Raz#### Two Sides of the Coin Problem

Revisions: 1

__
TR14-024
| 19th February 2014
__

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider#### 0-1 Integer Linear Programming with a Linear Number of Constraints

__
TR14-025
| 25th February 2014
__

Oded Goldreich, Tom Gur, Ilan Komargodski#### Strong Locally Testable Codes with Relaxed Local Decoders

__
TR14-026
| 27th February 2014
__

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf#### Lower Bounds for Approximate LDCs

__
TR14-027
| 21st February 2014
__

Andris Ambainis, Krisjanis Prusis#### A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity

Revisions: 1

__
TR14-028
| 27th February 2014
__

Vikraman Arvind, S Raja#### The Complexity of Two Register and Skew Arithmetic Computation

__
TR14-029
| 4th March 2014
__

Oded Goldreich, Dana Ron#### On Learning and Testing Dynamic Environments

Revisions: 3

__
TR14-030
| 5th March 2014
__

Dana Moshkovitz#### An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing

__
TR14-031
| 16th February 2014
__

Joao Marques-Silva, Mikolas Janota#### On the Query Complexity of Selecting Few Minimal Sets

__
TR14-032
| 8th March 2014
__

Olaf Beyersdorff, Leroy Chew#### Tableau vs. Sequent Calculi for Minimal Entailment

__
TR14-033
| 10th March 2014
__

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen#### Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

__
TR14-034
| 3rd March 2014
__

Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram#### On the complexity of trial and error for constraint satisfaction problems

__
TR14-035
| 13th March 2014
__

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, Vinodchandran Variyam, Lin Yang#### New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs.

__
TR14-036
| 8th March 2014
__

Mikolas Janota, Leroy Chew, Olaf Beyersdorff#### On Unification of QBF Resolution-Based Calculi

Revisions: 1

__
TR14-037
| 21st March 2014
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Succinct and explicit circuits for sorting and connectivity

__
TR14-038
| 24th March 2014
__

Ilario Bonacina, Nicola Galesi, Neil Thapen#### Total space in resolution

Revisions: 1

__
TR14-039
| 28th March 2014
__

Andrzej Lingas#### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-)

Revisions: 1

__
TR14-040
| 30th March 2014
__

Hamed Hatami, Pooya Hatami, Shachar Lovett#### General systems of linear forms: equidistribution and true complexity

Revisions: 1

__
TR14-041
| 31st March 2014
__

Shachar Lovett#### Recent advances on the log-rank conjecture in communication complexity

__
TR14-042
| 2nd April 2014
__

Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri#### Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

__
TR14-043
| 2nd April 2014
__

Venkatesan Guruswami, Euiwoong Lee#### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

__
TR14-044
| 2nd April 2014
__

Daniel Dewey#### Additively efficient universal computers

__
TR14-045
| 7th April 2014
__

Mrinal Kumar, Shubhangi Saraf#### On the power of homogeneous depth 4 arithmetic circuits

Revisions: 2

__
TR14-046
| 8th April 2014
__

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff#### Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

__
TR14-047
| 8th April 2014
__

Mark Braverman, Omri Weinstein#### An Interactive Information Odometer with Applications

Revisions: 1

__
TR14-048
| 10th April 2014
__

Avishay Tal#### Shrinkage of De Morgan Formulae from Quantum Query Complexity

Revisions: 1

__
TR14-049
| 11th April 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication

Revisions: 1

__
TR14-050
| 21st March 2014
__

Edward Hirsch, Dmitry Sokolov#### On the probabilistic closure of the loose unambiguous hierarchy

Revisions: 1

__
TR14-051
| 12th April 2014
__

Subhash Khot, Rishi Saket#### Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

__
TR14-052
| 14th April 2014
__

Joshua Grochow, Toniann Pitassi#### Circuit complexity, proof complexity, and polynomial identity testing

__
TR14-053
| 15th April 2014
__

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman#### Computing with a full memory: Catalytic space

Revisions: 1

__
TR14-054
| 16th April 2014
__

Dana Moshkovitz#### Parallel Repetition of Fortified Games

Revisions: 2

__
TR14-055
| 17th April 2014
__

Mika Göös, Thomas Watson#### Communication Complexity of Set-Disjointness for All Probabilities

Revisions: 1

__
TR14-056
| 18th April 2014
__

Zeev Dvir, Rafael Mendes de Oliveira#### Factors of Sparse Polynomials are Sparse

Revisions: 1
,
Comments: 1

__
TR14-057
| 17th April 2014
__

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar#### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

Revisions: 3

__
TR14-058
| 20th April 2014
__

Ilya Volkovich#### On Learning, Lower Bounds and (un)Keeping Promises

__
TR14-059
| 21st April 2014
__

Boaz Barak, David Steurer#### Sum-of-squares proofs and the quest toward optimal algorithms

Revisions: 2

__
TR14-060
| 21st April 2014
__

Anup Rao, Amir Yehudayoff#### Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revisions: 1

__
TR14-061
| 21st April 2014
__

Raghav Kulkarni, Youming Qiao, Xiaoming Sun#### Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive

__
TR14-062
| 22nd March 2014
__

Alexander Kozachinsky#### On the role of private coins in unbounded-round Information Complexity

__
TR14-063
| 23rd April 2014
__

Adam Klivans, Pravesh Kothari#### Embedding Hard Learning Problems into Gaussian Space

__
TR14-064
| 24th April 2014
__

Arkadev Chattopadhyay, Michael Saks#### The Power of Super-logarithmic Number of Players

__
TR14-065
| 2nd May 2014
__

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska#### Approximate Counting of Matchings in $(3,3)$-Hypergraphs

__
TR14-066
| 17th April 2014
__

Suguru Tamaki, Yuichi Yoshida#### Robust Approximation of Temporal CSP

__
TR14-067
| 4th May 2014
__

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang#### Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

__
TR14-068
| 5th May 2014
__

Eric Allender, Bireswar Das#### Zero Knowledge and Circuit Minimization

Revisions: 1

__
TR14-069
| 5th May 2014
__

Shashank Agrawal, Divya Gupta, Hemanta Maji, Omkant Pandey, Manoj Prabhakaran#### Explicit Non-Malleable Codes Resistant to Permutations

__
TR14-070
| 14th May 2014
__

Vikraman Arvind, Gaurav Rattan#### The Complexity of Geometric Graph Isomorphism

__
TR14-071
| 7th May 2014
__

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe#### O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem

__
TR14-072
| 29th April 2014
__

Sajin Koroth, Jayalal Sarma#### Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

__
TR14-073
| 14th May 2014
__

Shachar Lovett, Cris Moore, Alexander Russell#### Group representations that resist random sampling

Revisions: 1

__
TR14-074
| 14th May 2014
__

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra#### Topology matters in communication

__
TR14-075
| 16th May 2014
__

Holger Dell#### A simple proof that AND-compression of NP-complete problems is hard

Revisions: 3

__
TR14-076
| 27th May 2014
__

Thomas Steinke#### Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs

Revisions: 1

__
TR14-077
| 2nd June 2014
__

Andris Ambainis, Jevgenijs Vihrovs#### Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma

Revisions: 2

__
TR14-078
| 7th June 2014
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

__
TR14-079
| 11th June 2014
__

Simon Straub, Thomas Thierauf, Fabian Wagner#### Counting the Number of Perfect Matchings in $K_5$-free Graphs

__
TR14-080
| 11th June 2014
__

Stasys Jukna#### Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

__
TR14-081
| 13th June 2014
__

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals#### From Small Space to Small Width in Resolution

__
TR14-082
| 3rd June 2014
__

Yu Yu, Dawu Gu, Xiangxue Li#### The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions

Revisions: 3

__
TR14-083
| 19th June 2014
__

Irit Dinur, Shafi Goldwasser, Huijia Lin#### The Computational Benefit of Correlated Instances

__
TR14-084
| 12th June 2014
__

Luke Schaeffer#### A Physically Universal Cellular Automaton

__
TR14-085
| 29th June 2014
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for ROABP and Sum of Set-Multilinear circuits

__
TR14-086
| 11th July 2014
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### Verifiable Stream Computation and Arthur–Merlin Communication

__
TR14-087
| 12th July 2014
__

Abhishek Bhowmick, Shachar Lovett#### List decoding Reed-Muller codes over small fields

Revisions: 1

__
TR14-088
| 13th July 2014
__

Swagato Sanyal#### Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

Revisions: 1
,
Comments: 1

__
TR14-089
| 16th July 2014
__

Neeraj Kayal, Chandan Saha#### Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

Revisions: 1

__
TR14-090
| 11th July 2014
__

Justin Thaler#### Semi-Streaming Algorithms for Annotated Graph Streams

Revisions: 2

__
TR14-091
| 22nd July 2014
__

Ryan O'Donnell, A. C. Cem Say#### One time-travelling bit is as good as logarithmically many

Revisions: 1

__
TR14-092
| 22nd July 2014
__

Mark Braverman, Young Kun Ko, Omri Weinstein#### Approximating the best Nash Equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis

__
TR14-093
| 22nd July 2014
__

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov#### Resolution complexity of perfect mathcing principles for sparse graphs

__
TR14-094
| 24th July 2014
__

Zeev Dvir, Sivakanth Gopi#### 2-Server PIR with sub-polynomial communication

__
TR14-095
| 24th July 2014
__

Mark Braverman, Ankit Garg#### Small value parallel repetition for general games

Revisions: 1

__
TR14-096
| 29th July 2014
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran#### Solving Linear Equations Parameterized by Hamming Weight

__
TR14-097
| 31st July 2014
__

Oded Goldreich, Liav Teichner#### Super-Perfect Zero-Knowledge Proofs

Revisions: 1

__
TR14-098
| 30th July 2014
__

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva#### Simultaneous Approximation of Constraint Satisfaction Problems

__
TR14-099
| 7th August 2014
__

Gil Cohen, Igor Shinkar#### The Complexity of DNF of Parities

__
TR14-100
| 4th August 2014
__

Salman Beigi, Omid Etesami, Amin Gohari#### The Value of Help Bits in Randomized and Average-Case Complexity

__
TR14-101
| 8th August 2014
__

Balthazar Bauer, Shay Moran, Amir Yehudayoff#### Internal compression of protocols to entropy

Revisions: 1

__
TR14-102
| 4th August 2014
__

Eshan Chattopadhyay, David Zuckerman#### Non-Malleable Codes Against Constant Split-State Tampering

__
TR14-103
| 8th August 2014
__

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis#### A Unifying Hierarchy of Valuations with Complements and Substitutes

__
TR14-104
| 9th August 2014
__

Atri Rudra, Mary Wootters#### It'll probably work out: improved list-decoding through random operations

__
TR14-105
| 9th August 2014
__

Craig Gentry#### Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington’s Theorem

Comments: 1

__
TR14-106
| 9th August 2014
__

Craig Gentry#### Computing on the edge of chaos: Structure and randomness in encrypted computation

__
TR14-107
| 10th August 2014
__

Or Meir#### Locally Correctable and Testable Codes Approaching the Singleton Bound

Revisions: 2

__
TR14-108
| 10th August 2014
__

Andrej Bogdanov, Christina Brzuska#### On Basing Size-Verifiable One-Way Functions on NP-Hardness

Revisions: 1

__
TR14-109
| 14th August 2014
__

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan#### Quantum lower bound for inverting a permutation with advice

Revisions: 1

__
TR14-110
| 19th August 2014
__

Uriel Feige, Shlomo Jozeph#### Separation between Estimation and Approximation

__
TR14-111
| 15th August 2014
__

Vikraman Arvind, Gaurav Rattan#### Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

__
TR14-112
| 23rd August 2014
__

Louay Bazzi#### Entropy of weight distributions of small-bias spaces and pseudobinomiality

Revisions: 1

__
TR14-113
| 27th August 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication for Boolean Functions

__
TR14-114
| 27th August 2014
__

Roei Tell#### An Alternative Proof of an $\Omega(k)$ Lower Bound for Testing $k$-linear Boolean Functions

__
TR14-115
| 27th August 2014
__

Roei Tell#### Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees

Revisions: 1

__
TR14-116
| 6th September 2014
__

Rahul Mehta#### 2048 is (PSPACE) Hard, but Sometimes Easy

__
TR14-117
| 18th August 2014
__

Shiva Manne, Manjish Pal#### Fast Approximate Matrix Multiplication by Solving Linear Systems

Comments: 1

__
TR14-118
| 9th September 2014
__

Albert Atserias, Massimo Lauria, Jakob Nordström#### Narrow Proofs May Be Maximally Long

__
TR14-119
| 15th September 2014
__

Mark Braverman, Jieming Mao#### Simulating Noisy Channel Interaction

__
TR14-120
| 16th September 2014
__

Olaf Beyersdorff, Leroy Chew, Mikolas Janota#### Proof Complexity of Resolution-based QBF Calculi

__
TR14-121
| 22nd September 2014
__

Sebastian Mueller#### Graph Structure and Parity Games

__
TR14-122
| 30th September 2014
__

Eric Allender, Anna Gal, Ian Mertz#### Dual VP Classes

Revisions: 2

__
TR14-123
| 7th October 2014
__

Shachar Lovett, Jiapeng Zhang#### Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions

__
TR14-124
| 7th October 2014
__

Periklis Papakonstantinou#### The Depth Irreducibility Hypothesis

__
TR14-125
| 9th October 2014
__

Anindya De#### Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums

__
TR14-126
| 9th October 2014
__

Debasis Mandal, A. Pavan, Rajeswari Venugopalan#### Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis

__
TR14-127
| 11th October 2014
__

Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song#### Batch Codes through Dense Graphs without Short Cycles

__
TR14-128
| 10th October 2014
__

Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana , Maciej Obremski#### Non-malleable Reductions and Applications

Revisions: 3

__
TR14-129
| 10th October 2014
__

Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana , Maciej Obremski#### Leakage-resilient non-malleable codes

Revisions: 1

__
TR14-130
| 17th October 2014
__

Ankit Gupta#### Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

Revisions: 1

__
TR14-131
| 7th October 2014
__

Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah#### A game characterisation of tree-like Q-Resolution size

__
TR14-132
| 23rd October 2014
__

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky#### Information Complexity for Multiparty Communication

Revisions: 2

__
TR14-133
| 15th October 2014
__

Adam Case, Jack H. Lutz#### Mutual Dimension

__
TR14-134
| 10th October 2014
__

Martin Lück, Arne Meier, Irina Schindler#### Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies

Revisions: 3

__
TR14-135
| 23rd October 2014
__

Noga Alon, Shay Moran, Amir Yehudayoff#### Sign rank, VC dimension and spectral gaps

Revisions: 2

__
TR14-136
| 17th October 2014
__

Viliam Geffert, Abuzer Yakaryilmaz#### Classical Automata on Promise Problems

__
TR14-137
| 24th October 2014
__

Neil Thapen#### A trade-off between length and width in resolution

__
TR14-138
| 29th October 2014
__

Nicola Galesi, Pavel Pudlak, Neil Thapen#### The space complexity of cutting planes refutations

__
TR14-139
| 31st October 2014
__

Hong Van Le#### Lower bounds for the circuit size of partially homogeneous polynomials

Revisions: 1

__
TR14-140
| 31st October 2014
__

Hong Van Le#### Constructing elusive functions with help of evaluation mappings

__
TR14-141
| 24th October 2014
__

Shachar Lovett#### Linear codes cannot approximate the network capacity within any constant factor

__
TR14-142
| 1st November 2014
__

Subhash Khot, Dana Moshkovitz#### Candidate Lasserre Integrality Gap For Unique Games

__
TR14-143
| 3rd November 2014
__

Ronald de Haan, Stefan Szeider#### Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

__
TR14-144
| 30th October 2014
__

Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan#### Learning circuits with few negations

__
TR14-145
| 4th November 2014
__

Yuan Li, Alexander Razborov, Benjamin Rossman#### On the $AC^0$ Complexity of Subgraph Isomorphism

__
TR14-146
| 6th November 2014
__

Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan#### Space proof complexity for random $3$-CNFs via a $(2-\epsilon)$-Hall's Theorem

__
TR14-147
| 6th November 2014
__

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman#### Rectangles Are Nonnegative Juntas

Revisions: 1

__
TR14-148
| 8th November 2014
__

Vitaly Feldman, Will Perkins, Santosh Vempala#### On the Complexity of Random Satisfiability Problems with Planted Solutions

Revisions: 1

__
TR14-149
| 10th November 2014
__

Kai-Min Chung, Xin Li, Xiaodi Wu#### Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications

__
TR14-150
| 10th November 2014
__

Justin Thaler#### Lower Bounds for the Approximate Degree of Block-Composed Functions

Revisions: 3

__
TR14-151
| 13th November 2014
__

Debajyoti Bera#### Quantum One-Sided Exact Error Algorithms

Revisions: 2

__
TR14-152
| 13th November 2014
__

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo#### Tighter Relations Between Sensitivity and Other Complexity Measures

__
TR14-153
| 14th November 2014
__

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan#### Communication with Imperfectly Shared Randomness

Revisions: 2

__
TR14-154
| 20th November 2014
__

Andris Ambainis, Yuval Filmus, Francois Le Gall#### Fast Matrix Multiplication: Limitations of the Laser Method

__
TR14-155
| 21st November 2014
__

Scott Aaronson, Andris Ambainis#### Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

__
TR14-156
| 26th November 2014
__

Jayadev Acharya, Clement Canonne, Gautam Kamath#### A Chasm Between Identity and Equivalence Testing with Conditional Queries

Revisions: 2

__
TR14-157
| 27th November 2014
__

Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk#### Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

__
TR14-158
| 26th November 2014
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf#### Deterministic Identity Testing for Sum of Read Once ABPs

Revisions: 2

__
TR14-159
| 27th November 2014
__

A. C. Cem Say, Abuzer Yakaryilmaz#### Magic coins are useful for small-space quantum machines

__
TR14-160
| 27th November 2014
__

Gil Cohen, Igor Shinkar#### Zero-Fixing Extractors for Sub-Logarithmic Entropy

__
TR14-161
| 27th November 2014
__

Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari#### Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

Revisions: 2

__
TR14-162
| 28th November 2014
__

Michael Forbes, Venkatesan Guruswami#### Dimension Expanders via Rank Condensers

__
TR14-163
| 29th November 2014
__

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh#### Homomorphism polynomials complete for VP

__
TR14-164
| 30th November 2014
__

Cody Murray, Ryan Williams#### On the (Non) NP-Hardness of Computing Circuit Complexity

__
TR14-165
| 3rd December 2014
__

Venkatesan Guruswami, Ameya Velingker#### An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets

__
TR14-166
| 8th December 2014
__

Mark Bun, Thomas Steinke#### Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

__
TR14-167
| 11th November 2014
__

Beate Bollig#### On the Minimization of (Complete) Ordered Binary Decision Diagrams

__
TR14-168
| 8th December 2014
__

Ilya Volkovich#### Deterministically Factoring Sparse Polynomials into Multilinear Factors

__
TR14-169
| 9th December 2014
__

Stasys Jukna#### Lower Bounds for Monotone Counting Circuits

__
TR14-170
| 10th December 2014
__

Yael Tauman Kalai, Ran Raz#### On the Space Complexity of Linear Programming with Preprocessing

Revisions: 1

__
TR14-171
| 11th December 2014
__

Lance Fortnow, Rahul Santhanam#### Hierarchies Against Sublinear Advice

__
TR14-172
| 12th December 2014
__

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin#### Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

__
TR14-173
| 13th December 2014
__

Igor Carboni Oliveira, Rahul Santhanam#### Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

__
TR14-174
| 14th December 2014
__

Avishay Tal#### Tight bounds on The Fourier Spectrum of $AC^0$

Revisions: 2

__
TR14-175
| 15th December 2014
__

Abhishek Bhowmick, Shachar Lovett#### Nonclassical polynomials as a barrier to polynomial lower bounds

__
TR14-176
| 16th December 2014
__

Eric Allender, Dhiraj Holden, Valentine Kabanets#### The Minimum Oracle Circuit Size Problem

__
TR14-177
| 14th December 2014
__

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig#### Visibly Counter Languages and Constant Depth Circuits

__
TR14-178
| 5th December 2014
__

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov#### Heuristic time hierarchies via hierarchies for sampling distributions

__
TR14-179
| 20th December 2014
__

Salman Beigi, Omid Etesami, Amin Gohari#### Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources

__
TR14-180
| 22nd December 2014
__

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Space-Efficient Approximations for Subset Sum

__
TR14-181
| 19th December 2014
__

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee#### The space "just above" BQP

__
TR14-182
| 22nd December 2014
__

Dana Moshkovitz#### Direct Product Testing With Nearly Identical Sets

Comments: 1

__
TR14-183
| 25th December 2014
__

Nikhil Balaji, Andreas Krebs, Nutan Limaye#### Skew Circuits of Small Width

__
TR14-184
| 29th December 2014
__

Ruiwen Chen, Valentine Kabanets#### Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of

size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$.

In this paper we are interested in the Direct Sum Testing Problem,

where we are given ...
more >>>

Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Two polynomials $f, g \in F[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in {F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>>

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

An $r$-simple $k$-path is a {path} in the graph of length $k$ that

passes through each vertex at most $r$ times. The \simpath{r}{k}

problem, given a graph $G$ as input, asks whether there exists an

$r$-simple $k$-path in $G$. We first show that this problem is

NP-Complete. We then show ...
more >>>

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas. That is, we give

an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with $0, 1$-coefficients such that

for any representation of ...
more >>>

Venkatesan Guruswami, Euiwoong Lee

The Feedback Vertex Set problem (FVS), where the goal is to find a small subset of vertices that intersects every cycle in an input directed graph, is among the fundamental problems whose approximability is not well-understood. One can efficiently find an $\widetilde{O}(\log n)$ factor approximation, and while a constant-factor approximation ... more >>>

Mark Braverman, Klim Efremenko

In this paper we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient

to a noise rate of up to $1/2-\varepsilon$, ...
more >>>

Vinodchandran Variyam

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>>

Alexander A. Sherstov

The threshold degree of a Boolean function $f$ is the minimum degree of

a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969

monograph, Minsky and Papert constructed a polynomial-size constant-depth

$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This bound underlies ...
more >>>

Jean Bourgain, Zeev Dvir, Ethan Leeman

We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

more >>>Dmitry Gavinsky, Pavel Pudlak

We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard definition of expanders. While in the definition of expanders it is required that the number of edges between any ... more >>>

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>>

Mark Braverman, Kanika Pasricha

It is generally assumed that you can make a financial asset out of any underlying event or combination thereof, and then sell a security. We show that while this is theoretically true from the financial engineering perspective, compound securities might be intractable to price. Even given no information asymmetries, or ... more >>>

Olaf Beyersdorff, Leroy Chew

Circumscription is one of the main formalisms for non-monotonic reasoning. It uses reasoning with minimal models, the key idea being that minimal models have as few exceptions as possible. In this contribution we provide the first comprehensive proof-complexity analysis of different proof systems for propositional circumscription. In particular, we investigate ... more >>>

Jack H. Lutz, Neil Lutz

This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0.

more >>>Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz

We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>>

Eli Ben-Sasson, Emanuele Viola

We construct a PCP for NTIME(2$^n$) with constant

soundness, $2^n \poly(n)$ proof length, and $\poly(n)$

queries where the verifier's computation is simple: the

queries are a projection of the input randomness, and the

computation on the prover's answers is a 3CNF. The

previous upper bound for these two computations was

more >>>

Arnab Bhattacharyya

Fix a prime $p$. Given a positive integer $k$, a vector of positive integers ${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$ and a function $\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function $P: \mathbb{F}_p^n \to \mathbb{F}_p$ is $(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials $P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$ ... more >>>

Parikshit Gopalan, Amir Yehudayoff

This paper studies the elementary symmetric polynomials $S_k(x)$ for $x \in \mathbb{R}^n$. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are small for some $k>0$ then $|S_\ell(x)|$ is also small for all $\ell > k$. We use this to prove probability tail bounds for the symmetric polynomials when the inputs are only $t$-wise ... more >>>

Pavel Hrubes, Anup Rao

We consider boolean circuits in which every gate may compute an arbitrary boolean function of $k$ other gates, for a parameter $k$. We give an explicit function $f:\bits^n \rightarrow \bits$ that requires at least $\Omega(\log^2 n)$ non-input gates when $k = 2n/3$. When the circuit is restricted to being depth ... more >>>

Clement Canonne, Ronitt Rubinfeld

In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and extended ... more >>>

Shay Moran, Makrand Sinha, Amir Yehudayoff

Fooling pairs are one of the standard methods for proving lower bounds for deterministic two-player communication complexity. We study fooling pairs in the context of randomized communication complexity.

We show that every fooling pair induces far away distributions on transcripts of private-coin protocols. We then conclude that the private-coin randomized ...
more >>>

Gil Cohen, Anat Ganor, Ran Raz

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 0$ towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>>

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where $n$ is the

number of variables and $cn$ is the number of constraints. The key ...
more >>>

Oded Goldreich, Tom Gur, Ilan Komargodski

Locally testable codes (LTCs) are error-correcting codes

that admit very efficient codeword tests. An LTC is said to

be strong if it has a proximity-oblivious tester;

that is, a tester that makes only a constant number of queries

and reject non-codewords with probability that depends solely

on their distance from ...
more >>>

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf

We study an approximate version of $q$-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A $q$-query $(\alpha,\delta)$-approximate LDC is a set $V$ of $n$ points in $\mathbb{R}^d$ so that, for each $i \in [d]$ there are $\Omega(\delta n)$ ... more >>>

Andris Ambainis, Krisjanis Prusis

Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity ... more >>>

Vikraman Arvind, S Raja

We study two register arithmetic computation and skew arithmetic circuits. Our main results are the following:

(1) For commutative computations, we show that an exponential circuit size lower bound

for a model of 2-register straight-line programs (SLPs) which is a universal model

of computation (unlike width-2 algebraic branching programs that ...
more >>>

Oded Goldreich, Dana Ron

We initiate a study of learning and testing dynamic environments,

focusing on environment that evolve according to a fixed local rule.

The (proper) learning task consists of obtaining the initial configuration

of the environment, whereas for non-proper learning it suffices to predict

its future values. The testing task consists of ...
more >>>

Dana Moshkovitz

The Sliding Scale Conjecture in PCP states that there are PCP verifiers with a constant number of queries and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers.

The Sliding Scale Conjecture is one of the oldest open problems in ... more >>>

Joao Marques-Silva, Mikolas Janota

Propositional Satisfiability (SAT) solvers are routinely used for

solving many function problems.

A natural question that has seldom been addressed is: what is the

best worst-case number of calls to a SAT solver for solving some

target function problem?

This paper develops tighter upper bounds on the query complexity of

more >>>

Olaf Beyersdorff, Leroy Chew

In this paper we compare two proof systems for minimal entailment: a tableau system OTAB and a sequent calculus MLK, both developed by Olivetti (J. Autom. Reasoning, 1992). Our main result shows that OTAB-proofs can be efficiently translated into MLK-proofs, i.e., MLK p-simulates OTAB. The simulation is technically very involved ... more >>>

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>>

Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if ... more >>>

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, Vinodchandran Variyam, Lin Yang

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.

(1) A polynomial-time,

$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ...
more >>>

Mikolas Janota, Leroy Chew, Olaf Beyersdorff

Several calculi for quantified Boolean formulas (QBFs) exist, but

relations between them are not yet fully understood.

This paper defines a novel calculus, which is resolution-based and

enables unification of the principal existing resolution-based QBF

calculi, namely Q-resolution, long-distance Q-resolution and the expansion-based

calculus ...
more >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

Ilario Bonacina, Nicola Galesi, Neil Thapen

We show $\Omega(n^2)$ lower bounds on the total space used in resolution refutations of random $k$-CNFs over $n$ variables, and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the long-standing open problem of whether there are families of $k$-CNF formulas of size $O(n)$ ... more >>>

Andrzej Lingas

We observe that if we allow for the use of

division and the floor function

besides multiplication, addition and

subtraction then we can

compute the arithmetic convolution

of two n-dimensional integer vectors in O(n) steps and

perform the arithmetic matrix multiplication

of two integer n times n matrices ...
more >>>

Hamed Hatami, Pooya Hatami, Shachar Lovett

The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher-order Fourier analysis examines such averages by approximating the indicator function of a subset by a function of bounded number of polynomials. Then, to approximate ... more >>>

Shachar Lovett

The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this ... more >>>

Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. ... more >>>

Venkatesan Guruswami, Euiwoong Lee

Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>>

Daniel Dewey

We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore ... more >>>

Mrinal Kumar, Shubhangi Saraf

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in $VP$. Our results hold for the {\it Iterated Matrix Multiplication} polynomial - in particular we show that any homogeneous depth 4 circuit computing the $(1,1)$ entry in the product of $n$ ... more >>>

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term.

The logarithm of the nonnegative rank is known to ...
more >>>

Mark Braverman, Omri Weinstein

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretically secure computation.

As a first corollary, ... more >>>

Avishay Tal

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is $2$. Namely, we show that for any Boolean function $f: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>>

Edward Hirsch, Dmitry Sokolov

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>>

Subhash Khot, Rishi Saket

We show that it is quasi-NP-hard to color $2$-colorable $12$-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color $2$-colorable $8$-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a ... more >>>

Joshua Grochow, Toniann Pitassi

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>>

Dana Moshkovitz

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k in terms of the value of the game G and the number of repetitions k.

Contrary to what one might have guessed, the value of G^k is not val(G)^k, but rather a more complicated ...
more >>>

Mika Göös, Thomas Watson

We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions ... more >>>

Zeev Dvir, Rafael Mendes de Oliveira

We show that if $f(x_1,\ldots,x_n)$ is a polynomial with $s$ monomials and $g(x_1,\ldots,x_n)$ divides $f$ then $g$

has at most $\max(s^{O(\log s \log\log s)},d^{O(\log d)})$ monomials, where $d$ is a bound on the individual degrees

of $f$. This answers a question of von zur Gathen and Kaltofen (JCSS ...
more >>>

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

In this paper, we propose a quantification of distributions on a set

of strings, in terms of how close to pseudorandom the distribution

is. The quantification is an adaptation of the theory of dimension of

sets of infinite sequences first introduced by Lutz

\cite{Lutz:DISS}.

We show that this definition ...
more >>>

Ilya Volkovich

We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class $\mathcal{C}$ has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and ... more >>>

Boaz Barak, David Steurer

In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible ... more >>>

Anup Rao, Amir Yehudayoff

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof

showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,

Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ...
more >>>

Alexander Kozachinsky

We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity $I$ and communication complexity $C$ can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed $O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication ... more >>>

Adam Klivans, Pravesh Kothari

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that ... more >>>

Arkadev Chattopadhyay, Michael Saks

In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a $k \times m$ boolean matrix $A$ (where $k$ is the number of players) and Player $i$ sees all bits except those in the $i$-th row, and the players communicate by broadcast in order to evaluate a specified ... more >>>

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>

Suguru Tamaki, Yuichi Yoshida

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>>

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

Eric Allender, Bireswar Das

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is

efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>

Shashank Agrawal, Divya Gupta, Hemanta Maji, Omkant Pandey, Manoj Prabhakaran

The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value.

In the information theoretic setting, although existence of such codes for various ... more >>>

Vikraman Arvind, Gaurav Rattan

We study the complexity of Geometric Graph Isomorphism, in

$l_2$ and other $l_p$ metrics: given two sets of $n$ points $A,

B\subset \mathbb{Q}^k$ in

$k$-dimensional euclidean space the problem is to

decide if there is a bijection $\pi:A \rightarrow B$ such that for

...
more >>>

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... more >>>

Sajin Koroth, Jayalal Sarma

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure ... more >>>

Shachar Lovett, Cris Moore, Alexander Russell

We show that there exists a family of groups $G_n$ and nontrivial irreducible representations $\rho_n$ such that, for any constant $t$, the average of $\rho_n$ over $t$ uniformly random elements $g_1, \ldots, g_t \in G_n$ has operator norm $1$ with probability approaching 1 as $n \rightarrow \infty$. More quantitatively, we ... more >>>

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>>

Holger Dell

Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result.

An AND-compression is ... more >>>

Thomas Steinke

We present an explicit pseudorandom generator for oblivious, read-once, width-$3$ branching programs, which can read their input bits in any order. The generator has seed length $\tilde{O}( \log^3 n ).$ The previously best known seed length for this model is $n^{1/2+o(1)}$ due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our ... more >>>

Andris Ambainis, Jevgenijs Vihrovs

We study the structure of sets $S\subseteq\{0, 1\}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq\{0, 1\}^n$ of sensitivity $s$ must be of size at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

We study whether information complexity can be used to attack the long-standing open problem of proving lower bounds against Arthur--Merlin (AM) communication protocols. Our starting point is to show that---in contrast to plain randomized communication complexity---every boolean function admits an AM communication protocol where on each yes-input, the distribution of ... more >>>

Simon Straub, Thomas Thierauf, Fabian Wagner

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

Stasys Jukna

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals

In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools ... more >>>

Yu Yu, Dawu Gu, Xiangxue Li

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography ... more >>>

Irit Dinur, Shafi Goldwasser, Huijia Lin

The starting point of this paper is that instances of computational problems often do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. The challenge is how to gain computationally from instance correlations when they exist. We will be interested ... more >>>

Luke Schaeffer

Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by ... more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling ... more >>>

Abhishek Bhowmick, Shachar Lovett

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>

Swagato Sanyal

We prove that the Fourier dimension of any Boolean function with

Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof

method yields an improved bound of $\widetilde{O}(\sqrt{s})$

assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every

Boolean function of sparsity $s$ there is an affine subspace of

more >>>

Neeraj Kayal, Chandan Saha

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>

Justin Thaler

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of ... more >>>

Ryan O'Donnell, A. C. Cem Say

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... more >>>

Mark Braverman, Young Kun Ko, Omri Weinstein

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game

initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.

We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is ... more >>>

Zeev Dvir, Sivakanth Gopi

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. In this work we construct a 1-round 2-server PIR with total communication cost ... more >>>

Mark Braverman, Ankit Garg

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:

1. Does $Ax=b$ have a solution of weight at most $t$?

2. Does $Ax=b$ have a solution of weight exactly $t$?

3. Does $Ax=b$ have a ...
more >>>

Oded Goldreich, Liav Teichner

We initiate a study of super-perfect zero-knowledge proof systems.

Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.

In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated

by a strict probabilistic polynomial-time that ...
more >>>

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

Our main result is that ... more >>>

Gil Cohen, Igor Shinkar

We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as ... more >>>

Salman Beigi, Omid Etesami, Amin Gohari

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity.

Amir, Beigel, and Gasarch ... more >>>

Balthazar Bauer, Shay Moran, Amir Yehudayoff

We study internal compression of communication protocols

to their internal entropy, which is the entropy of the transcript from the players' perspective.

We first show that errorless compression to the internal entropy

(and hence to the internal information) is impossible.

We then provide two internal compression schemes with error.

One ...
more >>>

Eshan Chattopadhyay, David Zuckerman

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... more >>>

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis

We introduce a new hierarchy over monotone set functions, that we refer to as $MPH$ (Maximum over Positive Hypergraphs).

Levels of the hierarchy correspond to the degree of complementarity in a given function.

The highest level of the hierarchy, $MPH$-$m$ (where $m$ is the total number of items) captures all ...
more >>>

Atri Rudra, Mary Wootters

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code.

The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural ...
more >>>

Craig Gentry

We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington’s Theorem. Barrington showed how to express a NC1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington’s product program ... more >>>

Craig Gentry

This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" approach: they encrypt via a noisy encoding of the message, they decrypt ... more >>>

Or Meir

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are codes that admit local algorithms for decoding and testing respectively. The local algorithms are randomized algorithms that make only a small number of queries to their input. LCCs and LTCs are both interesting in their own right, and have important applications in ... more >>>

Andrej Bogdanov, Christina Brzuska

We prove that if the hardness of inverting a size-verifiable one-way function can

be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This

claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but

was later retracted (STOC 2010).

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>

Uriel Feige, Shlomo Jozeph

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.

As an ...
more >>>

Vikraman Arvind, Gaurav Rattan

We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous

best running time bound of $O^*(2^{O(k^2/\log

k)})$.

Louay Bazzi

A classical bound in Information Theory asserts that small $L_1$-distance between probability distributions implies small difference in Shannon entropy, but the converse need not be true. We show that if a probability distribution on $\{0,1\}^n$ has small-bias, then the converse holds for its weight distribution in the proximity of the ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>

Roei Tell

We provide an alternative proof for a known result stating that $\Omega(k)$ queries are needed to test $k$-sparse linear Boolean functions. Similar to the approach of Blais and Kane (2012), we reduce the proof to the analysis of Hamming weights of vectors in affi ne subspaces of the Boolean hypercube. ... more >>>

Roei Tell

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

Rahul Mehta

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result

holds for a version of the problem where the player has oracle access to the computer player's moves.

Specifically, we show that for an $n \times n$ game board $G$, computing a

more >>>

Shiva Manne, Manjish Pal

In this paper, we present novel deterministic algorithms for multiplying two $n \times n$ matrices approximately. Given two matrices $A,B$ we return a matrix $C'$ which is an \emph{approximation} to $C = AB$. We consider the notion of approximate matrix multiplication in which the objective is to make the Frobenius ... more >>>

Albert Atserias, Massimo Lauria, Jakob Nordström

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

Mark Braverman, Jieming Mao

We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-\epsilon}$ with feedback can be simulated with $O(\epsilon^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost'' model of interaction over a noisy channel. We show energy cost to be equivalent ... more >>>

Olaf Beyersdorff, Leroy Chew, Mikolas Janota

Proof systems for quantified Boolean formulas (QBFs) provide a theoretical underpinning for the performance of important

QBF solvers. However, the proof complexity of these proof systems is currently not well understood and in particular

lower bound techniques are missing. In this paper we exhibit a new and elegant proof technique ...
more >>>

Sebastian Mueller

We investigate the possible structural changes one can perform on a game graph without destroying the winning regions of the players playing a parity game on it. More precisely, given a game graph $(G,p)$ for which we can efficiently compute winning regions, can we remove or add a vertex or ... more >>>

Eric Allender, Anna Gal, Ian Mertz

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of

a class of high-degree polynomials that can be simulated via arithmetic circuits ...
more >>>

Shachar Lovett, Jiapeng Zhang

The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in $\{0,1\}^n$ with support of size $k$,

and given access only to noisy samples from it, where each bit is flipped independently with probability $1/2-\eps$,

estimate the original probability up to an additive error of ...
more >>>

Periklis Papakonstantinou

We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness ... more >>>

Anindya De

In this paper, we construct pseudorandom generators for the class of \emph{combinatorial sums}, a class of functions first studied by \cite{GMRZ13}

and defined as follows: A function $f: [m]^n \rightarrow \{0,1\}$ is said to be a combinatorial sum if there exists functions $f_1, \ldots, f_n: [m] \rightarrow \{0,1\}$ such that

more >>>

Debasis Mandal, A. Pavan, Rajeswari Venugopalan

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... more >>>

Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song

Consider a large database of $n$ data items that need to be stored using $m$ servers.

We study how to encode information so that a large number $k$ of read requests can be performed \textit{in parallel} while the rate remains constant (and ideally approaches one).

This problem is equivalent ...
more >>>

Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana , Maciej Obremski

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either ... more >>>

Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana , Maciej Obremski

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this ... more >>>

Ankit Gupta

We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we ... more >>>

Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah

We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives the first successful transfer of one of the lower bound techniques for classical proof systems to QBF ... more >>>

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model ... more >>>

Adam Case, Jack H. Lutz

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>

Martin Lück, Arne Meier, Irina Schindler

We present a complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. Our results show a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The two real operator fragments which are in FPT ... more >>>

Noga Alon, Shay Moran, Amir Yehudayoff

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

Viliam Geffert, Abuzer Yakaryilmaz

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by ... more >>>

Neil Thapen

We describe a family of CNF formulas in $n$ variables, with small initial width, which have polynomial length resolution refutations. By a result of Ben-Sasson and Wigderson it follows that they must also have narrow resolution refutations, of width $O(\sqrt {n \log n})$. We show that, for our formulas, this ... more >>>

Nicola Galesi, Pavel Pudlak, Neil Thapen

We study the space complexity of the cutting planes proof system, in which the lines in a proof are integral linear inequalities. We measure the space used by a refutation as the number of inequalities that need to be kept on a blackboard while verifying it. We show that any ... more >>>

Hong Van Le

In this paper

we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_\lambda (f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda (f)$ is bounded from above ...
more >>>

Hong Van Le

We develop a method to construct elusive functions using techniques of commutative algebra and algebraic geometry. The key notions of this method are elusive subsets and evaluation mappings. We also develop the effective elimination theory combined with algebraic number field theory in order to construct concrete points outside the image ... more >>>

Shachar Lovett

Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>>

Subhash Khot, Dana Moshkovitz

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.

Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ...
more >>>

Ronald de Haan, Stefan Szeider

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These parameterized problems are based on problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. The list will be updated as ... more >>>

Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and ... more >>>

Yuan Li, Alexander Razborov, Benjamin Rossman

Let $P$ be a fixed graph (hereafter called a ``pattern''), and let

$Subgraph(P)$ denote the problem of deciding whether a given graph $G$

contains a subgraph isomorphic to $P$. We are interested in

$AC^0$-complexity of this problem, determined by the smallest possible exponent

$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ...
more >>>

Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>>

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ ... more >>>

Vitaly Feldman, Will Perkins, Santosh Vempala

We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best known ... more >>>

Kai-Min Chung, Xin Li, Xiaodi Wu

We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new ... more >>>

Justin Thaler

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function $f$ on $N$ bits, define $F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$ to be the function on $M \cdot N$ bits obtained by block-composing $f$ with a specific DNF known ... more >>>

Debajyoti Bera

We define a complexity class for randomized algorithms with one-sided error that is exactly equal to a constant (unlike the usual definitions, in which the error is only bounded above or below by a constant). We show that the corresponding quantum classes (one each for a different error probability) are ... more >>>

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Andris Ambainis, Yuval Filmus, Francois Le Gall

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.3729})$. These algorithms are obtained by analyzing higher ... more >>>

Scott Aaronson, Andris Ambainis

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum ... more >>>

Jayadev Acharya, Clement Canonne, Gautam Kamath

A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain.

In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., ...
more >>>

Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>>

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. ... more >>>

A. C. Cem Say, Abuzer Yakaryilmaz

Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such ``magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits ... more >>>

Gil Cohen, Igor Shinkar

An $(n,k)$-bit-fixing source is a distribution on $n$ bit strings, that is fixed on $n-k$ of the coordinates, and jointly uniform on the remaining $k$ bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract $(1-o(1)) \cdot k$ bits for $k = ... more >>>

Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... more >>>

Michael Forbes, Venkatesan Guruswami

An emerging theory of "linear-algebraic pseudorandomness" aims to understand the linear-algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension ... more >>>

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

Cody Murray, Ryan Williams

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>>

Venkatesan Guruswami, Ameya Velingker

We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d. copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ ... more >>>

Mark Bun, Thomas Steinke

Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorithms for agnostically learning halfspaces, as well as pseudorandom generators for halfspaces. In this work, we investigate the limits of these techniques by proving inapproximability results for ... more >>>

Beate Bollig

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.

Some applications work with a restricted variant called complete OBDDs

which is strongly related to nonuniform deterministic finite automata.

One of its complexity measures is the width which has been investigated

in several areas in computer science ...
more >>>

Ilya Volkovich

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors.

Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in \cite{GathenKaltofen85} to devise an efficient deterministic algorithm for factoring (general) sparse polynomials.

We achieve ...
more >>>

Stasys Jukna

A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a circuit counts the number of monomials of evaluated to 1 by a given 0-1 input vector (with multiplicities ... more >>>

Yael Tauman Kalai, Ran Raz

Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?

It is widely believed that (even approximating) Linear Programming requires a large ... more >>>

Lance Fortnow, Rahul Santhanam

We strengthen the non-deterministic time hierarchy theorem of

\cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound

holds against sublinear advice. More formally, we show that for any constants

$c$ and $d$ such that $1 \leq c < d$, there is a language in $\NTIME(n^d)$

which is not in $\NTIME(n^c)/n^{1/d}$. ...
more >>>

Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

Avishay Tal

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up ... more >>>

Abhishek Bhowmick, Shachar Lovett

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ...
more >>>

Eric Allender, Dhiraj Holden, Valentine Kabanets

We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP$^{QBF}$ is known to be complete for PSPACE under ZPP reductions. We show that it is not ... more >>>

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].

more >>>Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

We give a new simple proof of the time hierarchy theorem for heuristic BPP originally proved by Fortnow and Santhanam [FS04] and then simplified and improved by Pervyshev [P07]. In the proof we use a hierarchy theorem for sampling distributions recently proved by Watson [W13]. As a byproduct we get ... more >>>

Salman Beigi, Omid Etesami, Amin Gohari

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible.

In this paper, we study the generalization of SV ...
more >>>

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

SUBSET SUM is a well known NP-complete problem:

given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ...
more >>>

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>

Dana Moshkovitz

In this work we analyze a direct product test in which each of two provers receives a subset of size n of a ground set U,

and the two subsets intersect in about (1-\delta)n elements.

We show that if each of the provers provides labels to the n ...
more >>>

Nikhil Balaji, Andreas Krebs, Nutan Limaye

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

Ruiwen Chen, Valentine Kabanets

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there ... more >>>