A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

**I**

__
TR21-036
| 14th March 2021
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan#### Ideal-theoretic Explanation of Capacity-achieving Decoding

__
TR21-172
| 1st December 2021
__

Robert Andrews, Michael Forbes#### Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals

__
TR04-058
| 28th May 2004
__

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan#### Identifying Clusters from Positive Data

__
TR15-184
| 21st November 2015
__

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk#### Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs

__
TR16-193
| 22nd November 2016
__

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S#### Identity Testing for +-Regular Noncommutative Arithmetic Circuits

__
TR16-009
| 28th January 2016
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Identity Testing for constant-width, and commutative, read-once oblivious ABPs

__
TR20-187
| 13th December 2020
__

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### If VNP is hard, then so are equations for it

__
TR03-055
| 20th July 2003
__

Jan Krajicek#### Implicit proofs

__
TR07-028
| 12th February 2007
__

Daniel Sawitzki#### Implicit Simulation of FNC Algorithms

__
TR00-039
| 25th April 2000
__

Yevgeniy Dodis#### Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping

__
TR20-098
| 4th July 2020
__

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf#### Impossibility of Derandomizing the Isolation Lemma for all Families

__
TR11-001
| 2nd January 2011
__

Scott Aaronson#### Impossibility of Succinct Quantum Proofs for Collision-Freeness

__
TR19-093
| 15th July 2019
__

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari#### Improved 3LIN Hardness via Linear Label Cover

__
TR06-110
| 15th August 2006
__

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai#### Improved Algorithms for Optimal Embeddings

__
TR15-112
| 16th July 2015
__

Ruiwen Chen, Rahul Santhanam#### Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP

__
TR10-041
| 11th March 2010
__

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer#### Improved Algorithms for Unique Games via Divide and Conquer

__
TR09-076
| 19th August 2009
__

Christian Glaßer, Christian Reitwießner, Maximilian Witek#### Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman

Revisions: 1

__
TR20-020
| 21st February 2020
__

Nikhil Mande, Justin Thaler, Shuchen Zhu#### Improved Approximate Degree Bounds For $k$-distinctness

__
TR07-120
| 5th October 2007
__

Sharon Feldman, Guy Kortsarz, Zeev Nutov#### Improved approximation algorithms for directed Steiner forest

__
TR03-008
| 11th February 2003
__

Piotr Berman, Marek Karpinski#### Improved Approximation Lower Bounds on Small Occurrence Optimization

__
TR00-021
| 19th April 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### Improved Approximation of MAX-CUT on Graphs of Bounded Degree

__
TR01-097
| 11th December 2001
__

Piotr Berman, Marek Karpinski#### Improved Approximations for General Minimum Cost Scheduling

__
TR13-058
| 5th April 2013
__

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

Revisions: 2

__
TR05-159
| 14th November 2005
__

Daniel Rolf#### Improved Bound for the PPSZ/Schöning-Algorithm for $3$-SAT

__
TR10-192
| 8th December 2010
__

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao#### Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR19-164
| 6th November 2019
__

Siddharth Bhandari, Sayantan Chakraborty#### Improved bounds for perfect sampling of $k$-colorings in graphs

Revisions: 1

__
TR16-191
| 24th November 2016
__

Roei Tell#### Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials

Revisions: 3

__
TR19-110
| 23rd August 2019
__

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang#### Improved bounds for the sunflower lemma

__
TR18-167
| 25th September 2018
__

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf#### Improved bounds on Fourier entropy and Min-entropy

Revisions: 1

__
TR19-171
| 27th November 2019
__

Oded Goldreich#### Improved bounds on the AN-complexity of multilinear functions

Revisions: 5

__
TR16-075
| 9th May 2016
__

Mark Bun, Justin Thaler#### Improved Bounds on the Sign-Rank of AC$^0$

Revisions: 1

__
TR16-073
| 7th May 2016
__

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev#### Improved concrete efficiency and security analysis of Reed-Solomon PCPPs

Revisions: 1
,
Comments: 1

__
TR10-190
| 9th December 2010
__

Xin Li#### Improved Constructions of Three Source Extractors

__
TR15-125
| 5th August 2015
__

Xin Li#### Improved Constructions of Two-Source Extractors

Revisions: 2

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

Revisions: 2

__
TR98-043
| 27th July 1998
__

Venkatesan Guruswami, Madhu Sudan#### Improved decoding of Reed-Solomon and algebraic-geometric codes.

__
TR10-080
| 5th May 2010
__

Andrew Drucker#### Improved Direct Product Theorems for Randomized Query Complexity

Revisions: 1

__
TR18-110
| 4th June 2018
__

Fu Li, David Zuckerman#### Improved Extractors for Recognizable and Algebraic Sources

Revisions: 1

__
TR13-076
| 15th May 2013
__

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

Revisions: 1

__
TR21-062
| 29th April 2021
__

Vishwas Bhargava, Sumanta Ghosh#### Improved Hitting Set for Orbit of ROABPs

Revisions: 2

__
TR09-107
| 28th October 2009
__

Kevin Dick, Chris Umans#### Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

__
TR09-099
| 16th October 2009
__

Venkatesan Guruswami, Ali Kemal Sinop#### Improved Inapproximability Results for Maximum k-Colorable Subgraph

Revisions: 1

__
TR20-048
| 16th April 2020
__

Shachar Lovett, Raghu Meka, Jiapeng Zhang#### Improved lifting theorems via robust sunflowers

__
TR20-168
| 11th November 2020
__

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters#### Improved List-Decodability of Reed–Solomon Codes via Tree Packings

__
TR22-078
| 8th May 2022
__

Dan Karliner, Amnon Ta-Shma#### Improved local testing for multiplicity codes

__
TR97-003
| 29th January 1997
__

Sanjeev Arora, Madhu Sudan#### Improved low-degree testing and its applications

__
TR22-064
| 2nd May 2022
__

Deepanshu Kush, Shubhangi Saraf#### Improved Low-Depth Set-Multilinear Circuit Lower Bounds

__
TR06-017
| 12th January 2006
__

Toshiya Itoh#### Improved Lower Bounds for Families of $\varepsilon$-Approximate k$-Restricted Min-Wise Independent Permutations

__
TR07-010
| 4th January 2007
__

Arist Kojevnikov#### Improved Lower Bounds for Resolution over Linear Inequalities

Revisions: 1

__
TR11-156
| 23rd November 2011
__

