All reports in year 2013:

__
TR13-001
| 2nd January 2013
__

Gillat Kol, Ran Raz#### Interactive Channel Capacity

Revisions: 1

__
TR13-002
| 31st December 2012
__

Venkatesan Guruswami, Krzysztof Onak#### Superlinear lower bounds for multipass graph processing

Revisions: 3

__
TR13-003
| 2nd January 2013
__

Eric Miles, Emanuele Viola#### Shielding circuits with groups

Revisions: 2

__
TR13-004
| 11th November 2012
__

A. C. Cem Say, Abuzer Yakaryilmaz#### Finite state verifiers with constant randomness

__
TR13-005
| 2nd January 2013
__

Alexander A. Sherstov#### Communication Lower Bounds Using Directional Derivatives

__
TR13-006
| 8th January 2013
__

Balagopal Komarath, Jayalal Sarma#### Pebbling, Entropy and Branching Program Size Lower Bounds

__
TR13-007
| 8th January 2013
__

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand#### Short lists with short programs in short time

Revisions: 1

__
TR13-008
| 7th January 2013
__

Adam Klivans, Raghu Meka#### Moment-Matching Polynomials

__
TR13-009
| 9th January 2013
__

Zahra Jafargholi, Emanuele Viola#### 3SUM, 3XOR, Triangles

Revisions: 1

__
TR13-010
| 4th January 2013
__

Yang Liu, Shengyu Zhang#### Quantum and randomized communication complexity of XOR functions in the SMP model

__
TR13-011
| 10th January 2013
__

Nader Bshouty#### Multilinear Complexity is Equivalent to Optimal Tester Size

__
TR13-012
| 16th January 2013
__

Hasan Abasi, Nader Bshouty#### A Simple Algorithm for Undirected Hamiltonicity

__
TR13-013
| 18th January 2013
__

Daniel Apon, Jonathan Katz, Alex Malozemoff#### One-Round Multi-Party Communication Complexity of Distinguishing Sums

Revisions: 1

__
TR13-014
| 11th January 2013
__

Zvika Brakerski, Moni Naor#### Fast Algorithms for Interactive Coding

__
TR13-015
| 18th January 2013
__

Iordanis Kerenidis, Mathieu Laurière, David Xiao#### New lower bounds for privacy in communication protocols

__
TR13-016
| 17th January 2013
__

Olaf Beyersdorff#### The Complexity of Theorem Proving in Autoepistemic Logic

Revisions: 1

__
TR13-017
| 23rd January 2013
__

Pratik Worah#### A Short Excursion into Semi-Algebraic Hierarchies

__
TR13-018
| 29th January 2013
__

Luke Friedman, Yixin Xu#### Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams

__
TR13-019
| 31st January 2013
__

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf#### On Two-Level Poset Games

__
TR13-020
| 2nd February 2013
__

Tom Gur, Ran Raz#### Arthur-Merlin Streaming Complexity

__
TR13-021
| 5th February 2013
__

Kristoffer Arnsfelt Hansen, Vladimir Podolskii#### Polynomial threshold functions and Boolean threshold circuits

__
TR13-022
| 5th February 2013
__

Michael Viderman#### Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 1

__
TR13-023
| 6th February 2013
__

Alexander A. Sherstov#### Approximating the AND-OR Tree

__
TR13-024
| 7th February 2013
__

Valentine Kabanets, Antonina Kolokolova#### Compression of Boolean Functions

__
TR13-025
| 6th February 2013
__

Xin Li#### Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revisions: 1

__
TR13-026
| 11th February 2013
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### Arithmetic circuits: A chasm at depth three

Revisions: 1

__
TR13-027
| 29th January 2013
__

Luke Friedman#### A Framework for Proving Proof Complexity Lower Bounds on Random CNFs Using Encoding Techniques

__
TR13-028
| 14th February 2013
__

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma#### Arithmetic Circuit Lower Bounds via MaxRank

__
TR13-029
| 19th February 2013
__

Diptarka Chakraborty, C. Seshadhri#### A {\huge ${o(n)}$} monotonicity tester for Boolean functions over the hypercube

Revisions: 1

__
TR13-030
| 20th February 2013
__

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan#### Absolutely Sound Testing of Lifted Codes

__
TR13-031
| 22nd February 2013
__

Irit Dinur, Elazar Goldenberg#### Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

__
TR13-032
| 26th February 2013
__

Mark Bun, Justin Thaler#### Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Revisions: 2

__
TR13-033
| 1st March 2013
__

Michael Forbes, Amir Shpilka#### Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Revisions: 1

__
TR13-034
| 2nd March 2013
__

Louay Bazzi, Nagi Nahas#### Small-bias is not enough to hit read-once CNF

__
TR13-035
| 6th March 2013
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct product via round-preserving compression

Revisions: 1

__
TR13-036
| 13th March 2013
__

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev#### Lower Bounds for Testing Properties of Functions on Hypergrid Domains

Revisions: 1

__
TR13-037
| 15th March 2013
__

Alexander Knop#### Circuit Lower Bounds for Heuristic MA

Revisions: 2

__
TR13-038
| 13th March 2013
__

Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen#### The complexity of proving that a graph is Ramsey

Revisions: 1

__
TR13-039
| 18th March 2013
__

Arturs Backurs, Mohammad Bavarian#### On the sum of $L1$ influences

Revisions: 2

__
TR13-040
| 11th March 2013
__

Michaël Cadilhac, Andreas Krebs, Pierre McKenzie#### The Algebraic Theory of Parikh Automata

Revisions: 2

__
TR13-041
| 14th March 2013
__

Igor Sergeev#### On the complexity of parallel prefix circuits

__
TR13-042
| 25th March 2013
__

Siu Man Chan#### Just a Pebble Game

__
TR13-043
| 25th March 2013
__

Oded Goldreich, Avi Wigderson#### On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

__
TR13-044
| 25th March 2013
__

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang#### Shared Randomness and Quantum Communication in the Multi-Party Model

__
TR13-045
| 26th March 2013
__

Marek Karpinski, Michael Lampis, Richard Schmied#### New Inapproximability Bounds for TSP

__
TR13-046
| 27th March 2013
__

Venkatesan Guruswami, Chaoping Xing#### Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

__
TR13-047
| 27th March 2013
__

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek#### Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

Comments: 1

__
TR13-048
| 27th March 2013
__

Jin-Yi Cai, Aaron Gorenstein#### Matchgates Revisited

__
TR13-049
| 1st April 2013
__