Marek Karpinski, Richard Schmied#### Improved Lower Bounds for the Shortest Superstring and Related Problems

Revisions: 1

__
TR21-025
| 15th February 2021
__

Sivakanth Gopi, Venkatesan Guruswami#### Improved Maximally Recoverable LRCs using Skew Polynomials

__
TR21-165
| 21st November 2021
__

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams#### Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

Revisions: 1

__
TR14-123
| 7th October 2014
__

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

__
TR96-016
| 6th February 1996
__

Andrea E. F. Clementi, Luca Trevisan#### Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

__
TR16-115
| 30th July 2016
__

Xin Li#### Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors

__
TR95-053
| 15th October 1995
__

Petr Slavik#### Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems

__
TR21-099
| 4th July 2021
__

Louis Golowich#### Improved Product-Based High-Dimensional Expanders

__
TR22-021
| 19th February 2022
__

Xin Lyu#### Improved Pseudorandom Generators for $\mathrm{AC}^0$ Circuits

__
TR09-141
| 19th December 2009
__

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani#### Improved Pseudorandom Generators for Depth 2 Circuits

__
TR17-171
| 6th November 2017
__

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal#### Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

__
TR12-138
| 2nd November 2012
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Improved rank bounds for design matrices and a new proof of Kelly's theorem

__
TR01-055
| 26th July 2001
__

Alexander Razborov#### Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

__
TR11-110
| 10th August 2011
__

Alessandro Chiesa, Michael Forbes#### Improved Soundness for QMA with Multiple Provers

Revisions: 1

__
TR99-017
| 4th June 1999
__

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky#### Improved Testing Algorithms for Monotonicity.

Revisions: 1

__
TR03-053
| 8th July 2003
__

Kazuo Iwama, Suguru Tamaki#### Improved Upper Bounds for 3-SAT

__
TR03-010
| 13th February 2003
__

Sven Baumer, Rainer Schuler#### Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs

__
TR06-078
| 12th June 2006
__

Tobias Riege, Jörg Rothe#### Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem

Revisions: 1

__
TR11-167
| 6th December 2011
__

Nikolay Vereshchagin#### Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances''

Revisions: 1

__
TR04-069
| 13th August 2004
__

Eran Rom, Amnon Ta-Shma#### Improving the alphabet size in high noise, almost optimal rate list decodable codes

Revisions: 2

__
TR10-135
| 24th August 2010
__

Oded Goldreich#### In a World of P=BPP

Revisions: 2

__
TR11-039
| 19th March 2011
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### In Brute-Force Search of Correlation Bounds for Polynomials

__
TR09-045
| 20th May 2009
__

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee#### Inaccessible Entropy

__
TR04-065
| 28th July 2004
__

Luca Trevisan#### Inapproximability of Combinatorial Optimization Problems

Revisions: 1

__
TR07-113
| 15th November 2007
__

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang#### Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

__
TR14-006
| 16th January 2014
__

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

Revisions: 1

__
TR18-037
| 21st February 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Inapproximability of Matrix $p \rightarrow q$ Norms

__
TR13-071
| 8th May 2013
__

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

__
TR15-093
| 5th June 2015
__

Aviad Rubinstein#### Inapproximability of Nash Equilibrium

__
TR12-020
| 3rd March 2012
__

Daniele Micciancio#### Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

Revisions: 1

__
TR03-026
| 20th February 2003
__

Janka Chlebíková, Miroslav Chlebik#### Inapproximability results for bounded variants of optimization problems

__
TR02-030
| 3rd June 2002
__

Lars Engebretsen, Jonas Holmerin, Alexander Russell#### Inapproximability Results for Equations over Finite Groups

Revisions: 1

__
TR06-052
| 15th April 2006
__

Wenbin Chen, Jiangtao Meng#### Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm

__
TR15-113
| 9th July 2015
__

Amit Chakrabarti, Tony Wirth#### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

__
TR06-044
| 24th January 2006
__

Andreas Björklund, Thore Husfeldt#### Inclusion-Exclusion Based Algorithms for Graph Colouring

__
TR15-051
| 5th April 2015
__

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang#### Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

__
TR22-032
| 1st March 2022
__

Iftach Haitner, Noam Mazor, Jad Silbak#### Incompressiblity and Next-Block Pseudoentropy

__
TR04-081
| 9th September 2004
__

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin#### Increasing Kolmogorov Complexity

__
TR05-136
| 14th November 2005
__

Anna Gal, Michal Koucky, Pierre McKenzie#### Incremental branching programs

__
TR18-042
| 1st March 2018
__

Stasys Jukna#### Incremental versus Non-Incremental Dynamic Programming

__
TR00-035
| 6th June 2000
__

Nikolay Vereshchagin, Mikhail V. Vyugin#### Independent minimum length programs to translate between given strings

__
TR18-061
| 6th April 2018
__

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola#### Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs

Revisions: 5

__
TR16-092
| 3rd June 2016
__

Gilad Asharov, Alon Rosen, Gil Segev#### Indistinguishability Obfuscation Does Not Reduce to Structured Languages

Revisions: 1

__
TR20-126
| 19th August 2020
__

Aayush Jain, Huijia Lin, Amit Sahai#### Indistinguishability Obfuscation from Well-Founded Assumptions

__
TR07-017
| 18th January 2007
__

Ashish Rastogi, Richard Cole#### Indivisible Markets with Good Approximate EquilibriumPrices

Revisions: 1

__
TR14-019
| 14th February 2014
__

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

__
TR07-096
| 8th October 2007
__

Lance Fortnow, Rahul Santhanam#### Infeasibility of Instance Compression and Succinct PCPs for NP

__
TR06-010
| 1st December 2005
__

Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag#### Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

__
TR06-051
| 8th April 2006
__

Alan Nash, Russell Impagliazzo, Jeff Remmel#### Infinitely-Often Universal Languages and Diagonalization

__
TR21-111
| 19th July 2021
__

Aniruddha Biswas, Palash Sarkar#### Influence of a Set of Variables on a Boolean Function

Revisions: 2

__
TR15-060
| 14th April 2015
__

Omri Weinstein#### Information Complexity and the Quest for Interactive Compression

Revisions: 1

__
TR15-070
| 22nd April 2015
__

Himanshu Tyagi, Shaileshh Venkatakrishnan , Pramod Viswanath, Shun Watanabe#### Information Complexity Density and Simulation of Protocols

Revisions: 1

__
TR14-132
| 23rd October 2014
__

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

Revisions: 2

__
TR15-023
| 10th February 2015
__

Mark Braverman, Jon Schneider#### Information complexity is computable

__
TR10-076
| 18th April 2010
__

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor#### Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

Revisions: 1

__
TR00-016
| 29th February 2000
__

Mikhail V. Vyugin#### Information Distance and Conditional Complexities

__
TR21-053
| 13th April 2021
__

Jan Krajicek#### Information in propositional proofs and algorithmic proof search

__
TR12-177
| 19th December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### Information lower bounds via self-reducibility

__
TR17-078
| 21st April 2017
__

Nico Döttling, Jesper Buus Nielsen, Maceij Obremski#### Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model

Revisions: 1

__
TR16-078
| 9th May 2016
__

Gregory Valiant, Paul Valiant#### Information Theoretically Secure Databases

__
TR04-068
| 13th August 2004
__

Nir Ailon, Bernard Chazelle#### Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

__
TR17-182
| 21st November 2017
__

Mark Braverman, Young Kun Ko#### Information Value of Two-Prover Games

__
TR13-158
| 18th November 2013
__

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

Revisions: 3

__
TR01-015
| 9th February 2001
__

Amos Beimel, Yuval Ishai#### Information-Theoretic Private Information Retrieval: A Unified Construction

__
TR15-029
| 18th February 2015
__

Stanislav Zak#### Inherent logic and complexity

__
TR17-184
| 29th November 2017
__

Vladimir Podolskii, Alexander A. Sherstov#### Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

__
TR11-012
| 2nd February 2011
__

Andrej Bogdanov, Alon Rosen#### Input locality and hardness amplification

__
TR11-023
| 16th February 2011
__

Oded Goldreich, Or Meir#### Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Revisions: 5
,
Comments: 2

__
TR09-022
| 16th February 2009
__

Jack H. Lutz, Elvira Mayordomo#### Inseparability and Strong Hypotheses for Disjoint NP Pairs

Revisions: 1

__
TR19-113
| 5th September 2019
__

Tomer Grossman, Ilan Komargodski, Moni Naor#### Instance Complexity and Unlabeled Certificates in the Decision Tree Model

__
TR12-077
| 10th June 2012
__

Chiranjit Chakraborty, Rahul Santhanam#### Instance Compression for the Polynomial Hierarchy and Beyond

Comments: 2

__
TR13-111
| 17th August 2013
__

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

__
TR08-068
| 3rd July 2008
__

Lior Malka#### Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs

__
TR23-029
| 18th March 2023
__

Nicollas Sdroievski, Dieter van Melkebeek#### Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

__
TR00-012
| 14th February 2000
__

Ke Yang#### Integer Circuit Evaluation is PSPACE-complete

__
TR13-001
| 2nd January 2013
__

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

Revisions: 1

__
TR17-093
| 22nd May 2017
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Coding Over the Noisy Broadcast Channel

__
TR18-054
| 24th March 2018
__

Klim Efremenko, Elad Haramaty, Yael Kalai#### Interactive Coding with Constant Round and Communication Blowup

Revisions: 1

__
TR22-146
| 9th November 2022
__

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai#### Interactive Coding with Small Memory

__
TR15-168
| 18th October 2015
__

Gillat Kol#### Interactive Compression for Product Distributions

__
TR20-022
| 19th February 2020
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Error Resilience Beyond $\frac{2}{7}$

Revisions: 1

__
TR11-123
| 15th September 2011
__

Mark Braverman#### Interactive information complexity

__
TR10-020
| 19th February 2010
__

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai#### Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

__
TR20-165
| 6th November 2020
__

Sarah Bordage, Jade Nardi#### Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

Revisions: 3

__
TR07-031
| 26th March 2007
__

Yael Tauman Kalai, Ran Raz#### Interactive PCP

__
TR20-058
| 24th April 2020
__

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff#### Interactive Proofs for Verifying Machine Learning

Revisions: 1

__
TR10-187
| 3rd December 2010
__

Gus Gutoski#### Interactive proofs with competing teams of no-signaling provers

Revisions: 2

__
TR99-024
| 25th June 1999
__

Oded Goldreich, Silvio Micali.#### Interleaved Zero-Knowledge in the Public-Key Model.

Revisions: 1
,
Comments: 1

__
TR14-101
| 8th August 2014
__

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

Revisions: 1

__
TR97-015
| 21st April 1997
__

Jan Krajicek#### Interpolation by a game

__
TR12-032
| 4th April 2012
__

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe#### Interval graph representation with given interval and intersection lengths

__
TR10-043
| 5th March 2010
__

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky#### Interval Graphs: Canonical Representation in Logspace

Revisions: 1

__
TR10-082
| 11th May 2010
__

Oded Goldreich#### Introduction to Testing Graph Properties

__
TR10-051
| 26th March 2010
__

Madhu Sudan#### Invariance in Property Testing

__
TR07-123
| 21st November 2007
__

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky#### Inverse Conjecture for the Gowers norm is false

Revisions: 2

__
TR12-152
| 7th November 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Inverse Problems in Approximate Uniform Generation

__
TR21-003
| 6th January 2021
__

Lijie Chen, Xin Lyu#### Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma

__
TR10-121
| 28th July 2010
__

Ashwin Nayak#### Inverting a permutation is as hard as unordered search

Revisions: 1

__
TR06-024
| 18th February 2006
__

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin#### Inverting onto functions might not be hard

__
TR99-041
| 22nd August 1999
__

Oliver Kullmann#### Investigating a general hierarchy of polynomially decidable classes of CNF's based on short tree-like resolution proofs

Revisions: 2

__
TR10-137
| 29th August 2010
__

Or Meir#### IP = PSPACE using Error Correcting Codes

Revisions: 7

__
TR17-179
| 20th November 2017
__

Alexander Knop#### IPS-like Proof Systems Based on Binary Decision Diagrams

__
TR12-084
| 3rd July 2012
__

Rahul Santhanam#### Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds

__
TR17-016
| 31st January 2017
__

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena#### Irreducibility and deterministic r-th root finding over finite fields

__
TR98-003
| 3rd November 1997
__

I. Cahit, M. Tezer#### Irregular Assignments of the Forest of Paths

__
TR02-053
| 20th July 2002
__

Lars Engebretsen, Venkatesan Guruswami#### Is Constraint Satisfaction Over Two Variables Always Easy?

__
TR20-051
| 15th April 2020
__

Rafael Pass, Muthuramakrishnan Venkitasubramaniam#### Is it Easier to Prove Theorems that are Guaranteed to be True?