Amir Shpilka, Ben Lee Volk, Avishay Tal#### On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

__
TR13-050
| 1st April 2013
__

Venkatesan Guruswami, Patrick Xia#### Polar Codes: Speed of polarization and polynomial gap to capacity

Revisions: 1

__
TR13-051
| 2nd April 2013
__

Eric Blais, Li-Yang Tan#### Approximating Boolean functions with depth-2 circuits

__
TR13-052
| 3rd April 2013
__

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh#### {Upper Bounds on Fourier Entropy

Revisions: 1

__
TR13-053
| 4th April 2013
__

Alan Guo#### High rate locally correctable codes via lifting

Revisions: 1

__
TR13-054
| 4th April 2013
__

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook#### Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

__
TR13-055
| 5th April 2013
__

David Gamarnik, Madhu Sudan#### Limits of local algorithms over sparse random graphs

__
TR13-056
| 30th March 2013
__

Gábor Braun, Sebastian Pokutta#### Common information and unique disjointness

Revisions: 5

__
TR13-057
| 5th April 2013
__

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman#### Mining Circuit Lower Bound Proofs for Meta-Algorithms

__
TR13-058
| 5th April 2013
__

Ilan Komargodski, Ran Raz, Avishay Tal#### Improved Average-Case Lower Bounds for DeMorgan Formula Size

Revisions: 2

__
TR13-059
| 9th April 2013
__

Lior Gishboliner, Asaf Shapira#### Deterministic vs Non-deterministic Graph Property Testing

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

__
TR13-061
| 17th April 2013
__

Zeev Dvir, Guangda Hu#### Matching-Vector Families and LDCs Over Large Modulo

__
TR13-062
| 18th April 2013
__

Diptarka Chakraborty, C. Seshadhri#### An optimal lower bound for monotonicity testing over hypergrids

__
TR13-063
| 19th April 2013
__

Dung Nguyen, Alan Selman#### Non-autoreducible Sets for NEXP

__
TR13-064
| 22nd April 2013
__

Anat Ganor, Ran Raz#### Space Pseudorandom Generators by Communication Complexity Lower Bounds

Revisions: 1

__
TR13-065
| 21st April 2013
__

Yijia Chen, Joerg Flum#### On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity

__
TR13-066
| 25th April 2013
__

Marek Karpinski, Richard Schmied#### Approximation Hardness of Graphic TSP on Cubic Graphs

__
TR13-067
| 2nd May 2013
__

Oded Goldreich#### On Multiple Input Problems in Property Testing

Revisions: 1

__
TR13-068
| 3rd May 2013
__

Mrinal Kumar, Shubhangi Saraf#### Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin

__
TR13-069
| 1st May 2013
__

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis#### A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing

__
TR13-070
| 4th May 2013
__

Iddo Tzameret#### On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation

Revisions: 1

__
TR13-071
| 8th May 2013
__

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket#### Inapproximability of Minimum Vertex Cover on $k$-uniform $k$-partite Hypergraphs

__
TR13-072
| 3rd May 2013
__

Jan Johannsen#### Exponential Separations in a Hierarchy of Clause Learning Proof Systems

__
TR13-073
| 14th May 2013
__

Oded Goldreich#### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

Revisions: 2

__
TR13-074
| 9th May 2013
__

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky#### Helly Circular-Arc Graph Isomorphism is in Logspace

__
TR13-075
| 23rd May 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Strong Approximation Resistance

__
TR13-076
| 15th May 2013
__

Divesh Aggarwal, Chandan Dubey#### Improved hardness results for unique shortest vector problem

Revisions: 1

__
TR13-077
| 14th May 2013
__

Ján Pich#### Circuit Lower Bounds in Bounded Arithmetics

__
TR13-078
| 28th May 2013
__

Tom Gur, Ron Rothblum#### Non-Interactive Proofs of Proximity

Revisions: 1

__
TR13-079
| 2nd June 2013
__

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff#### Direct Sum Fails for Zero Error Average Communication

__
TR13-080
| 4th June 2013
__

Dmitry Gavinsky, Shachar Lovett#### En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

__
TR13-081
| 6th June 2013
__

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett#### Non-malleable Codes from Additive Combinatorics

__
TR13-082
| 6th June 2013
__

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish#### Some properties are not even partially testable

__
TR13-083
| 7th June 2013
__

Miklos Ajtai#### Lower Bounds for RAMs and Quantifier Elimination

__
TR13-084
| 8th June 2013
__

Shachar Lovett#### Communication is bounded by root of rank

Revisions: 1

__
TR13-085
| 13th June 2013
__

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth#### Constant rate PCPs for circuit-SAT with sublinear query complexity

__
TR13-086
| 13th June 2013
__

Omer Reingold, Thomas Steinke, Salil Vadhan#### Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

__
TR13-087
| 4th June 2013
__

Hamed Hatami, Shachar Lovett#### Estimating the distance from testable affine-invariant properties

__
TR13-088
| 16th June 2013
__

Zachary Remscrim, Michael Sipser#### $AC^0$ Pseudorandomness of Natural Operations

__
TR13-089
| 17th June 2013
__

Abhishek Bhrushundi#### On testing bent functions

Revisions: 1

__
TR13-090
| 18th June 2013
__

Elena Grigorescu, Karl Wimmer, Ning Xie#### Tight Lower Bounds for Testing Linear Isomorphism

__
TR13-091
| 17th June 2013
__

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi#### A super-polynomial lower bound for regular arithmetic formulas.

__
TR13-092
| 19th June 2013
__

Pavel Pudlak, Arnold Beckmann, Neil Thapen#### Parity Games and Propositional Proofs

Revisions: 1

__
TR13-093
| 21st June 2013
__

Anna Gal, Jing-Tang Jang#### A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators

__
TR13-094
| 13th June 2013
__

Brendan Juba#### On Non-automatizability in PAC-Semantics

__
TR13-095
| 24th June 2013
__

Uriel Feige, Rani Izsak#### Welfare Maximization and the Supermodular Degree

__
TR13-096
| 25th June 2013
__

Dana Ron, Rocco Servedio#### Exponentially improved algorithms and lower bounds for testing signed majorities

__
TR13-097
| 25th June 2013
__

Mikolas Janota, Joao Marques-Silva#### On Propositional QBF Expansions and Q-Resolution

__
TR13-098
| 28th June 2013
__

Benny Applebaum, Yoni Moses#### Locally Computable UOWHF with Linear Shrinkage