__
TR20-094
| 24th June 2020
__

Ronen Shaltiel#### Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

__
TR11-151
| 9th November 2011
__

Valentine Kabanets, Osamu Watanabe#### Is the Valiant-Vazirani Isolation Lemma Improvable?

Revisions: 2

__
TR15-146
| 7th September 2015
__

Elette Boyle, Moni Naor#### Is There an Oblivious RAM Lower Bound?

Revisions: 1

__
TR17-127
| 12th August 2017
__

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi#### Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Revisions: 1

__
TR16-155
| 10th October 2016
__

Vaibhav Krishan, Nutan Limaye#### Isolation Lemma for Directed Reachability and NL vs. L

__
TR10-194
| 9th December 2010
__

Thanh Minh Hoang#### Isolation of Matchings via Chinese Remaindering

__
TR98-019
| 5th April 1998
__

Eric Allender, Klaus Reinhardt#### Isolation, Matching, and Counting

__
TR11-137
| 14th October 2011
__

Vikraman Arvind, Yadu Vasudev#### Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits

__
TR20-174
| 18th November 2020
__

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova#### Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

__
TR14-104
| 9th August 2014
__

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

__
TR21-138
| 23rd September 2021
__

Rahul Santhanam, Iddo Tzameret#### Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

__
TR06-123
| 15th September 2006
__

Venkatesan Guruswami, Venkatesan Guruswami#### Iterative Decoding of Low-Density Parity Check Codes (A Survey)

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithm. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and their ... more >>>

Robert Andrews, Michael Forbes

We show that any nonzero polynomial in the ideal generated by the $r \times r$ minors of an $n \times n$ matrix $X$ can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial $f$ in this ideal, we construct a small depth-three $f$-oracle circuit that approximates the ... more >>>

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

The present work studies clustering from an abstract point of view

and investigates its properties in the framework of inductive inference.

Any class $S$ considered is given by a numbering

$A_0,A_1,...$ of nonempty subsets of the natural numbers

or the rational k-dimensional vector space as a hypothesis space.

A clustering ...
more >>>

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs).

In this work, we give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a ...
more >>>

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

An efficient randomized polynomial identity test for noncommutative

polynomials given by noncommutative arithmetic circuits remains an

open problem. The main bottleneck to applying known techniques is that

a noncommutative circuit of size $s$ can compute a polynomial of

degree exponential in $s$ with a double-exponential number of nonzero

monomials. ...
more >>>

Rohit Gurjar, Arpita Korwar, Nitin Saxena

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost $(nw)^{O(\log n)}$, where $n$ is the number of variables and $w$ is the width of ... more >>>

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP *does not* have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size.

In a ... more >>>

Jan Krajicek

We describe a general method how to construct from

a propositional proof system P a possibly much stronger

proof system iP. The system iP operates with

exponentially long P-proofs described ``implicitly''

by polynomial size circuits.

As an example we prove that proof system iEF, implicit EF,

corresponds to bounded ...
more >>>

Daniel Sawitzki

Implicit algorithms work on their input's characteristic functions and should solve problems heuristically by as few and as efficient functional operations as possible. Together with an appropriate data structure to represent the characteristic functions they yield heuristics which are successfully applied in numerous areas. It is known that implicit algorithms ... more >>>

Yevgeniy Dodis

Collective Coin-Flipping is a classical problem where n

computationally unbounded processors are trying to generate a random

bit in a setting where only a single broadcast channel is available

for communication. The protocol is said to be b(n)-resilient if any

adversary that can corrupt up to b(n) players, still cannot ...
more >>>

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

Scott Aaronson

We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right] $ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right) $ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

In the last decade, the notion of metric embeddings with

small distortion received wide attention in the literature, with

applications in combinatorial optimization, discrete mathematics, functional

analysis and bio-informatics. The notion of embedding is, given two metric

spaces on the same number of points, to find a bijection that minimizes

more >>>

Ruiwen Chen, Rahul Santhanam

We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-$k$-CSP. For instances with $n$ variables and $cn$ clauses (constraints), we give algorithms running in time $\poly(n)\cdot 2^{n(1-\mu)}$ for

\begin{itemize}

\item $\mu = \Omega(\frac{1}{c} )$ and polynomial space solving MAX-SAT and MAX-$k$-SAT,

\item $\mu = \Omega(\frac{1}{\sqrt{c}} )$ and ...
more >>>

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>>

Christian Glaßer, Christian Reitwießner, Maximilian Witek

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

Nikhil Mande, Justin Thaler, Shuchen Zhu

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

Sharon Feldman, Guy Kortsarz, Zeev Nutov

We consider the k-Directed Steiner Forest} (k-dsf) problem:

given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V

of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph

H of G

that contains an st-path for (at least) k ...
more >>>

Piotr Berman, Marek Karpinski

We improve a number of approximation lower bounds for

bounded occurrence optimization problems like MAX-2SAT,

E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching.

Uriel Feige, Marek Karpinski, Michael Langberg

We analyze the addition of a simple local improvement step to various known

randomized approximation algorithms.

Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently

known for the Max Cut problem on general graphs~\cite{GW95}.

We consider a semidefinite relaxation of the Max Cut problem,

round it using the ...
more >>>

Piotr Berman, Marek Karpinski

We give improved trade-off results on approximating general

minimum cost scheduling problems.

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 >>>

Daniel Rolf

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, Schöning proved ... more >>>

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

Siddharth Bhandari, Sayantan Chakraborty

We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k > 3\Delta$, and returns a random proper $k$-coloring of $G$. The

distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; ...
more >>>

Roei Tell

Goldreich and Wigderson (STOC 2014) initiated a study of quantified derandomization, which is a relaxed derandomization problem: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, the problem is to decide whether a circuit $C\in\mathcal{C}$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs.

In ... more >>>

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

A sunflower with $r$ petals is a collection of $r$ sets so that the

intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ...
more >>>

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf

Given a Boolean function $f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of $[n]$, where each $S\subseteq [n]$ is sampled with probability $\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>

Oded Goldreich

We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number.

This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ...
more >>>

Mark Bun, Justin Thaler

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.

PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. ...
more >>>

Xin Li

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on $n$ bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy $0.499n$ \cite{Bourgain05}, and the ... more >>>

Xin Li

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{\Omega(1)}$, while the error remains $n^{-\Omega(1)}$.

... more >>>Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions ... more >>>

Venkatesan Guruswami, Madhu Sudan

We present an improved list decoding algorithm for decoding

Reed-Solomon codes. Given an arbitrary string of length n, the

list decoding problem is that of finding all codewords within a

specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon

codes reduces to the ...
more >>>

Andrew Drucker

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.

We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm

has success probability at ...
more >>>

Fu Li, David Zuckerman

We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = v} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources.

Our first method shows that ...
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 >>>

Vishwas Bhargava, Sumanta Ghosh

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of ... more >>>

Kevin Dick, Chris Umans

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are $\Sigma_2^p$-hard to approximate to within factors of $n^{1/3-\epsilon}$ and $n^{1/2-\epsilon}$ (where the previous results achieved $n^{1/4 - \epsilon}$), ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>

Shachar Lovett, Raghu Meka, Jiapeng Zhang

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>

Dan Karliner, Amnon Ta-Shma

Multiplicity codes are a generalization of Reed-Muller codes which include derivatives as well as the values of low degree polynomials, evaluated in every point in $\mathbb{F}_p^m$.

Similarly to Reed-Muller codes, multiplicity codes have a local nature that allows for local correction and local testing.

Recently, the authors and ...
more >>>

Sanjeev Arora, Madhu Sudan

NP = PCP(log n, 1) and related results crucially depend upon

the close connection between the probability with which a

function passes a ``low degree test'' and the distance of

this function to the nearest degree d polynomial. In this

paper we study a test ...
more >>>

Deepanshu Kush, Shubhangi Saraf

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega ... more >>>

Toshiya Itoh

A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer $n>0$, let $S_{n}$ be the family of al permutations on $[1,n]=\{1,2,\ldots, n\}$.

For any integer $k \in [1,n]$ and any real $\varepsilon >0$, we ...
more >>>

Arist Kojevnikov

We continue a study initiated by Krajicek of

a Resolution-like proof system working with clauses of linear

inequalities, R(CP). For all proof systems of this kind

Krajicek proved an exponential lower bound that depends

on the maximal absolute value of coefficients in the given proof and

the maximal clause width.

Marek Karpinski, Richard Schmied

We study the approximation hardness of the Shortest Superstring, the Maximal Compression and

the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem.

We introduce a new reduction method that produces strongly restricted instances of

the Shortest Superstring problem, in which the maximal orbit size is eight

(with no ...
more >>>

Sivakanth Gopi, Venkatesan Guruswami

An $(n,r,h,a,q)$-Local Reconstruction Code is a linear code over $\mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies `$a$' local parity checks to recover from `$a$' erasures in that local group and there are further $h$ global parity ... more >>>

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability $1$, and rejects invalid proofs with probability arbitrarily close to $1$. The running time of such a system is defined to be the length of Merlin's proof plus the running time of Arthur. We ... more >>>

Shachar Lovett, Jiapeng Zhang

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

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

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

Andrea E. F. Clementi, Luca Trevisan

We provide new non-approximability results for the restrictions

of the min-VC problem to bounded-degree, sparse and dense graphs.

We show that for a sufficiently large B, the recent 16/15 lower

bound proved by Bellare et al. extends with negligible

loss to graphs with bounded ...
more >>>

Xin Li

In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are:

(1) An explicit seeded non-malleable extractor with error $\epsilon$ and seed length $d=O(\log n)+O(\log(1/\epsilon)\log \log (1/\epsilon))$, that supports min-entropy $k=\Omega(d)$ and outputs $\Omega(k)$ bits. Combined with ... more >>>

Petr Slavik

We establish significantly improved bounds on the performance of the greedy

algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our

improvements result from a new approach to both problems. In particular,

(a) we improve the known bound on the performance ratio of the greedy ...
more >>>

Louis Golowich

High-dimensional expanders generalize the notion of expander graphs to higher-dimensional simplicial complexes. In contrast to expander graphs, only a handful of high-dimensional expander constructions have been proposed, and no elementary combinatorial construction with near-optimal expansion is known. In this paper, we introduce an improved combinatorial high-dimensional expander construction, by modifying ... more >>>

Xin Lyu

We give PRG for depth-$d$, size-$m$ $\mathrm{AC}^0$ circuits with seed length $O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m))$. Our PRG improves on previous work [TX13, ST19, Kel21] from various aspects. It has optimal dependence on $\frac{1}{\varepsilon}$ and is only one “$\log\log(m)$” away from the lower bound barrier. For the case of $d=2$, the seed length tightly ... more >>>

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

We prove the existence of a $poly(n,m)$-time computable

pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables

and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.

Previously, the best pseudorandom generator for depth-2 circuits had seed

length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus of a recent work by Barak et. al. (BDWY11) in which they were used to answer questions regarding point configurations. In ... more >>>

Alexander Razborov

Recently, Raz established exponential lower bounds on the size

of resolution proofs of the weak pigeonhole principle. We give another

proof of this result which leads to better numerical bounds. Specifically,

we show that every resolution proof of $PHP^m_n$ must have size

$\exp\of{\Omega(n/\log m)^{1/2}}$ which implies an

$\exp\of{\Omega(n^{1/3})}$ bound when ...
more >>>

Alessandro Chiesa, Michael Forbes

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ...
more >>>

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

We present improved algorithms for testing monotonicity of functions.

Namely, given the ability to query an unknown function $f$, where

$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a

monotone $f$, and rejects $f$ with high probability if it is $\e$-far

from being monotone (i.e., every ...
more >>>

Kazuo Iwama, Suguru Tamaki

This paper presents a new upper bound for the

$k$-satisfiability problem. For small $k$'s, especially for $k=3$,

there have been a lot of algorithms which run significantly faster

than the trivial $2^n$ bound. The following list summarizes those

algorithms where a constant $c$ means that the algorithm runs in time

more >>>

Sven Baumer, Rainer Schuler

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT)

is a well known NP-complete problem and the development of faster

(moderately exponential time) algorithms has received much interest

in recent years. We show that the 3-SAT problem can be solved by a

probabilistic algorithm in expected time O(1,3290^n).

more >>>

Tobias Riege, Jörg Rothe

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>

Nikolay Vereshchagin

Assume that $NP\ne RP$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm $D$ for SAT there is a polynomial time samplable distribution such that $D$ errs with probability at least $1/6-\epsilon$ on a random formula chosen with respect to ... more >>>

Eran Rom, Amnon Ta-Shma

In this note we revisit the construction of high noise, almost