__
TR13-099
| 6th July 2013
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Local reductions

Revisions: 3

__
TR13-100
| 15th July 2013
__

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan#### Lower bounds for depth $4$ formulas computing iterated matrix multiplication

__
TR13-101
| 12th July 2013
__

Colin Jia Zheng, Salil Vadhan#### A Uniform Min-Max Theorem with Applications in Cryptography

Revisions: 2

__
TR13-102
| 17th July 2013
__

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Small Depth Proof Systems

__
TR13-103
| 24th July 2013
__

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha#### Generalized Wong sequences and their applications to Edmonds' problems

__
TR13-104
| 20th July 2013
__

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin#### Explicit Maximally Recoverable Codes with Locality

__
TR13-105
| 29th July 2013
__

Raghu Meka, Avi Wigderson#### Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique

Revisions: 1

__
TR13-106
| 29th July 2013
__

Shay Moran, Amir Yehudayoff#### A note on average-case sorting

Revisions: 2

__
TR13-107
| 7th August 2013
__

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum#### Efficient Multiparty Protocols via Log-Depth Threshold Formulae

__
TR13-108
| 9th August 2013
__

Rahul Santhanam, Ryan Williams#### New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

__
TR13-109
| 11th August 2013
__

Oded Goldreich, Dana Ron#### On Sample-Based Testers

Revisions: 1

__
TR13-110
| 12th August 2013
__

Xiaoming Sun, Marcos Villagra#### Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity

__
TR13-111
| 17th August 2013
__

Gregory Valiant, Paul Valiant#### Instance-by-instance optimal identity testing

__
TR13-112
| 12th August 2013
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf#### Exact Perfect Matching in Complete Graphs

__
TR13-113
| 19th August 2013
__

Moritz Müller, Stefan Szeider#### Revisiting Space in Proof Complexity: Treewidth and Pathwidth

__
TR13-114
| 24th August 2013
__

Parikshit Gopalan, Salil Vadhan, Yuan Zhou#### Locally Testable Codes and Cayley Graphs

Revisions: 1

__
TR13-115
| 27th August 2013
__

Daniele Micciancio#### Locally Dense Codes

__
TR13-116
| 29th August 2013
__

Albert Atserias, Moritz Müller, Sergi Oliva#### Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle

__
TR13-117
| 1st September 2013
__

Igor Oliveira#### Algorithms versus Circuit Lower Bounds

__
TR13-118
| 2nd September 2013
__

Mahdi Cheraghchi, Venkatesan Guruswami#### Capacity of Non-Malleable Codes

__
TR13-119
| 2nd September 2013
__

Emanuele Viola#### Challenges in computational lower bounds

__
TR13-120
| 4th September 2013
__

Zeyu Guo#### Randomness-efficient Curve Samplers

__
TR13-121
| 4th September 2013
__

Mahdi Cheraghchi, Venkatesan Guruswami#### Non-Malleable Coding Against Bit-wise and Split-State Tampering

Revisions: 1

__
TR13-122
| 5th September 2013
__

Irit Dinur, Venkatesan Guruswami#### PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

__
TR13-123
| 6th September 2013
__

Joshua Grochow, Youming Qiao#### Algorithms for group isomorphism via group extensions and cohomology

__
TR13-124
| 9th September 2013
__

Thomas Watson#### The Complexity of Deciding Statistical Properties of Samplable Distributions

Revisions: 2

__
TR13-125
| 11th September 2013
__

Venkatesan Guruswami, Euiwoong Lee#### Complexity of approximating CSP with Balance / Hard Constraints

__
TR13-126
| 11th September 2013
__

Arman Fazeli, Shachar Lovett, Alex Vardy#### Nontrivial t-designs over finite fields exist for all t

__
TR13-127
| 15th September 2013
__

Paul Beame, Raphael Clifford, Widad Machmouchi#### Element Distinctness, Frequency Moments, and Sliding Windows

__
TR13-128
| 16th September 2013
__

Pavel Hrubes#### A note on semantic cutting planes

__
TR13-129
| 17th September 2013
__

Adam Klivans, Pravesh Kothari, Igor Oliveira#### Constructing Hard Functions from Learning Algorithms

Revisions: 1

__
TR13-130
| 17th September 2013
__

Mark Braverman, Ankit Garg#### Public vs private coin in bounded-round information

Revisions: 1

__
TR13-131
| 17th September 2013
__

Nikhil Balaji, Samir Datta#### Collapsing Exact Arithmetic Hierarchies

Revisions: 1

__
TR13-132
| 23rd September 2013
__

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka#### Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

__
TR13-133
| 23rd September 2013
__

Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland#### A Structured View on Weighted Counting with Relations to Quantum Computation and Applications

Revisions: 1

__
TR13-134
| 25th September 2013
__

Or Meir#### Combinatorial PCPs with Short Proofs

__
TR13-135
| 27th September 2013
__

Scott Aaronson#### BosonSampling Is Far From Uniform

Revisions: 2

__
TR13-136
| 27th September 2013
__

Paul Goldberg, Aaron Roth#### Bounds for the Query Complexity of Approximate Equilibria

__
TR13-137
| 29th September 2013
__

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran#### On the Power of Public-key Encryption in Secure Computation

__
TR13-138
| 5th October 2013
__

Itai Benjamini, Gil Cohen, Igor Shinkar#### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revisions: 1

__
TR13-139
| 7th October 2013
__

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu#### Detecting Monomials with $k$ Distinct Variables

__
TR13-140
| 8th October 2013
__

Atri Rudra, Mary Wootters#### Every list-decodable code for high noise has abundant near-optimal rate puncturings

__
TR13-141
| 8th October 2013
__

Leonid Gurvits#### Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

Revisions: 1

__
TR13-142
| 11th October 2013
__

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni#### Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees

Revisions: 2

__
TR13-143
| 19th October 2013
__

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman#### Robust Pseudorandom Generators

Revisions: 1

__
TR13-144
| 8th October 2013
__

VyasRam Selvam#### The two queries assumption and Arthur-Merlin classes

__
TR13-145
| 20th October 2013
__

Gil Cohen, Avishay Tal#### Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

__
TR13-146
| 20th October 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Approximation Resistance

Revisions: 1

__
TR13-147
| 25th October 2013
__

Adam Bouland, Scott Aaronson#### Any Beamsplitter Generates Universal Quantum Linear Optics

Revisions: 3

__
TR13-148
| 26th October 2013
__