optimal rate list decodable code of Guruswami ("Better extractors for better codes?")

Guruswami showed that based on optimal extractors one can build a

$(1-\epsilon,O({1 \over \epsilon}))$ list decodable codes of rate

$\Omega({\epsilon \over {log{1 \over \epsilon}}})$ and alphabet

size ...
more >>>

Oded Goldreich

We show that proving results such as BPP=P essentially

necessitate the construction of suitable pseudorandom generators

(i.e., generators that suffice for such derandomization results).

In particular, the main incarnation of this equivalence

refers to the standard notion of uniform derandomization

and to the corresponding pseudorandom generators

(i.e., the standard uniform ...
more >>>

Frederic Green, Daniel Kreymer, Emanuele Viola

We report on some initial results of a brute-force search for determining the maximum correlation between degree-$d$ polynomials modulo $p$ and the $n$-bit mod $q$ function. For various settings of the parameters $n,d,p,$ and $q$, our results indicate that symmetric polynomials yield the maximum correlation. This contrasts with the previously-analyzed ... more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

We put forth a new computational notion of entropy, which measures the

(in)feasibility of sampling high entropy strings that are consistent

with a given protocol. Specifically, we say that the i'th round of a

protocol (A, B) has _accessible entropy_ at most k, if no

polynomial-time strategy A^* can generate ...
more >>>

Luca Trevisan

We survey results on the hardness of approximating combinatorial

optimization problems.

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

In the undirected Edge-Disjoint Paths problem with Congestion

(EDPwC), we are given an undirected graph with $V$ nodes, a set of

terminal pairs and an integer $c$. The objective is to route as many

terminal pairs as possible, subject to the constraint that at most

$c$ demands can be routed ...
more >>>

Venkatesan Guruswami, Euiwoong Lee

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

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been ... 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 >>>

Aviad Rubinstein

We prove that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for constant $\epsilon$ and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions.

As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete ... more >>>

Daniele Micciancio

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time reverse unfaithful random reductions. These are probabilistic reductions with one-sided error that produce false negatives with small probability, but are guaranteed not to produce false positives regardless of ... more >>>

Janka Chlebíková, Miroslav Chlebik

We study small degree graph problems such as Maximum Independent Set

and Minimum Node Cover and improve approximation lower bounds for

them and for a number of related problems, like Max-B-Set Packing,

Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.

For example, we prove NP-hardness factor of 95/94

more >>>

Lars Engebretsen, Jonas Holmerin, Alexander Russell

An equation over a finite group G is an expression of form

w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted

variable, or a constant from G; such an equation is satisfiable

if there is a setting of the variables to values in G ...
more >>>

Wenbin Chen, Jiangtao Meng

We show that the Closest Vector

Problem with Preprocessing over infty Norm

is NP-hard to approximate to within a factor of $(\log

n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their

reductions are based on norm embeddings. However, ...
more >>>

Amit Chakrabarti, Tony Wirth

Set cover, over a universe of size $n$, may be modelled as a

data-streaming problem, where the $m$ sets that comprise the instance

are to be read one by one. A semi-streaming algorithm is allowed only

$O(n \text{ poly}\{\log n, \log m\})$ space to process this ...
more >>>

Andreas Björklund, Thore Husfeldt

We present a deterministic algorithm producing the number of

$k$-colourings of a graph on $n$ vertices in time

$2^nn^{O(1)}$.

We also show that the chromatic number can be found by a

polynomial space algorithm running in time $O(2.2461^n)$.

Finally, we present a family of ...
more >>>

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

Iftach Haitner, Noam Mazor, Jad Silbak

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.

... more >>>Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can

increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings

require

Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ...
more >>>

Anna Gal, Michal Koucky, Pierre McKenzie

In this paper we propose the study of a new model of restricted

branching programs which we call incremental branching programs.

This is in line with the program proposed by Cook in 1974 as an

approach for separating the class of problems solvable in logarithmic

space from problems solvable ...
more >>>

Stasys Jukna

Many dynamic programming algorithms for discrete optimization problems are "pure" in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even "incremental" in that one of the inputs to the addition operations is a variable. We ... more >>>

Nikolay Vereshchagin, Mikhail V. Vyugin

A string $p$ is called a program to compute $y$ given $x$

if $U(p,x)=y$, where $U$ denotes universal programming language.

Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$

is defined as minimum length of

a program to compute $y$ given $x$.

Let $K(x)$ denote $K(x|\text{empty string})$

(Kolmogorov complexity of $x$) ...
more >>>

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

We study how well can $q$-query decision trees distinguish between the

following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.

variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge

2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of

size ...
more >>>

Gilad Asharov, Alon Rosen, Gil Segev

We prove that indistinguishability obfuscation (iO) and one-way functions do not naturally reduce to any language within $NP \cap coNP$. This is proved within the framework introduced by Asharov and Segev (FOCS '15) that captures the vast majority of techniques that have been used so far in iO-based constructions.

Our ... more >>>

Aayush Jain, Huijia Lin, Amit Sahai

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:

Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $\lambda$ is a security parameter, and the parameters $\ell,k,n$ below ... more >>>

Ashish Rastogi, Richard Cole

This paper considers the tradeoff between divisibility and the hardness of approximating

equilibrium prices. Tight bounds are obtained for smooth Fisher markets that obey a relaxed

weak gross substitutes property (WGS). A smooth market is one in which small changes in

prices cause only proportionately small changes ...
more >>>

Parikshit Gopalan, Amir Yehudayoff

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

Lance Fortnow, Rahul Santhanam

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there

is a polynomial-time computable function $f$ and a set $A$ such that

for each instance ...
more >>>

Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag

In this paper we consider the p-ary transitive reduction (TR<sub>p</sub>) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. ... more >>>

Alan Nash, Russell Impagliazzo, Jeff Remmel

Diagonalization is a powerful technique in recursion theory and in

computational complexity \cite{For00}. The limits of this technique are

not clear. On the one hand, many people argue that conflicting

relativizations mean a complexity question cannot be resolved using only

diagonalization. On the other hand, it is not clear that ...
more >>>

Aniruddha Biswas, Palash Sarkar

The influence of a set of variables on a Boolean function has three separate definitions in the literature, the first due to Ben-Or and Linial (1989), the second due to Fischer et al. (2002) and Blais (2009) and the third due to Tal (2017). The goal of the present work ... more >>>

Omri Weinstein

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is ... more >>>

Himanshu Tyagi, Shaileshh Venkatakrishnan , Pramod Viswanath, Shun Watanabe

A simulation of an interactive protocol entails the use of an interactive communication to produce the output of the protocol to within a fixed statistical distance $\epsilon$. Recent works in the TCS community have propagated that the information complexity of the protocol plays a central role in characterizing the minimum ... more >>>

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

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

Mark Braverman, Jon Schneider

The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $\alpha>0$, thus resolving an ... more >>>

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that ... more >>>

Mikhail V. Vyugin

C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.H.~Zurek

have defined information distance between two strings $x$, $y$

as

$$

d(x,y)=\max\{ K(x|y), K(y|x) \}

$$

where $K(x|y)$ is the conditional Kolmogorov complexity.

It is easy to see that for any string $x$ and any integer $n$

there is a string $y$ ...
more >>>

Jan Krajicek

We study from the proof complexity perspective the (informal) proof search problem:

Is there an optimal way to search for propositional proofs?

We note that for any fixed proof system there exists a time-optimal proof search algorithm. Using classical proof complexity results about reflection principles we prove that a time-optimal ...
more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform ... more >>>

Nico Döttling, Jesper Buus Nielsen, Maceij Obremski

We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding. Prior to our result only codes with computational security were known for this model, and it has ... more >>>

Gregory Valiant, Paul Valiant

We introduce the notion of a database system that is information theoretically "secure in between accesses"--a database system with the properties that 1) users can efficiently access their data, and 2) while a user is not accessing their data, the user's information is information theoretically secure to malicious agents, provided ... more >>>

Nir Ailon, Bernard Chazelle

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>

Mark Braverman, Young Kun Ko

We introduce a generalization of the standard framework for studying the difficulty of two-prover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints) --- in contrast to the usual two-prover game where they are not allowed to communicate after receiving their respective ... 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 >>>

Amos Beimel, Yuval Ishai

A Private Information Retrieval (PIR) protocol enables a user to

retrieve a data item from a database while hiding the identity of the

item being retrieved. In a $t$-private, $k$-server PIR protocol the

database is replicated among $k$ servers, and the user's privacy is

protected from any collusion of up ...
more >>>

Stanislav Zak

Abstract. The old intuitive question "what does the machine think" at

different stages of its computation is examined. Our paper is based on

the formal de nitions and results which are collected in the branching

program theory around the intuitive question "what does the program

know about the contents of ...
more >>>

Vladimir Podolskii, Alexander A. Sherstov

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f\colon(\{0,1\}^n)^{k}\to\{0,1\}$ with $k\gg\log n$ parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every $k\geq\log n$, showing in both cases that $\Theta(1+\lceil\log n\rceil/\log\lceil1+k/\log n\rceil)$ bits are ... more >>>

Andrej Bogdanov, Alon Rosen

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original ... more >>>

Oded Goldreich, Or Meir

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.

Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.

In particular, we provide a uniform complexity formulation of the ...
more >>>

Jack H. Lutz, Elvira Mayordomo

This paper investigates the existence of inseparable disjoint

pairs of NP languages and related strong hypotheses in

computational complexity. Our main theorem says that, if NP does

not have measure 0 in EXP, then there exist disjoint pairs of NP

languages that are P-inseparable, in fact TIME(2^(n^k)-inseparable.

We also relate ...
more >>>

Tomer Grossman, Ilan Komargodski, Moni Naor

Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, ... more >>>

Chiranjit Chakraborty, Rahul Santhanam

We define instance compressibility for parametric problems in PH and PSPACE. We observe that

the problem \Sigma_{i}CircuitSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential uantifier is complete for parametric problems in \Sigma_{i}^{p} with respect to W-reductions, and that analogously ... 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 >>>

Lior Malka

We study the question whether the number of rounds in public-coin perfect zero-knowledge (PZK) proofs can be collapsed to a constant. Despite extensive research into the round complexity of interactive

and zero-knowledge protocols, there is no indication how to address this question. Furthermore, the main tool to tackle this question ...
more >>>

Nicollas Sdroievski, Dieter van Melkebeek

A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the ... more >>>

Ke Yang

In this paper, we address the problem of evaluating the

Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over

the set of natural numbers. The problem is a natural extension

to the integer expression by Stockmeyer and Mayer, and is also studied

by Mckenzie, Vollmer and Wagner in ...
more >>>

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 >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

A set of $n$ players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player ... more >>>

Klim Efremenko, Elad Haramaty, Yael Kalai

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since ... more >>>

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

In this work, we design an interactive coding scheme that converts any two party interactive protocol $\Pi$ into another interactive protocol $\Pi'$, such that even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ would be in an ... more >>>

Gillat Kol

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?

For the non-adaptive channel, where the parties must agree ... more >>>

Mark Braverman

The primary goal of this paper is to define and study the interactive information complexity of functions. Let $f(x,y)$ be a function, and suppose Alice is given $x$ and Bob is given $y$. Informally, the interactive information complexity $IC(f)$ of $f$ is the least amount of information Alice and Bob ... more >>>

Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>

Sarah Bordage, Jade Nardi

In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal C, \mathcal P, D)$ is a vector space associated to evaluations on $\mathcal P$ of functions in the Riemann-Roch space $L_\mathcal C(D)$. The problem of testing proximity to an ... more >>>

Yael Tauman Kalai, Ran Raz

An interactive-PCP (say, for the membership $x \in L$) is a

proof that can be verified by reading only one of its bits, with the

help of a very short interactive-proof.

We show that for membership in some languages $L$, there are

interactive-PCPs that are significantly shorter than the known

more >>>

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

Gus Gutoski

This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling ... more >>>

Oded Goldreich, Silvio Micali.

We introduce the notion of Interleaved Zero-Knowledge (iZK),

a new security measure for cryptographic protocols which strengthens

the classical notion of zero-knowledge, in a way suitable for multiple

concurrent executions in an asynchronous environment like the internet.

We prove that iZK protocols are robust: they are ``parallelizable'',

and ...
more >>>

Balthazar Bauer, Shay Moran, Amir Yehudayoff

We study internal compression of communication protocols

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

We first show that errorless compression to the internal entropy

(and hence to the internal information) is impossible.

We then provide two internal compression schemes with error.

One ...
more >>>

Jan Krajicek

We introduce a notion of a "real game"

(a generalization of the Karchmer - Wigderson game),

and "real communication complexity",

and relate them to the size of monotone real formulas

and circuits. We give an exponential lower bound