Irit Dinur, Igor Shinkar#### On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

__
TR13-149
| 28th October 2013
__

Albert Atserias, Neil Thapen#### The Ordering Principle in a Fragment of Approximate Counting

__
TR13-150
| 4th November 2013
__

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh#### An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

__
TR13-151
| 7th November 2013
__

Mark Bun, Justin Thaler#### Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

__
TR13-152
| 7th November 2013
__

Oded Goldreich, Avi Wigderson#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

__
TR13-153
| 8th November 2013
__

Mrinal Kumar, Shubhangi Saraf#### The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in

__
TR13-154
| 29th October 2013
__

Martin Schwarz, Maarten Van den Nest#### Simulating Quantum Circuits with Sparse Output Distributions

__
TR13-155
| 10th November 2013
__

Gil Cohen, Amnon Ta-Shma#### Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

__
TR13-156
| 15th November 2013
__

Jan Krajicek#### A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems

Revisions: 2

__
TR13-157
| 11th November 2013
__

Bin Fu#### Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

Revisions: 1
,
Comments: 1

__
TR13-158
| 18th November 2013
__

Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta#### Information-theoretic approximations of the nonnegative rank

Revisions: 3

__
TR13-159
| 20th November 2013
__

Per Austrin, Venkatesan Guruswami, Johan Håstad#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

__
TR13-160
| 20th November 2013
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Breaking the quadratic barrier for 3-LCCs over the Reals

__
TR13-161
| 23rd October 2013
__

Jack H. Lutz#### The Frequent Paucity of Trivial Strings

Revisions: 1

__
TR13-162
| 1st October 2013
__

Janka Chlebíková, Morgan Chopin#### The Firefighter Problem: A Structural Analysis

Revisions: 1

__
TR13-163
| 28th November 2013
__

Russell Impagliazzo, Valentine Kabanets#### Fourier Concentration from Shrinkage

Revisions: 2

__
TR13-164
| 28th November 2013
__

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian#### Weak Parity

__
TR13-165
| 28th November 2013
__

Michael Walfish, Andrew Blumberg#### Verifying computations without reexecuting them: from theoretical possibility to near-practicality

Revisions: 3

__
TR13-166
| 28th November 2013
__

Arnab Bhattacharyya#### On testing affine-invariant properties

__
TR13-167
| 28th November 2013
__

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma#### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

__
TR13-168
| 29th November 2013
__

Raghav Kulkarni, Avishay Tal#### On Fractional Block Sensitivity

Revisions: 1
,
Comments: 1

__
TR13-169
| 2nd December 2013
__

Benjamin Rossman#### Formulas vs. Circuits for Small Distance Connectivity

__
TR13-170
| 2nd December 2013
__

Venkatesan Guruswami, Carol Wang#### Explicit rank-metric codes list-decodable with optimal redundancy

__
TR13-171
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

__
TR13-172
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

__
TR13-173
| 28th November 2013
__

Anindya De, Rocco Servedio#### Efficient deterministic approximate counting for low degree polynomial threshold functions

__
TR13-174
| 6th December 2013
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for low-distance multilinear depth-$3$

__
TR13-175
| 6th December 2013
__

Venkatesan Guruswami, Chaoping Xing#### Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

__
TR13-176
| 8th December 2013
__

Daniel Kane, Osamu Watanabe#### A Short Implicant of CNFs with Relatively Many Satisfying Assignments

Revisions: 1
,
Comments: 1

__
TR13-177
| 10th December 2013
__

Eric Allender, Nikhil Balaji, Samir Datta#### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Revisions: 1

__
TR13-178
| 14th December 2013
__

Nikolay Vereshchagin#### Randomized communication complexity of appropximating Kolmogorov complexity

Revisions: 2

__
TR13-179
| 15th December 2013
__

Irit Dinur, David Steurer#### Direct Product Testing

__
TR13-180
| 17th December 2013
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### On Interactivity in Arthur-Merlin Communication and Stream Computation

Revisions: 1

__
TR13-181
| 20th December 2013
__

Mrinal Kumar, Shubhangi Saraf#### Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits

__
TR13-182
| 20th December 2013
__

Boaz Barak#### Structure vs Combinatorics in Computational Complexity

__
TR13-183
| 22nd December 2013
__

Yael Tauman Kalai, Ran Raz, Ron Rothblum#### How to Delegate Computations: The Power of No-Signaling Proofs

Revisions: 1

__
TR13-184
| 23rd December 2013
__

Boaz Barak, Jonathan Kelner, David Steurer#### Rounding Sum-of-Squares Relaxations

__
TR13-185
| 24th December 2013
__

Fu Li, Iddo Tzameret#### Generating Matrix Identities and Proof Complexity Lower Bounds

Revisions: 3

__
TR13-186
| 27th December 2013
__

Nitin Saxena#### Progress on Polynomial Identity Testing - II

__
TR13-187
| 27th December 2013
__

Peyman Afshani, Kevin Matulef, Bryan Wilkinson#### Property Testing on Linked Lists

Revisions: 1

__
TR13-188
| 13th December 2013
__

Christian Glaßer, Maximilian Witek#### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

__
TR13-189
| 21st December 2013
__

Periklis Papakonstantinou, Dominik Scheder, Hao Song#### Overlays and Limited Memory Communication Mode(l)s

__
TR13-190
| 28th December 2013
__

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson#### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

__
TR13-191
| 26th December 2013
__

Petr Savicky#### Boolean functions with a vertex-transitive group of automorphisms

Revisions: 2
,
Comments: 1

Gillat Kol, Ran Raz

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate $\epsilon$, where ... more >>>

Venkatesan Guruswami, Krzysztof Onak

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

Eric Miles, Emanuele Viola

We show how to efficiently compile any given circuit $C$

into a leakage-resistant circuit $\widehat{C}$ such that any

function on the wires of $\widehat{C}$ that leaks information

during a computation $\widehat{C}(x)$ yields advantage in

computing the product of $|\widehat{C}|^{\Omega(1)}$ elements

of the alternating group $A_u$. In combination with new

compression ...
more >>>

A. C. Cem Say, Abuzer Yakaryilmaz

We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. ... more >>>

Alexander A. Sherstov

We prove that the set disjointness problem has randomized communication complexity

$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement

on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum

protocols, where it is essentially tight. Proving it was an open problem since 1997, ...
more >>>

Balagopal Komarath, Jayalal Sarma

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al.(2011). Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this ... more >>>

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>