for tree-like monotone protocols of small real

communication complexity ...
more >>>

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe

We consider the problem of finding interval representations of graphs that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir proved that the problem is NP-complete if only the former are given [SIAM J. Discr. ... more >>>

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.

more >>>Oded Goldreich

The aim of this article is to introduce the reader to the study

of testing graph properties, while focusing on the main models

and issues involved. No attempt is made to provide a

comprehensive survey of this study, and specific results

are often mentioned merely as illustrations of general ...
more >>>

Madhu Sudan

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For ``global properties'', i.e., properties that really depend somewhat on every piece of the data, one could ask ... more >>>

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

Let $p$ be a fixed prime number, and $N$ be a large integer.

The 'Inverse Conjecture for the Gowers norm' states that if the "$d$-th Gowers norm" of a function $f:\F_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We initiate the study of \emph{inverse} problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $\C$ of Boolean functions ... more >>>

Lijie Chen, Xin Lyu

In this work we prove that there is a function $f \in \textrm{E}^\textrm{NP}$ such that, for every sufficiently large $n$ and $d = \sqrt{n}/\log n$, $f_n$ ($f$ restricted to $n$-bit inputs) cannot be $(1/2 + 2^{-d})$-approximated by $\textrm{F}_2$-polynomials of degree $d$. We also observe that a minor improvement ...
more >>>

Ashwin Nayak

We describe a reduction from the problem of unordered search(with a unique solution) to the problem of inverting a permutation. Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent.

The reduction helps us bypass the Bennett-Bernstein-Brassard-Vazirani hybrid argument (1997} and the Ambainis quantum adversary ... more >>>

Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

The class TFNP, defined by Megiddo and Papadimitriou, consists of

multivalued functions with values that are polynomially verifiable

and guaranteed to exist. Do we have evidence that such functions are

hard, for example, if TFNP is computable in polynomial-time does

this imply the polynomial-time hierarchy collapses?

We give a relativized ... more >>>

Oliver Kullmann

A relativized hierarchy of conjunctive normal forms

is introduced, recognizable and SAT decidable in polynomial

time. The corresponding hardness parameter, the first level

of inclusion in the hierarchy, is studied in detail, admitting

several characterizations, e.g., using pebble games, the space

complexity of (relativized) tree-like ...
more >>>

Or Meir

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The ... more >>>

Alexander Knop

It is well-known that there is equivalence between ordered resolution and ordered binary decision diagrams (OBDD) [LNNW95]; i.e., for any unsatisfiable formula ?, the size of the smallest ordered resolution refutation of ? equal to the size of the smallest OBDD for the canonical search problem corresponding to ?. But ... more >>>

Rahul Santhanam

I discuss recent progress in developing and exploiting connections between

SAT algorithms and circuit lower bounds. The centrepiece of the article is

Williams' proof that $NEXP \not \subseteq ACC^0$, which proceeds via a new

algorithm for $ACC^0$-SAT beating brute-force search. His result exploits

a formal connection from non-trivial SAT algorithms ...
more >>>

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>

I. Cahit, M. Tezer

An irregular assignement of $G$ is labelling $f: E \ra

\{1,2,...,m\}$ of the

edge-set of $G$ such that all of the induced vertex labels computed as

$\sigma_{v\in e}f(e)$ are distinct. The minimal number $m$ for which this

is possible is called the minimal irregularity strength $s_{m}(G)$ of $G$.

The ...
more >>>

Lars Engebretsen, Venkatesan Guruswami

By the breakthrough work of Håstad, several constraint satisfaction

problems are now known to have the following approximation resistance

property: satisfying more clauses than what picking a random

assignment would achieve is NP-hard. This is the case for example for

Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable ...
more >>>

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in $\NP$ imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that ... more >>>

Ronen Shaltiel

Yao's XOR lemma states that for every function $f:\set{0,1}^k \ar \set{0,1}$, if $f$ has hardness $2/3$ for $P/poly$ (meaning that for every circuit $C$ in $P/poly$, $\Pr[C(X)=f(X)] \le 2/3$ on a uniform input $X$), then the task of computing $f(X_1) \oplus \ldots \oplus f(X_t)$ for sufficiently large $t$ has hardness ... more >>>

Valentine Kabanets, Osamu Watanabe

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... more >>>

Elette Boyle, Moni Naor

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with the goal of ... more >>>

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi

We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.

More precisely,

the property that we need is that every face of the polytope lies in an affine space defined ...
more >>>

Vaibhav Krishan, Nutan Limaye

In this work we study the problem of efficiently isolating witnesses for the complexity classes NL and LogCFL, which are two well-studied complexity classes contained in P. We prove that if there is a L/poly randomized procedure with success probability at least 2/3 for isolating an s-t path in a ... more >>>

Thanh Minh Hoang

In this paper we investigate the question whether a perfect matching can be isolated by a weighting scheme

using Chinese Remainder Theorem (short: CRT). We give a systematical analysis to a method based on CRT

suggested by Agrawal in a CCC'03-paper

for testing perfect matchings. We show that ...
more >>>

Eric Allender, Klaus Reinhardt

We show that the perfect matching problem is in the

complexity class SPL (in the nonuniform setting).

This provides a better upper bound on the complexity of the

matching problem, as well as providing motivation for studying

the complexity class SPL.

Using similar ...
more >>>

Vikraman Arvind, Yadu Vasudev

Given two $n$-variable boolean functions $f$ and $g$, we study the problem of computing an $\varepsilon$-approximate isomorphism between them. I.e.\ a permutation $\pi$ of the $n$ variables such that $f(x_1,x_2,\ldots,x_n)$ and $g(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$ differ on at most an $\varepsilon$ fraction of all boolean inputs $\{0,1\}^n$. We give a randomized $2^{O(\sqrt{n}\log(n)^{O(1)})}$ algorithm ... more >>>

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an arbitrary partially ... more >>>

Atri Rudra, Mary Wootters

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

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

Rahul Santhanam, Iddo Tzameret

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally.

We give an explicit sequence of CNF formulas $\{\phi_n\}$ such that VNP$\neq$VP iff there are ... more >>>

Venkatesan Guruswami, Venkatesan Guruswami

Much progress has been made on decoding algorithms for

error-correcting codes in the last decade. In this article, we give an

introduction to some fundamental results on iterative, message-passing

algorithms for low-density parity check codes. For certain

important stochastic channels, this line of work has enabled getting

very close to ...
more >>>