Adam Klivans, Raghu Meka

We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product ... more >>>

Zahra Jafargholi, Emanuele Viola

We show that if one can solve 3SUM on a set of size $n$

in time $n^{1+\epsilon}$ then one can list $t$ triangles in a

graph with $m$ edges in time $\tilde

O(m^{1+\epsilon}t^{1/3+\epsilon'})$ for any $\epsilon' > 0$. This is a

reversal of Patrascu's reduction from 3SUM to

listing triangles ...
more >>>

Yang Liu, Shengyu Zhang

Communication complexity of XOR functions $f (x \oplus y)$ has attracted increasing attention in recent years, because of its connections to Fourier analysis, and its exhibition of exponential separations between classical and quantum communication complexities of total functions.However, the complexity of certain basic functions still seems elusive especially in the ... more >>>

Nader Bshouty

In this paper we first show that Tester for an $F$-algebra $A$

and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear

algorithm for the product of elements in $A$

(see Algebraic

complexity theory. vol. 315, Springer-Verlag). Our

result is constructive in deterministic polynomial time. ...
more >>>

Hasan Abasi, Nader Bshouty

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>>

Daniel Apon, Jonathan Katz, Alex Malozemoff

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ for some predicate $f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>>

Zvika Brakerski, Moni Naor

Consider two parties who wish to communicate in order to execute some interactive protocol $\pi$. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits as he pleases, thus interrupting the execution of ... more >>>

Iordanis Kerenidis, Mathieu Laurière, David Xiao

Communication complexity is a central model of computation introduced by Yao in 1979, where

two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed

function f with the least amount of communication. Recently people have revisited the question of the ...
more >>>

Olaf Beyersdorff

Autoepistemic logic is one of the most successful formalisms for nonmonotonic reasoning. In this paper we provide a proof-theoretic analysis of sequent calculi for credulous and sceptical reasoning in propositional autoepistemic logic, introduced by Bonatti and Olivetti (ACM ToCL, 2002). We show that the calculus for credulous reasoning obeys almost ... more >>>

Pratik Worah

This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>>

Luke Friedman, Yixin Xu

A propositional proof system based on ordered binary decision diagrams (OBDDs) was introduced by Atserias et al. Krajicek proved exponential lower bounds for a strong variant of this system using feasible interpolation, and Tveretina et al. proved exponential lower bounds for restricted versions of this system for refuting formulas derived ... more >>>

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf

We consider the complexity of determining the winner of a finite, two-level poset game.

This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.

We give a simple formula allowing one to compute the status ...
more >>>

Tom Gur, Ran Raz

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.

... more >>>Kristoffer Arnsfelt Hansen, Vladimir Podolskii

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We ...
more >>>

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

Alexander A. Sherstov

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial

that approximates $f$ within $1/3$ at every point. We prove that the function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,

known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight

and closes a ...
more >>>

Valentine Kabanets, Antonina Kolokolova

We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

Luke Friedman

Propositional proof complexity is an area of complexity theory that addresses the question of whether the class NP is closed under complement, and also provides a theoretical framework for studying practical applications such as SAT solving.

Some of the most well-studied contradictions are random $k$-CNF formulas where each clause of ...
more >>>

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove

super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :

$\bullet$ As ... more >>>

Diptarka Chakraborty, C. Seshadhri

Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability $>2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to ... more >>>

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>>

Irit Dinur, Elazar Goldenberg

We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.

In ... more >>>

Mark Bun, Justin Thaler

The $\epsilon$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $\epsilon$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an ... more >>>

Michael Forbes, Amir Shpilka

Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In ... more >>>

Louay Bazzi, Nagi Nahas

Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We show in this paper that this goal is not achievable using small-bias spaces. Namely, we ... more >>>

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

We obtain a strong direct product theorem for two-party bounded round communication complexity.

Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses

at most C bits of communication in computing f(x,y) when (x,y)~\mu.

Jain et al. [JPY12] have recently showed that if

more >>>

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.

Our lower bounds also apply to the more restricted setting ...
more >>>

Alexander Knop

Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in HeurMA that cannot be solved by circuits of size $n^k$ on more ... more >>>

Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of ... more >>>

Arturs Backurs, Mohammad Bavarian

For a multilinear polynomial $p(x_1,...x_n)$, over the reals, the $L1$-influence is defined to be $\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where $x^i$ is $x$ with $i$-th bit swapped. If $p$ maps $\{-1,1\}^n$ to $[-1,1]$, we prove that the $L1$-influence of $p$ is upper bounded by a function of its degree (and independent of ... more >>>

Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh ... more >>>

Igor Sergeev

It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, ... more >>>

Siu Man Chan

The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>

Oded Goldreich, Avi Wigderson

We propose that multi-linear functions of relatively low degree

over GF(2) may be good candidates for obtaining exponential

lower bounds on the size of constant-depth Boolean circuits

(computing explicit functions).

Specifically, we propose to move gradually from linear functions

to multilinear ones, and conjecture that, for any $t\geq2$,

more >>>

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

Marek Karpinski, Michael Lampis, Richard Schmied

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>>

Venkatesan Guruswami, Chaoping Xing

We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank $1$, and designed to have an automorphism of large order that is used to ``fold" the AG code. ... more >>>

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek

We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.

Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>

Jin-Yi Cai, Aaron Gorenstein

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. ... more >>>

Amir Shpilka, Ben Lee Volk, Avishay Tal

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.

1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.

2. ... more >>>

Venkatesan Guruswami, Patrick Xia

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. Polar coding gives the *first known explicit construction* with rigorous ... more >>>

Eric Blais, Li-Yang Tan

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function.

In the first direction, our main positive results are the first non-trivial universal upper bounds on ...
more >>>

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture ... more >>>

Alan Guo

We present a general framework for constructing high rate error correcting codes that are locally correctable (and hence locally decodable if linear) with a sublinear number of queries, based on lifting codes with respect to functions on the coordinates. Our approach generalizes the lifting of affine-invariant codes of Guo, Kopparty, ... more >>>

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas ... more >>>

David Gamarnik, Madhu Sudan

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>

Gábor Braun, Sebastian Pokutta

We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance ... more >>>

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

Ilan Komargodski, Ran Raz, Avishay Tal

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the ``expected ... more >>>

Lior Gishboliner, Asaf Shapira

A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P ... more >>>

Venkatesan Guruswami, Swastik Kopparty

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

Zeev Dvir, Guangda Hu

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>>

Diptarka Chakraborty, C. Seshadhri

For positive integers $n, d$, consider the hypergrid $[n]^d$ with the coordinate-wise product partial ordering denoted by $\prec$.

A function $f: [n]^d \mapsto \mathbb{N}$ is monotone if $\forall x \prec y$, $f(x) \leq f(y)$.

A function $f$ is $\varepsilon$-far from monotone if at least an $\varepsilon$-fraction of values must ...
more >>>

Dung Nguyen, Alan Selman

We investigate autoreducibility properties of complete sets for $\cNEXP$ under different polynomial reductions.

Specifically, we show under some polynomial reductions that there is are complete sets for

$\cNEXP$ that are not autoreducible. We obtain the following results:

- There is a $\reduction{p}{tt}$-complete set for $\cNEXP$ that is not $\reduction{p}{btt}$-autoreducible.

more >>>

Anat Ganor, Ran Raz

In 1989, Babai, Nisan and Szegedy [BNS92] gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was $2^{\Theta(\sqrt n)}\,\,\,$, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for ... more >>>

Yijia Chen, Joerg Flum

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

Marek Karpinski, Richard Schmied

We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>>

Oded Goldreich

We consider three types of multiple input problems in the context of property testing.

Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}

\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:

Given a sequence of $m$ inputs, output a sequence ...
more >>>

Mrinal Kumar, Shubhangi Saraf

We study the class of homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuits, which are depth 4 homogenous circuits with top fanin bounded by $r$. We show that any homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuit computing the permanent of an $n\times n$ matrix must have size at least $\exp\left(n^{\Omega(1/r)}\right)$.

In a recent result, Gupta, Kamath, Kayal and ... more >>>

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

The following two decision problems capture the complexity of

comparing integers or rationals that are succinctly represented in

product-of-exponentials notation, or equivalently, via arithmetic

circuits using only multiplication and division gates, and integer

inputs:

Input instance: four lists of positive integers:

$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>

Iddo Tzameret

We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient *deterministic* refutation algorithm for random 3SAT with ... more >>>

Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

We study the problem of computing the minimum vertex cover on $k$-uniform $k$-partite hypergraphs when the $k$-partition is given. On bipartite graphs ($k=2$), the minimum vertex cover can be computed in polynomial time. For $k \ge 3$, this problem is known to be NP-hard. For general $k$, the problem was ... more >>>

Jan Johannsen

Resolution trees with lemmas ($\mathrm{RTL}$) are a resolution-based propositional proof system that is related to the DPLL algorithm with clause learning. Its fragments $\mathrm{RTL}(k)$ are related to clause learning algorithms where the width of learned clauses is bounded by $k$.

For every $k$ up to $O(\log n)$, an exponential separation ... more >>>

Oded Goldreich

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity

of property testing via communication complexity. They provided a restricted formulation of their methodology

(via ``simple combining operators'')

and also hinted towards a more general formulation, which we spell ...
more >>>

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

For a predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range $[\rho(f)-\Omega(1), \rho(f)+\Omega(1)]$.

We present a characterization of ... more >>>

Divesh Aggarwal, Chandan Dubey

We give several improvements on the known hardness of the unique shortest vector problem in lattices, i.e., the problem of finding a shortest vector in a given lattice given a promise that the shortest vector is unique upto a uniqueness factor $\gamma$.

We give a deterministic reduction from the ...
more >>>

Ján Pich

We prove that $T_{NC^1}$, the true universal first-order theory in the language containing names for all uniform $NC^1$ algorithms, cannot prove that for sufficiently large $n$, SAT is not computable by circuits of size $n^{2kc}$ where $k\geq 1, c\geq 4$ unless each function $f\in SIZE(n^k)$ can be approximated by formulas ... more >>>

Tom Gur, Ron Rothblum

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information ... more >>>

Dmitry Gavinsky, Shachar Lovett

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that ... more >>>

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

Non-malleable codes provide a useful and meaningful security 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 the original message, or a ... more >>>

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... more >>>

Miklos Ajtai

For each natural number $d$ we consider a finite structure ${\bf M}_{d}$ whose universe is the set of all $0,1$-sequence of length $n=2^{d}$, each representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace$ in binary form. The operations included in the structure are the four constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

Shachar Lovett

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>>

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>>

Omer Reingold, Thomas Steinke, Salil Vadhan

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

Hamed Hatami, Shachar Lovett

Let $\cal{P}$ be an affine invariant property of functions $\mathbb{F}_p^n \to [R]$ for fixed $p$ and $R$. We show that if $\cal{P}$ is locally testable with a constant number of queries, then one can estimate the distance of a function $f$ from $\cal{P}$ with a constant number of queries. This ... more >>>

Zachary Remscrim, Michael Sipser

A function $f:\Sigma^{*} \rightarrow \Sigma^{*}$ on strings is $AC^0$-pseudorandom if the pair $(x,\hat f(x))$ is $AC^0$-indistinguishable from a uniformly random pair $(y,z)$ when $x$ is chosen uniformly at random. Here $\hat f(x)$ is the string that is obtained from $f(x)$ by discarding some selected bits from $f(x)$.

It is shown ... more >>>

Abhishek Bhrushundi

A bent function is a Boolean function all of whose Fourier coefficients are equal in absolute value. These functions have been extensively studied in cryptography and play an important role in cryptanalysis and design of cryptographic systems.

We study bent functions in the framework of property testing. In particular, we ...
more >>>

Elena Grigorescu, Karl Wimmer, Ning Xie

We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions $P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$ is linear/affine invariant if for any $f\in P$, it is the case that $f\circ L\in P$ for any linear/affine transformation $L$ of the domain. Motivated by ... more >>>

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>

Pavel Pudlak, Arnold Beckmann, Neil Thapen

A propositional proof system is \emph{weakly automatizable} if there

is a polynomial time algorithm which separates satisfiable formulas

from formulas which have a short refutation in the system, with

respect to a given length bound. We show that if the resolution

proof system is weakly automatizable, ...
more >>>

Anna Gal, Jing-Tang Jang

Spira showed that any Boolean formula of size $s$ can be simulated in depth $O(\log s)$. We generalize Spira's theorem and show that any Boolean circuit of size $s$ with segregators of size $f(s)$ can be simulated in depth $O(f(s)\log s)$. If the segregator size is at least $s^{\varepsilon}$ for ... more >>>

Brendan Juba

We consider the proof search ("automatizability") problem for integrated learning and reasoning, a problem modeling certain kinds of data mining and common sense reasoning (Juba, 2013a). In such a problem, the approximate validity (i.e., under Valiant’s PAC-Semantics (Valiant, 2000)) of an input query formula over a background probability distribution is ... more >>>

Uriel Feige, Rani Izsak

Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items,

the welfare maximization problem requires that every item be allocated to exactly one player,

and one wishes to maximize the sum of values obtained by the players,

as computed ...
more >>>

Dana Ron, Rocco Servedio

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form

$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ...
more >>>

Mikolas Janota, Joao Marques-Silva

Over the years, proof systems for propositional satisfiability (SAT)

have been extensively studied. Recently, proof systems for

quantified Boolean formulas (QBFs) have also been gaining attention.

Q-resolution is a calculus enabling producing proofs from

DPLL-based QBF solvers. While DPLL has become a dominating technique

for SAT, QBF has been tackled ...
more >>>

Benny Applebaum, Yoni Moses

We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $H:\{0,1\}^n \rightarrow \{0,1\}^m$. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this ... more >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT

instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$

such that there is an explicit circuit $C$ that on input

an index $i$ of $\log |\phi|$ bits outputs the $i$th

clause, and each output bit of $C$ depends on ...
more >>>

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth $4$ arithmetic formula computing the product of $d$ generic matrices of size $n \times n$, IMM$_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d \leq n^{1/10}$. This improves the result of Nisan and Wigderson (Computational ... more >>>

Colin Jia Zheng, Salil Vadhan

We present a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game --- specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of ... more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix $M$ whose entries are homogeneous linear polynomials over the integers. Given a linear subspace $\mathcal{B}$ of the $n \times n$ matrices over some field $\mathbb{F}$, we consider ... more >>>

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous ... more >>>

Raghu Meka, Avi Wigderson

Finding cliques in random graphs and the closely related ``planted'' clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = ... more >>>

Shay Moran, Amir Yehudayoff

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize

the expected number of comparisons. We generalize Fredman's algorithm which

is a variant of insertion sort and provide a basically tight upper bound: If \mu is

more >>>

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves

security against a single corrupted party. Such protocols are typically easy

to construct as they may employ techniques that do not ...
more >>>

Rahul Santhanam, Ryan Williams

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability

of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$

quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error

randomized algorithms. This is the first known improvement over brute force search in ...
more >>>

Oded Goldreich, Dana Ron

The standard definition of property testing endows the tester with the ability to make arbitrary queries to ``elements''

of the tested object.

In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.

While sample-based testers were defined by

Goldreich, Goldwasser, and Ron ({\em JACM}\/ ...
more >>>

Xiaoming Sun, Marcos Villagra

There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper} we show that multiparty $\nqp$-communication can be exponentially stronger than $\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists ... more >>>

Gregory Valiant, Paul Valiant

We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete support $p=(p_1,p_2,\ldots,p_n)$, how many samples (independent draws) must one obtain from an unknown distribution, $q$, to distinguish, with high probability, the case that $p=q$ from the case that the total ... more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges.

We show that for complete and bipartite complete graphs, the exact perfect ... more >>>

Moritz Müller, Stefan Szeider

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>>

Parikshit Gopalan, Salil Vadhan, Yuan Zhou

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\begin{enumerate}

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ...
more >>>

Daniele Micciancio

The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>>

Albert Atserias, Moritz Müller, Sergi Oliva

The relativized weak pigeonhole principle states that if at least $2n$ out of $n^2$ pigeons fly into $n$ holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size $2^{(\log n)^{3/2-\epsilon}}$ for every $\epsilon > 0$ and every sufficiently ... more >>>

Igor Oliveira

Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

Emanuele Viola

We draw two incomplete, biased maps of challenges in

computational complexity lower bounds. Our aim is to put

these challenges in perspective, and to present some

connections which do not seem widely known.

Zeyu Guo

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>

Irit Dinur, Venkatesan Guruswami

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>>

Joshua Grochow, Youming Qiao

The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>>

Thomas Watson

We consider the problems of deciding whether the joint distribution sampled by a given circuit satisfies certain statistical properties such as being i.i.d., being exchangeable, being pairwise independent, having two coordinates with identical marginals, having two uncorrelated coordinates, and many other variants. We give a proof that simultaneously shows all ... more >>>

Venkatesan Guruswami, Euiwoong Lee

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

Arman Fazeli, Shachar Lovett, Alex Vardy

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known ... more >>>

Paul Beame, Raphael Clifford, Widad Machmouchi

We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time $T$ and space $S$ ... more >>>

Pavel Hrubes

We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system.

We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two ... more >>>

Adam Klivans, Pravesh Kothari, Igor Oliveira

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... more >>>

Mark Braverman, Ankit Garg

We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We show that if using private randomness a message can be transmitted while revealing $I$ bits of information, the transmission can be ... more >>>

Nikhil Balaji, Samir Datta

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$

for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]

more >>>

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... more >>>

Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland

Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by ... more >>>

Or Meir

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>>

Scott Aaronson

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random ... more >>>

Paul Goldberg, Aaron Roth

We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... more >>>

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

We qualitatively separate semi-honest secure computation of non-trivial secure-function evaluation (SFE) functionalities from existence of key-agreement protocols.

Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any ...
more >>>

Itai Benjamini, Gil Cohen, Igor Shinkar

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every ... more >>>

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

We study the complexity of detecting monomials

with special properties in the sum-product

expansion of a polynomial represented by an arithmetic

circuit of size polynomial in the number of input

variables and using only multiplication and addition.

We focus on monomial properties expressed in terms

of the number of distinct ...
more >>>

Atri Rudra, Mary Wootters

We show that any $q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius $1 - 1/q - \epsilon$ with near-optimal rate and list sizes.

Our results imply that ``most" Reed-Solomon codes are list decodable ... more >>>

Leonid Gurvits

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with

boolean matrices with prescribed row and (uniformly bounded) column sums within simply ...
more >>>

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of the complexity in another model of computation called parity decision trees. ... more >>>

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman

Let $G:\{0,1\}^n\to\{0,1\}^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is $(k,q)$-robust if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ ... more >>>

VyasRam Selvam

We explore the implications of the two queries assumption, $P^{NP[1]}=P_{||}^{NP[2]}$, with respect to the polynomial hierarchy and the classes $AM$ and $MA$.

We prove the following results:

1. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $AM = MA$

2. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH \subset MA_{/1}$

3. $\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}$ and $NP^B \not\subseteq coMA^B$.

4. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH ...
more >>>

Gil Cohen, Avishay Tal

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$ is called {\it approximation resistant} if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment that satisfies at least $\rho(f)+\Omega(1)$ fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

Adam Bouland, Scott Aaronson

In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m by m unitary transformations (or orthogonal transformations, in the real case) ... more >>>

Irit Dinur, Igor Shinkar

For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games ... more >>>

Albert Atserias, Neil Thapen

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on ... more >>>

Mark Bun, Justin Thaler

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit ... more >>>

Oded Goldreich, Avi Wigderson

{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:

For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ...
more >>>

Mrinal Kumar, Shubhangi Saraf

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of {\it depth reduction} developed in the works of Agrawal-Vinay [AV08], Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partial derivative complexity measure ... more >>>

Martin Schwarz, Maarten Van den Nest

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained ... more >>>

Gil Cohen, Amnon Ta-Shma

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>

Jan Krajicek

We give a general reduction of lengths-of-proofs lower bounds for

constant depth Frege systems in DeMorgan language augmented by

a connective counting modulo a prime $p$

(the so called $AC^0[p]$ Frege systems)

to computational complexity

lower bounds for search tasks involving search trees branching upon

values of linear maps on ...
more >>>

Bin Fu

We show that

derandomizing polynomial identity testing over an arbitrary finite

field implies that NEXP does not have polynomial size boolean

circuits. In other words, for any finite field F(q) of size q,

$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where

$PIT_q$ is the polynomial identity testing problem over F(q), and

NSUBEXP is ...
more >>>

Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Common information was introduced by Wyner as a measure of dependence of two

random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such

as communication ...
more >>>

Per Austrin, Venkatesan Guruswami, Johan Håstad

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+\lambda}$ for some fixed, positive $\lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then ... more >>>

Jack H. Lutz

A 1976 theorem of Chaitin, strengthening a 1969 theorem of Meyer,says that infinitely many lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. ... more >>>

Janka Chlebíková, Morgan Chopin

We consider the complexity of the firefighter problem where ${b \geq 1}$ firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree $b+3$ for any fixed budget ... more >>>

Russell Impagliazzo, Valentine Kabanets

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on ``small-degree'' coefficients. For a Boolean function $f:\{0,1\}^n\to\{1,-1\}$ computable by a de Morgan formula of size $s$, we show that

\[

\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ...
more >>>

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

Michael Walfish, Andrew Blumberg

How can we trust results computed by a third party, or the integrity of data stored by such a party? This is a classic question in systems security, and it is particularly relevant in the context of cloud computing.

Various solutions have been proposed that make assumptions about the class ... more >>>

Arnab Bhattacharyya

An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has ... more >>>

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the “short code” of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

In particular, we prove quasi-NP-hardness of the following problems on ... more >>>

Raghav Kulkarni, Avishay Tal

In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and

Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by $fbs(f)$, and showed

that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by $RC(f)$, which ...
more >>>

Benjamin Rossman

We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance $k(n)$ Connectivity, which asks whether two specified nodes in a graph of size $n$ are connected by a path of length at most $k(n)$. This problem is solvable (by ... more >>>

Venkatesan Guruswami, Carol Wang

We construct an explicit family of linear rank-metric codes over any field ${\mathbb F}_h$ that enables efficient list decoding up to a fraction $\rho$ of errors in the rank metric with a rate of $1-\rho-\epsilon$, for any desired $\rho \in (0,1)$ and $\epsilon > 0$. Previously, a Monte Carlo construction ... more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates \[

\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1] \]

to within an additive $\pm \eps$. For any constant ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates

\[

\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]

\]

to within an additive $\pm \eps$ in ...
more >>>

Anindya De, Rocco Servedio

We give a deterministic algorithm for

approximately counting satisfying assignments of a degree-$d$ polynomial threshold function

(PTF).

Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$

and a parameter $\epsilon > 0$, our algorithm approximates

$

\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]

$

to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ...
more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper we take a step towards designing such hitting-sets. We define a notion of ... more >>>

Venkatesan Guruswami, Chaoping Xing

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>

Daniel Kane, Osamu Watanabe

Consider any Boolean function $F(X_1,\ldots,X_N)$ that has more than $2^{-N^{d}}$ satisfying assignments and that can be expressed by a CNF formula with at most $N^{1+e}$ clauses for some $d>0$ and $e>0$ such that $d+e$ is less than $1$ (*). Then how many variables do we need to fix in order ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

Nikolay Vereshchagin

The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$, and they want to compute or approximate

more >>>

Irit Dinur, David Steurer

A direct product is a function of the form $g(x_1,\ldots,x_k)=(g_1(x_1),\ldots,g_k(x_k))$. We show that the direct product property is locally testable with $2$ queries, that is, a canonical two-query test distinguishes between direct products and functions that are from direct products with constant probability.

This local testing question comes up ... more >>>

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

We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>>

Mrinal Kumar, Shubhangi Saraf

In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree $n$ in $n^2$ variables such that any homogeneous depth 4 arithmetic circuit computing it must have size $n^{\Omega(\log \log n)}$.

Our results extend ... more >>>

Boaz Barak

Some computational problems seem to have a certain "structure" that is manifested in non-trivial algorithmic properties, while others are more "unstructured" in the sense that they are either "very easy" or "very hard". I survey some of the known results and open questions about this classification and its connections to ... more >>>

Yael Tauman Kalai, Ran Raz, Ron Rothblum

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. ... more >>>

Boaz Barak, Jonathan Kelner, David Steurer

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>>

Fu Li, Iddo Tzameret

Motivated by the fundamental lower bounds questions in proof complexity, we investigate the complexity of generating identities of matrix rings, and related problems. Specifically, for a field $\mathbb{F}$ let $A$ be a non-commutative (associative) $\mathbb{F}$-algebra (e.g., the algebra Mat$_d(\mathbb{F})\;$ of $d\times d$ matrices over $\mathbb{F}$). We say that a non-commutative ... more >>>

Nitin Saxena

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.

more >>>Peyman Afshani, Kevin Matulef, Bryan Wilkinson

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is ... more >>>

Christian Glaßer, Maximilian Witek

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:

- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.

- For P, the delta-levels of ...
more >>>

Periklis Papakonstantinou, Dominik Scheder, Hao Song

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function $f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>>

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

Petr Savicky

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.