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

**R**

__
TR19-132
| 26th September 2019
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Radio Network Coding Requires Logarithmic Overhead

Revisions: 1

__
TR19-094
| 16th July 2019
__

Venkatesan Guruswami, Sai Sandeep#### Rainbow coloring hardness via low sensitivity polymorphisms

__
TR06-043
| 22nd March 2006
__

Eran Ofek, Uriel Feige#### Random 3CNF formulas elude the Lovasz theta function

__
TR12-033
| 5th April 2012
__

Ankit Gupta, Neeraj Kayal, Youming Qiao#### Random Arithmetic Formulas can be Reconstructed Efficiently

__
TR17-045
| 7th March 2017
__

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere#### Random CNFs are Hard for Cutting Planes

Revisions: 2

__
TR09-137
| 14th December 2009
__

Massimo Lauria#### Random CNFs require spacious Polynomial Calculus refutations

Comments: 1

__
TR17-042
| 6th March 2017
__

Pavel Hrubes, Pavel Pudlak#### Random formulas, monotone circuits, and interpolation

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

__
TR08-080
| 3rd July 2008
__

Ido Ben-Eliezer, Rani Hod, Shachar Lovett#### Random low degree polynomials are hard to approximate

Revisions: 1

__
TR02-006
| 8th November 2001
__

Philippe Moser#### Random nondeterministic real functions and Arthur Merlin games

Revisions: 1

__
TR16-175
| 8th November 2016
__

Pavel Pudlak, Neil Thapen#### Random resolution refutations

Revisions: 2

__
TR19-165
| 18th November 2019
__

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten#### Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

__
TR01-100
| 14th December 2001
__

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Random Sampling and Approximation of MAX-CSP Problems

__
TR06-026
| 27th February 2006
__

Ronen Gradwohl, Salil Vadhan, David Zuckerman#### Random Selection with an Adversarial Majority

__
TR98-049
| 10th July 1998
__

Dimitris Fotakis, Paul Spirakis#### Random Walks, Conditional Hitting Sets and Partial Derandomization

__
TR05-065
| 26th June 2005
__

Alexander Barvinok, Alex Samorodnitsky#### Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

__
TR10-056
| 1st April 2010
__

Kord Eickmeyer, Martin Grohe#### Randomisation and Derandomisation in Descriptive Complexity Theory

Revisions: 1

__
TR97-021
| 16th May 1997
__

Farid Ablayev#### Randomization and nondeterminsm are incomparable for ordered read-once branching programs

__
TR96-058
| 25th November 1996
__

Dima Grigoriev, Marek Karpinski#### Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

__
TR20-024
| 20th February 2020
__

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Randomized and Symmetric Catalytic Computation

__
TR00-007
| 14th December 1999
__

Pavlos S. Efraimidis, Paul Spirakis#### Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

__
TR13-178
| 14th December 2013
__

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

Revisions: 2

__
TR15-169
| 23rd October 2015
__

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson#### Randomized Communication vs. Partition Number

Revisions: 1

__
TR99-020
| 9th June 1999
__

Marek Karpinski#### Randomized Complexity of Linear Arrangements and Polyhedra

__
TR16-089
| 2nd June 2016
__

Vikraman Arvind, Partha Mukhopadhyay, Raja S#### Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

__
TR20-091
| 14th June 2020
__

Janaky Murthy, vineet nair, Chandan Saha#### Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests

__
TR16-087
| 30th May 2016
__

Shalev Ben-David, Robin Kothari#### Randomized query complexity of sabotaged and composed functions

__
TR04-059
| 21st June 2004
__

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler#### Randomized Quicksort and the Entropy of the Random Number Generator

__
TR04-009
| 22nd January 2004
__

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda#### Randomly coloring constant degree graphs

__
TR19-064
| 23rd April 2019
__

Igor Carboni Oliveira#### Randomness and Intractability in Kolmogorov Complexity

__
TR98-018
| 27th March 1998
__

Martin Sauerhoff#### Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Comments: 1

__
TR10-175
| 14th November 2010
__

Emanuele Viola#### Randomness buys depth for approximate counting

Revisions: 1

__
TR19-183
| 21st December 2019
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Randomness Extraction from Somewhat Dependent Sources

Revisions: 1

__
TR16-018
| 3rd February 2016
__

Kuan Cheng, Xin Li#### Randomness Extraction in $AC^0$ and with Small Locality

Revisions: 7

__
TR13-120
| 4th September 2013
__

Zeyu Guo#### Randomness-efficient Curve Samplers

__
TR06-058
| 25th April 2006
__

Alexander Healy#### Randomness-Efficient Sampling within NC^1

Revisions: 1

__
TR12-003
| 13th December 2011
__

Pratik Worah#### Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver

__
TR10-149
| 22nd September 2010
__

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff#### Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Revisions: 1

__
TR95-018
| 27th March 1995
__

Jay Belanger, Jie Wang#### Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions

__
TR20-084
| 31st May 2020
__

Gil Cohen, Tal Yankovitz#### Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes

__
TR17-010
| 18th January 2017
__

Xiaodi Wu, Penghui Yao, Henry Yuen#### Raz-McKenzie simulation with the inner product gadget

Revisions: 1

__
TR18-106
| 30th May 2018
__

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari#### Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

__
TR09-029
| 3rd April 2009
__

Fabian Wagner, Thomas Thierauf#### Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

Revisions: 1

__
TR15-140
| 26th August 2015
__

Adam Case, Jack H. Lutz, Donald Stull#### Reachability Problems for Continuous Chemical Reaction Networks

__
TR11-060
| 15th April 2011
__

Brady Garvin, Derrick Stolee, Raghunath Tewari, Vinodchandran Variyam#### ReachFewL = ReachUL

__
TR10-011
| 22nd January 2010
__

Amir Shpilka, Ilya Volkovich#### Read-Once Polynomial Identity Testing

__
TR95-042
| 14th September 1995
__

Beate Bollig, Ingo Wegener#### Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

__
TR12-134
| 22nd October 2012
__

Alexander Razborov, Emanuele Viola#### Real Advantage

Revisions: 1

__
TR10-158
| 31st October 2010
__

Shiva Kintali#### Realizable Paths and the NL vs L Problem

Revisions: 2

__
TR17-044
| 21st February 2017
__

Olaf Beyersdorff, Luke Hinde, Ján Pich#### Reasons for Hardness in QBF Proof Systems

Revisions: 1

__
TR14-041
| 31st March 2014
__

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

__
TR18-151
| 29th August 2018
__

Ankit Garg, Rafael Oliveira#### Recent progress on scaling algorithms and applications

__
TR20-178
| 30th November 2020
__

Stasys Jukna, Hannes Seiwert, Igor Sergeev#### Reciprocal Inputs in Arithmetic and Tropical Circuits

__
TR03-062
| 10th July 2003
__

Andrei Krokhin, Peter Jonsson#### Recognizing Frozen Variables in Constraint Satisfaction Problems

__
TR05-008
| 11th December 2004
__

Neeraj Kayal#### Recognizing permutation functions in polynomial time.

__
TR09-119
| 17th November 2009
__

Frederic Magniez, Claire Mathieu, Ashwin Nayak#### Recognizing well-parenthesized expressions in the streaming model

__
TR15-150
| 13th September 2015
__

Gaurav Sinha#### Reconstruction of $\Sigma\Pi\Sigma(2)$ Circuits over Reals

Revisions: 3

__
TR19-104
| 6th August 2019
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Reconstruction of Depth-$4$ Multilinear Circuits

__
TR11-153
| 13th November 2011
__

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam#### Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

__
TR17-021
| 11th February 2017
__

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas#### Reconstruction of full rank Algebraic Branching Programs

__
TR18-191
| 10th November 2018
__

Neeraj Kayal, Chandan Saha#### Reconstruction of non-degenerate homogeneous depth three circuits

__
TR14-147
| 6th November 2014
__

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

Revisions: 1

__
TR01-004
| 13th October 2000
__

Tobias Gärtner, Günter Hotz#### Recursive analytic functions of a complex variable

__
TR98-007
| 12th January 1998
__

Luca Trevisan#### Recycling Queries in PCPs and in Linearity Tests

__
TR05-090
| 17th August 2005
__

Paul Goldberg, Christos H. Papadimitriou#### Reducibility Among Equilibrium Problems

__
TR09-041
| 9th April 2009
__

Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng#### Reducibility Among Fractional Stability Problems

__
TR11-113
| 11th August 2011
__

Emanuele Viola#### Reducing 3XOR to listing triangles, an exposition

__
TR99-018
| 8th June 1999
__

Manindra Agrawal, Somenath Biswas#### Reducing Randomness via Chinese Remaindering

__
TR16-080
| 18th May 2016
__

Oded Goldreich#### Reducing testing affine spaces to testing linearity

Revisions: 4

__
TR20-093
| 23rd June 2020
__

Ronen Eldan, Dana Moshkovitz#### Reduction From Non-Unique Games To Boolean Unique Games

__
TR04-077
| 17th July 2004
__

Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford#### Reductions Between Classification Tasks

__
TR03-027
| 21st April 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta#### Reductions between Disjoint NP-Pairs

__
TR10-172
| 11th November 2010
__

Prasad Raghavendra, David Steurer, Madhur Tulsiani#### Reductions Between Expansion Problems

__
TR07-071
| 1st August 2007
__

Jacobo Toran#### Reductions to Graph Isomorphism

__
TR12-054
| 2nd May 2012
__

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff#### Reductions to the set of random strings:the resource-bounded case

Revisions: 1

__
TR05-068
| 7th July 2005
__

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang#### Redundancy in Complete Sets

__
TR10-052
| 8th March 2010
__

Melanie Winkler, Berthold Vöcking, Sascha Geulen#### Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm

__
TR11-173
| 22nd December 2011
__

Christoph Behle, Andreas Krebs#### Regular Languages in MAJ[<] with three variables

__
TR08-103
| 22nd November 2008
__

Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

__
TR20-159
| 9th October 2020
__

Leroy Chew, Marijn Heule#### Relating existing powerful proof systems for QBF

__
TR16-164
| 25th October 2016
__

Andreas Krebs, Meena Mahajan, Anil Shukla#### Relating two width measures for resolution proofs

__
TR10-040
| 10th March 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Relationless completeness and separations

__
TR19-075
| 25th May 2019
__

Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams#### Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

__
TR15-028
| 27th February 2015
__

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland#### Relative Discrepancy does not separate Information and Communication Complexity

__
TR18-103
| 30th April 2018
__

Zhao Song, David Woodruff, Peilin Zhong#### Relative Error Tensor Low Rank Approximation

__
TR01-068
| 19th September 2001
__

Philippe Moser#### Relative to P, APP and promise-BPP are the same

Revisions: 1

__
TR03-084
| 27th November 2003
__

Joshua Buresh-Oppenheim, Tsuyoshi Morioka#### Relativized NP Search Problems and Propositional Proof Systems

__
TR10-042
| 12th March 2010
__

Thomas Watson#### Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

Revisions: 3

__
TR17-143
| 26th September 2017
__

Tom Gur, Govind Ramnarayan, Ron Rothblum#### Relaxed Locally Correctable Codes

Revisions: 1

__
TR20-142
| 15th September 2020
__

Vahid Reza Asadi, Igor Shinkar#### Relaxed Locally Correctable Codes with Improved Parameters

__
TR20-113
| 27th July 2020
__

Alessandro Chiesa, Tom Gur, Igor Shinkar#### Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

__
TR15-199
| 7th December 2015
__

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan#### Relaxed partition bound is quadratically tight for product distributions

__
TR15-014
| 18th January 2015
__

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Reliable Communication over Highly Connected Noisy Networks

__
TR18-041
| 26th February 2018
__

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov#### Reordering Rule Makes OBDD Proof Systems Stronger

__
TR04-082
| 9th September 2004
__

Olaf Beyersdorff#### Representable Disjoint NP-Pairs

Revisions: 1

__
TR15-157
| 1st September 2015
__

Thomas O'Neil#### Representation-Independent Fixed Parameter Tractability for Vertex Cover and Weighted Monotone Satisfiability

__
TR17-106
| 16th June 2017
__

Mateus de Oliveira Oliveira, Pavel Pudlak#### Representations of Monotone Boolean Functions by Linear Programs

__
TR06-158
| 8th December 2006
__

Gyula Gyôr#### Representing Boolean OR function by quadratic polynomials modulo 6

__
TR18-048
| 11th March 2018
__

Ofer Grossman, Yang P. Liu#### Reproducibility and Pseudo-Determinism in Log-Space

__
TR99-042
| 24th October 1999
__

Ran Canetti, Oded Goldreich, Silvio Micali.#### Resettable Zero-Knowledge.

Revisions: 1

__
TR04-112
| 26th November 2004
__

Neil Thapen, Nicola Galesi#### Resolution and pebbling games

__
TR18-165
| 20th September 2018
__

Stefan Dantchev, Nicola Galesi, Barnaby Martin#### Resolution and the binary encoding of combinatorial principles

__
TR14-093
| 22nd July 2014
__

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

__
TR19-084
| 26th May 2019
__

Michal Garlik#### Resolution Lower Bounds for Refutation Statements

__
TR01-075
| 2nd November 2001
__

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

__
TR01-021
| 7th March 2001
__

Ran Raz#### Resolution Lower Bounds for the Weak Pigeonhole Principle

Revisions: 1

__
TR07-078
| 11th August 2007
__

Ran Raz, Iddo Tzameret#### Resolution over Linear Equations and Multilinear Proofs

__
TR18-117
| 23rd June 2018
__

Fedor Part, Iddo Tzameret#### Resolution with Counting: Lower Bounds over Different Moduli

Revisions: 2

__
TR01-085
| 1st October 2001
__

Gerhard J. Woeginger#### Resource augmentation for online bounded space bin packing

__
TR04-066
| 6th July 2004
__

Tomoyuki Yamakami, Toshio Suzuki#### Resource Bounded Immunity and Simplicity

__
TR02-038
| 5th June 2002
__

Rahul Santhanam#### Resource Tradeoffs and Derandomization

Revisions: 1

__
TR17-119
| 25th July 2017
__

Badih Ghazi, T.S. Jayram#### Resource-Efficient Common Randomness and Secret-Key Schemes

__
TR12-082
| 28th June 2012
__

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker#### Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

__
TR00-048
| 3rd July 2000
__

Beate Bollig#### Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

__
TR09-094
| 7th October 2009
__

Bireswar Das, Jacobo Toran, Fabian Wagner#### Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

__
TR11-160
| 1st December 2011
__

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff#### Restriction Access

__
TR19-097
| 4th July 2019
__

Jacobo Toran, Florian Wörz#### Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

Revisions: 1
,
Comments: 1

__
TR05-032
| 16th March 2005
__

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen#### Reviewing Bounds on the Circuit Size of the Hardest Functions

__
TR19-092
| 9th July 2019
__

Venkatesan Guruswami, Jakub Opršal, Sai Sandeep#### Revisiting Alphabet Reduction in Dinur's PCP

__
TR13-113
| 19th August 2013
__

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

__
TR02-043
| 11th July 2002
__

Dalit Naor, Moni Naor, Jeff Lotspiech#### Revocation and Tracing Schemes for Stateless Receivers

__
TR20-075
| 6th May 2020
__

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal#### Rigid Matrices From Rectangular PCPs

Revisions: 2

__
TR14-066
| 17th April 2014
__

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

__
TR06-118
| 2nd September 2006
__

Irit Dinur, Madhu Sudan, Avi Wigderson#### Robust Local Testability of Tensor Products of LDPC Codes

__
TR04-046
| 4th June 2004
__

Eli Ben-Sasson, Madhu Sudan#### Robust Locally Testable Codes and Products of Codes

__
TR11-062
| 18th April 2011
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor#### Robust Lower Bounds for Communication and Stream Computation

__
TR16-204
| 20th December 2016
__

Prahladh Harsha, Srikanth Srinivasan#### Robust Multiplication-based Tests for Reed-Muller Codes

__
TR04-021
| 23rd March 2004
__

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan#### Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

__
TR13-143
| 19th October 2013
__

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

Revisions: 1

__
TR11-163
| 2nd December 2011
__

Libor Barto, Marcin Kozik#### Robust Satisfiability of Constraint Satisfaction Problems

__
TR16-161
| 26th October 2016
__

Shachar Lovett, Jiapeng Zhang#### Robust sensitivity

Revisions: 1

__
TR15-043
| 2nd April 2015
__

Alan Guo, Elad Haramaty, Madhu Sudan#### Robust testing of lifted codes with applications to low-degree testing

__
TR21-005
| 13th January 2021
__

Anindya De, Elchanan Mossel, Joe Neeman#### Robust testing of low-dimensional functions

__
TR20-149
| 29th September 2020
__

Oded Goldreich, Avi Wigderson#### Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2

__
TR17-055
| 26th March 2017
__

Maya Leshkowitz#### Round Complexity Versus Randomness Complexity in Interactive Proofs

__
TR06-093
| 27th July 2006
__

Takeshi Koshiba, Yoshiharu Seri#### Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme

__
TR11-065
| 25th April 2011
__

Boaz Barak, Prasad Raghavendra, David Steurer#### Rounding Semidefinite Programming Hierarchies via Global Correlation

__
TR13-184
| 23rd December 2013
__

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

__
TR03-040
| 3rd June 2003
__

Philippe Moser#### RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

__
TR06-084
| 19th June 2006
__

Frank Neumann, Carsten Witt#### Runtime Analysis of a Simple Ant Colony Optimization Algorithm

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, ... more >>>

Venkatesan Guruswami, Sai Sandeep

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>

Eran Ofek, Uriel Feige

Let $\phi$ be a 3CNF formula with n variables and m clauses. A

simple nonconstructive argument shows that when m is

sufficiently large compared to n, most 3CNF formulas are not

satisfiable. It is an open question whether there is an efficient

refutation algorithm that for most such formulas proves ...
more >>>

Ankit Gupta, Neeraj Kayal, Youming Qiao

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial $f$ computed by an unknown/hidden arithmetic formula $\phi$ reconstructs, on the average, an equivalent or smaller formula $\hat{\phi}$ in time polynomial in the size of its output $\hat{\phi}$.

Specifically, we consider arithmetic formulas wherein the ... more >>>

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

The random k-SAT model is the most important and well-studied distribution over

k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for

satisfiablity algorithms, and lastly average-case hardness over this distribution has also

been linked to hardness of approximation via Feige’s hypothesis. In this ...
more >>>

Massimo Lauria

We study the space required by Polynomial Calculus refutations of random $k$-CNFs. We are interested in how many monomials one needs to keep in memory to carry on a refutation. More precisely we show that for $k \geq 4$ a refutation of a random $k$-CNF of $\Delta n$ clauses and ... more >>>

Pavel Hrubes, Pavel Pudlak

We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call "unsatisfiability certificate". This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicable to CNF formulas that do not seem suitable for interpolation. Specifically, we ... more >>>

Phokion G. Kolaitis, Swastik Kopparty

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

Ido Ben-Eliezer, Rani Hod, Shachar Lovett

We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$.

We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to ...
more >>>

Philippe Moser

We construct a nondeterministic analogue to \textbf{APP}, denoted

\textbf{NAPP}; which is the set of all real valued functions

$f: \{ 0,1 \}^{*} \rightarrow [0,1]$, that are approximable within 1/$k$,

by a probabilistic nondeterministic transducer, in time poly($n,1^{k}$).

We show that the subset of all Boolean ...
more >>>

Pavel Pudlak, Neil Thapen

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the ... more >>>

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how ... more >>>

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Ronen Gradwohl, Salil Vadhan, David Zuckerman

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

Dimitris Fotakis, Paul Spirakis

In this work we use random walks on expanders in order to

relax the properties of hitting sets required for partially

derandomizing one-side error algorithms. Building on a well-known

probability amplification technique [AKS87,CW89,IZ89], we use

random walks on expander graphs of subexponential (in the

random bit complexity) size so as ...
more >>>

Alexander Barvinok, Alex Samorodnitsky

For a family X of k-subsets of the set 1...n, let |X| be the cardinality of X and let Gamma(X, mu) be the expected maximum weight of a subset from X when the weights of 1...n are chosen independently at random from a symmetric probability distribution mu on R. We ... more >>>

Kord Eickmeyer, Martin Grohe

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the

complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined ...
more >>>

Farid Ablayev

In the manuscript F. Ablayev and M. Karpinski, On the power of

randomized branching programs (generalization of ICALP'96 paper

results for the case of pure boolean function, available at

http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions

$f_n$ in $n$ variables such that:

1) $f_{n}$ can be computed ... more >>>

Dima Grigoriev, Marek Karpinski

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the

general model of \emph{randomized computation trees} solving

the \emph{Knapsack Problem}, and more generally \emph{Restricted

Integer Programming}. This is the \emph{first nontrivial} lower

bound proven for this model of computation. The method of the ...
more >>>

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

Pavlos S. Efraimidis, Paul Spirakis

The problem of Scheduling $n$ Independent Jobs

on $m$ Unrelated Parallel Machines, when $m$

is fixed, is considered. The standard problem

of minimizing the makespan of the schedule

(SUM) and the bicriteria problem of scheduling

with bounded makespan and cost (SUMC), are

addressed, and randomized fully linear time

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

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

more >>>Marek Karpinski

We survey some of the recent results on the complexity of recognizing

n-dimensional linear arrangements and convex polyhedra by randomized

algebraic decision trees. We give also a number of concrete applications

of these results. In particular, we derive first nontrivial, in fact

quadratic, ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay, Raja S

In this paper we show that polynomial identity testing for

noncommutative circuits of size $s$, computing a polynomial in

$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm

with running time polynomial in $s$ and $n$. This answers a question

that has been open for over ten years.

The ... more >>>

Janaky Murthy, vineet nair, Chandan Saha

Equivalence testing for a polynomial family $\{g_m\}_{m \in \mathbb{N}}$ over a field F is the following problem: Given black-box access to an $n$-variate polynomial $f(\mathbb{x})$, where $n$ is the number of variables in $g_m$ for some $m \in \mathbb{N}$, check if there exists an $A \in \text{GL}(n,\text{F})$ such that $f(\mathbb{x}) ... more >>>

Shalev Ben-David, Robin Kothari

We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f ... more >>>

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler

The worst-case complexity of an implementation of Quicksort depends

on the random number generator that is used to select the pivot

elements. In this paper we estimate the expected number of

comparisons of Quicksort as a function in the entropy of the random

source. We give upper and lower bounds ...
more >>>

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree Δ. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> ≥ <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>>

Igor Carboni Oliveira

We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion of Kolmogorov complexity from 1984. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability.

This complexity measure gives rise to a ... more >>>

Martin Sauerhoff

We extend the tools for proving lower bounds for randomized branching

programs by presenting a new technique for the read-once case which is

applicable to a large class of functions. This technique fills the gap

between simple methods only applicable for OBDDs and the well-known

"rectangle technique" of Borodin, Razborov ...
more >>>

Emanuele Viola

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, ... more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness.

Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions.

Going from the more restricted model ...
more >>>

Kuan Cheng, Xin Li

We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that ... more >>>

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

Alexander Healy

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results:

... more >>>Pratik Worah

Lov\'{a}sz and Schrijver introduced several lift and project methods for $0$-$1$ integer programs, now collectively known as Lov\'{a}sz-Schrijver ($LS$) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the $LS$ and $LS_+$ hierarchies. In this paper we investigate rank bounds in the ... more >>>

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

A $(q,k,t)$-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most $q$ non-zeros, each column has at least $k$ non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>>

Jay Belanger, Jie Wang

We show that polynomially rankable distributions

do not provide harder instances than uniform distributions

for NP problems. In particular, we show that if Levin's

randomized tiling problem is solvable in polynomial time on

average, then every NP problem under any p-rankable

...
more >>>

Gil Cohen, Tal Yankovitz

In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good $n$-bit locally decodable codes (LDC) with $2^{\widetilde{O}(\sqrt{\log{n}})}$ queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance $\delta$ of a code to a constant at ... more >>>

Xiaodi Wu, Penghui Yao, Henry Yuen

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices

$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous

logarithmic space.

Fabian Wagner, Thomas Thierauf

We show that the reachability problem for directed graphs

that are either K_{3,3}-free or K_5-free

is in unambiguous log-space, UL \cap coUL.

This significantly extends the result of Bourke, Tewari, and Vinodchandran

that the reachability problem for directed planar graphs

is in UL \cap coUL.

Our algorithm decomposes ... more >>>

Adam Case, Jack H. Lutz, Donald Stull

Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed system. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced a new model of chemical kinetics, rate-independent continuous CRNs ... more >>>

Brady Garvin, Derrick Stolee, Raghunath Tewari, Vinodchandran Variyam

We show that two complexity classes introduced about two decades ago are equal. ReachUL is the class of problems decided by nondeterministic log-space machines which on every input have at most one computation path from the start configuration to any other configuration. ReachFewL, a natural generalization of ReachUL, is the ... more >>>

Amir Shpilka, Ilya Volkovich

An \emph{arithmetic read-once formula} (ROF for short) is a

formula (a circuit whose underlying graph is a tree) in which the

operations are $\{+,\times\}$ and such that every input variable

labels at most one leaf. A \emph{preprocessed ROF} (PROF for

short) is a ROF in which we are allowed to ...
more >>>

Beate Bollig, Ingo Wegener

Computational complexity is concerned with the complexity of solving

problems and computing functions and not with the complexity of verifying

circuit designs.

The importance of formal circuit verification is evident.

Therefore, a framework of a complexity theory for formal circuit

verification with binary decision diagrams ...
more >>>

Alexander Razborov, Emanuele Viola

We highlight the challenge of proving correlation bounds

between boolean functions and integer-valued polynomials,

where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac 12

\log_2 \log_2 n$ have zero correlation with parity. Such a

result is false for modular and threshold polynomials.

Its proof ...
more >>>

Shiva Kintali

A celebrated theorem of Savitch states that NSPACE(S) is contained DSPACE(S^2). In particular, Savitch gave a deterministic algorithm to solve ST-CONNECTIVITY (an NL-complete problem) using O(log^2{n}) space, implying NL is in DSPACE(log^2{n}). While Savitch’s theorem itself has not been improved in the last four decades, studying the space complexity of ... more >>>

Olaf Beyersdorff, Luke Hinde, Ján Pich

We aim to understand inherent reasons for lower bounds for QBF proof systems and revisit and compare two previous approaches in this direction.

The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bounds via strategy extraction (Beyersdorff & Pich, LICS'16). Here we ... more >>>

Shachar Lovett

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

Ankit Garg, Rafael Oliveira

Scaling problems have a rich and diverse history, and thereby have found numerous

applications in several fields of science and engineering. For instance, the matrix scaling problem

has had applications ranging from theoretical computer science to telephone forecasting,

economics, statistics, optimization, among many other fields. Recently, a generalization of matrix

more >>>

Stasys Jukna, Hannes Seiwert, Igor Sergeev

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that ... more >>>

Andrei Krokhin, Peter Jonsson

In constraint satisfaction problems over finite domains, some variables

can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the

instances. We show that the complexity of ...
more >>>

Neeraj Kayal

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.

The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on

the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map

$f : \mathbb{F}_q ...
more >>>

Frederic Magniez, Claire Mathieu, Ashwin Nayak

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis.

We present a one-pass randomized streaming ... more >>>

Gaurav Sinha

Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We present a deterministic algorithm for reconstructing multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. For any fixed $k$, given black-box access to a polynomial $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ computable by a multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit of size $s$, the algorithm runs in time ... more >>>

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

An algebraic branching program (ABP) A can be modelled as a product expression $X_1\cdot X_2\cdot \dots \cdot X_d$, where $X_1$ and $X_d$ are $1 \times w$ and $w \times 1$ matrices respectively, and every other $X_k$ is a $w \times w$ matrix; the entries of these matrices are linear forms ... more >>>

Neeraj Kayal, Chandan Saha

A homogeneous depth three circuit $C$ computes a polynomial

$$f = T_1 + T_2 + ... + T_s ,$$ where each $T_i$ is a product of $d$ linear forms in $n$ variables over some underlying field $\mathbb{F}$. Given black-box access to $f$, can we efficiently reconstruct (i.e. proper learn) a ...
more >>>

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

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

Tobias Gärtner, Günter Hotz

We extend the concept of recursive definition on analytic functions. For special cases of linear primitive recursive definitions we show the existence of natural continuations of the over $\N$ primitive recursive functions to analytic functions. Especially, we show that solutions exist if the coefficients of the linear recursive equation are ... more >>>

Luca Trevisan

We study query-efficient Probabilistically Checkable

Proofs (PCPs) and linearity tests. We focus on the number

of amortized query bits. A testing algorithm uses $q$ amortized

query bits if, for some constant $k$, it reads $qk$ bits and has

error probability at most $2^{-k}$. The best known ...
more >>>

Paul Goldberg, Christos H. Papadimitriou

We address the fundamental question of whether the Nash equilibria of

a game can be computed in polynomial time. We describe certain

efficient reductions between this problem for

normal form games with a fixed number of players

and graphical games with fixed degree. Our main result is that ...
more >>>

Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

"As has often been the case with NP-completeness proofs, PPAD-completeness proofs will be eventually refined to cover simpler and more realistic looking classes of games. And then researchers will strive to identify even simpler classes." --Papadimitriou (chapter 2 of Algorithmic Game Theory book)

In a landmark paper, Papadimitriou introduced a ... more >>>

Emanuele Viola

The 3SUM problem asks if there are three integers $a,b,c$ summing to $0$ in a given set of $n$ integers of magnitude poly($n$). Patrascu (STOC '10) reduces solving 3SUM in time $n^{2-\Omega(1)}$ to listing $m$ triangles in a graph with $m$ edges in time $m^{4/3-\Omega(1)}$.

In this note we present ...
more >>>

Manindra Agrawal, Somenath Biswas

We give new randomized algorithms for testing multivariate polynomial

identities over finite fields and rationals. The algorithms use

\lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil

in case of rationals where C is the largest coefficient)

random bits to test if a

polynomial P(x_1, ..., x_n) is zero where d_i is ...
more >>>

Oded Goldreich

We consider the task of testing whether a Boolean function $f:\{0,1\}^\ell\to\{0,1\}$

is the indicator function of an $(\ell-k)$-dimensional affine space.

An optimal tester for this property was presented by Parnas, Ron, and Samorodnitsky ({\em SIDMA}, 2002), by mimicking the celebrated linearity tester (of Blum, Luby and Rubinfeld, {\em JCSS}, 1993) ...
more >>>

Ronen Eldan, Dana Moshkovitz

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.

In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., ...
more >>>

Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford

There are two approaches to solving a new supervised learning task: either

analyze the task independently or reduce it to a task that has already

been thoroughly analyzed. This paper investigates the latter approach for

classification problems. In addition to obvious theoretical motivations,

there is fairly strong empirical evidence that ...
more >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta

We prove that all of the following assertions are equivalent:

There is a many-one complete disjoint NP-pair;

there is a strongly many-one complete disjoint NP-pair;

there is a Turing complete disjoint NP-pair such that all reductions

are smart reductions;

there is a complete disjoint NP-pair for one-to-one, invertible ...
more >>>

Prasad Raghavendra, David Steurer, Madhur Tulsiani

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique ... more >>>

Jacobo Toran

We show that several reducibility notions coincide when applied to the

Graph Isomorphism (GI) problem. In particular we show that if a set is

many-one logspace reducible to GI, then it is in fact many-one AC^0

reducible to GI. For the case of Turing reducibilities we show that ...
more >>>

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

Melanie Winkler, Berthold Vöcking, Sascha Geulen

Suppose a decision maker has to purchase a commodity over time with

varying prices and demands. In particular, the price per unit might

depend on the amount purchased and this price function might vary from

step to step. The decision maker has a buffer of bounded size for

storing units ...
more >>>

Christoph Behle, Andreas Krebs

We consider first order logic over words and show FO+MOD[<] is contained in MAJ[<] with three variables.

It is known that for the classes FO[<], FO+MOD[<], FO+GROUP[<] three variables suffice. In the case of MOD[<] even two variables are sufficient.

As a consequence we know that if TC^ 0 neq ... more >>>

Luca Trevisan, Madhur Tulsiani, Salil Vadhan

We show that every high-entropy distribution is indistinguishable from an

efficiently samplable distribution of the same entropy. Specifically, we prove

that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,

then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most

$S\cdot ...
more >>>

Leroy Chew, Marijn Heule

We advance the theory of QBF proof systems by showing the first simulation of the universal checking format QRAT by a theory-friendly system. We show that the sequent system G fully p-simulates QRAT, including the Extended Universal Reduction (EUR) rule which was recently used to show QRAT does not ... more >>>

Andreas Krebs, Meena Mahajan, Anil Shukla

In this short note, we revisit two hardness measures for resolution proofs: width and asymmetric width. It is known that for every unsatisfiable CNF F,

width(F \derives \Box) \le awidth(F \derives \Box) + max{ awidth(F \derives \Box), width(F)}.

We give a simple direct proof of the upper bound, ... more >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds.

We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent ...
more >>>

Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

Zhao Song, David Woodruff, Peilin Zhong

We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-$q$ tensor $A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$ tensor $B$ for which $\|A-B\|_F^2 \leq (1+\epsilon) {\rm OPT}$, where ${\rm OPT} = \inf_{\textrm{rank-}k~A'} \|A-A'\|_F^2$. Despite much success on obtaining relative error low ... more >>>

Philippe Moser

We show that for determinictic polynomial time computation, oracle access to

$\mathbf{APP}$, the class of real functions

approximable by probabilistic Turing machines, is the same as having oracle access to

promise-$\mathbf{BPP}$. First

we construct a mapping that maps every function in $\mathbf{APP}$ to a promise problem

more >>>

Joshua Buresh-Oppenheim, Tsuyoshi Morioka

We consider Total Functional $\NP$ ($\TFNP$) search problems. Such problems are based on combinatorial principles that guarantee, through locally checkable conditions, that a solution to the problem exists in an exponentially-large domain, and have the property that any solution has a polynomial-size witness that can be verified in polynomial time. ... more >>>

Thomas Watson

We prove that relative to an oracle, there is no worst-case to errorless-average-case reduction for $\NP$. This result is the first progress on an open problem posed by Impagliazzo in 1995, namely to construct an oracle relative to which $\NP$ is worst-case hard but errorless-average-case easy. We also handle classes ... more >>>

Tom Gur, Govind Ramnarayan, Ron Rothblum

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of ... more >>>

Vahid Reza Asadi, Igor Shinkar

Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off ... more >>>

Alessandro Chiesa, Tom Gur, Igor Shinkar

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... more >>>

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

We consider the task of multiparty computation performed over networks in

the presence of random noise. Given an $n$-party protocol that takes $R$

rounds assuming noiseless communication, the goal is to find a coding

scheme that takes $R'$ rounds and computes the same function with high

probability even when the ...
more >>>

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Atserias, Kolaitis, and Vardi [AKV04] showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD($\land$, weakening), simulates CP* (Cutting Planes with unary coefficients). We show that OBDD($\land$, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring ... more >>>

Olaf Beyersdorff

We investigate the class of disjoint NP-pairs under different reductions.

The structure of this class is intimately linked to the simulation order

of propositional proof systems, and we make use of the relationship between

propositional proof systems and theories of bounded arithmetic as the main

tool of our analysis.

more >>>

Thomas O'Neil

A symmetric representation for a set of objects requires the same amount of space for the set as for its complement. Complexity classifications that are based on the length of the input can depend on whether the representation is symmetric. In this article we describe a symmetric representation scheme for ... more >>>

Mateus de Oliveira Oliveira, Pavel Pudlak

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of

computation for partial Boolean functions. Using this model, we prove the following results:

1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.

2. MLP circuits are exponentially stronger than monotone span programs.

3. ...
more >>>

Gyula Gyôr

We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to ... more >>>

Ofer Grossman, Yang P. Liu

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits ... more >>>

Ran Canetti, Oded Goldreich, Silvio Micali.

We introduce the notion of Resettable Zero-Knowledge (rZK),

a new security measure for cryptographic protocols

which strengthens the classical notion of zero-knowledge.

In essence, an rZK protocol is one that remains zero knowledge

even if an adeversary can interact with the prover many times, each

time ...
more >>>

Neil Thapen, Nicola Galesi

We define a collection of Prover-Delayer games that characterize certain subsystems of resolution. This allows us to give some natural criteria which guarantee lower bounds on the resolution width of a formula, and to extend these results to formulas of unbounded initial width.

We also use games to give upper ... more >>>

Stefan Dantchev, Nicola Galesi, Barnaby Martin

We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>

Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

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

Michal Garlik

For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolution refutations of a propositional statement that the formula has a resolution refutation. We describe three applications. (1) An open question in [Atserias-Müller,2019] asks whether a certain natural propositional encoding of the above statement is ... more >>>

Alexander Razborov

We show that every resolution proof of the {\em functional} version

$FPHP^m_n$ of the pigeonhole principle (in which one pigeon may not split

between several holes) must have size $\exp\of{\Omega\of{\frac n{(\log

m)^2}}}$. This implies an $\exp\of{\Omega(n^{1/3})}$ bound when the number

of pigeons $m$ is arbitrary.

Ran Raz

We prove that any Resolution proof for the weak

pigeon hole principle, with $n$ holes and any number of

pigeons, is of length $\Omega(2^{n^{\epsilon}})$,

(for some global constant $\epsilon > 0$).

Ran Raz, Iddo Tzameret

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. ... more >>>

Fedor Part, Iddo Tzameret

Resolution over linear equations (introduced in [RT08]) emerged recently as an important object of study. This refutation system, denoted Res(lin$_R$), operates with disjunction of linear equations over a ring $R$. On the one hand, the system captures a natural ``minimal'' extension of resolution in which efficient counting can be achieved; ... more >>>

Gerhard J. Woeginger

We study online bounded space bin packing in the resource

augmentation model of competitive analysis.

In this model, the online bounded space packing algorithm has

to pack a list L of items in (0,1] into a small number of

bins of size b>=1.

Its performance is measured by comparing the ...
more >>>

Tomoyuki Yamakami, Toshio Suzuki

Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we ... more >>>

Rahul Santhanam

We consider uniform assumptions for derandomization. We provide

intuitive evidence that BPP can be simulated non-trivially in

deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE

implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP

= P. These results extend and complement earlier work of ...
more >>>

Badih Ghazi, T.S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker

We prove that a random linear code over $\mathbb{F}_q$, with probability arbitrarily close to $1$, is list decodable at radius $1-1/q-\epsilon$ with list size $L=O(1/\epsilon^2)$ and rate $R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon)))$. Up to the polylogarithmic factor in $1/\epsilon$ and constant factors depending on $q$, this matches the lower bound $L=\Omega_q(1/\epsilon^2)$ for the list ... more >>>

Beate Bollig

Branching programs are a well established computation model for

Boolean functions, especially read-once branching programs have

been studied intensively.

In this paper the expressive power of nondeterministic read-once

branching programs, i.e., the class of functions

representable in polynomial size, is investigated.

For that reason two restricted models of nondeterministic read-once

more >>>

Bireswar Das, Jacobo Toran, Fabian Wagner

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width

are known to be solvable in polynomial time \cite{Bo90},\cite{YBFT}.

We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>>

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>>

Jacobo Toran, Florian Wörz

We show a new connection between the space measure in tree-like resolution and the reversible pebble game in graphs. Using this connection we provide several formula classes for which there is a logarithmic factor separation between the space complexity measure in tree-like and general resolution. We show that these separations ... more >>>

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen

In this paper we review the known bounds for $L(n)$, the circuit size

complexity of the hardest Boolean function on $n$ input bits. The

best known bounds appear to be $$\frac{2^n}{n}(1+\frac{\log

n}{n}-O(\frac{1}{n})) \leq L(n) \leq\frac{2^n}{n}(1+3\frac{\log

n}{n}+O(\frac{1}{n}))$$ However, the bounds do not seem to be

explicitly stated in the literature. We ...
more >>>

Venkatesan Guruswami, Jakub Opršal, Sai Sandeep

Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the ... 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 >>>

Dalit Naor, Moni Naor, Jeff Lotspiech

We deal with the problem of a center sending a secret message to

a group of users such that some subset of the users is considered

revoked and should not be able to obtain the content of the

message. We concentrate on the stateless receiver case, where

the users do ...
more >>>

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*.

We ... more >>>

Suguru Tamaki, Yuichi Yoshida

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

Irit Dinur, Madhu Sudan, Avi Wigderson

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

Eli Ben-Sasson, Madhu Sudan

We continue the investigation of locally testable codes, i.e.,

error-correcting codes for whom membership of a given word in the

code can be tested probabilistically by examining it in very few

locations. We give two general results on local testability:

First, motivated by the recently proposed notion of robust

probabilistically ...
more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models. We aim to understand whether ... more >>>

Prahladh Harsha, Srikanth Srinivasan

We consider the following multiplication-based tests to check if a given function $f: \mathbb{F}_q^n\to \mathbb{F}_q$ is the evaluation of a degree-$d$ polynomial over $\mathbb{F}_q$ for $q$ prime.

* $\mathrm{Test}_{e,k}$: Pick $P_1,\ldots,P_k$ independent random degree-$e$ polynomials and accept iff the function $fP_1\cdots P_k$ is the evaluation of a degree-$(d+ek)$ polynomial.

... more >>>Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

We continue the study of the trade-off between the length of PCPs

and their query complexity, establishing the following main results

(which refer to proofs of satisfiability of circuits of size $n$):

We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$

that can be verified by making $o(\log\log n)$ Boolean queries.

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

Libor Barto, Marcin Kozik

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(\varepsilon))$-fraction of the constraints given a $(1-\varepsilon)$-satisfiable instance, where $g(\varepsilon) \rightarrow 0$ as $\varepsilon \rightarrow 0$, $g(0)=0$.

Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction ...
more >>>

Shachar Lovett, Jiapeng Zhang

The sensitivity conjecture is one of the central open problems in boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a boolean function to moments of its sensitivity. We prove this ... more >>>

Alan Guo, Elad Haramaty, Madhu Sudan

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probabilility. A local tester for a code is said to be ``robust'' ... more >>>

Anindya De, Elchanan Mossel, Joe Neeman

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. ... more >>>

Oded Goldreich, Avi Wigderson

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.

Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.

We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ...
more >>>

Maya Leshkowitz

Consider an interactive proof system for some set S that has randomness complexity r(n) for instances of length n, and arbitrary round complexity. We show a public-coin interactive proof system for S of round complexity O(r(n)/log n). Furthermore, the randomness complexity is preserved up to a constant factor, and the ... more >>>

Takeshi Koshiba, Yoshiharu Seri

We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider ... more >>>

Boaz Barak, Prasad Raghavendra, David Steurer

We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with ... 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 >>>

Philippe Moser

We use recent results on the hardness of resource-bounded

Kolmogorov random strings, to prove that RP is small in SUBEXP

else ZPP=PSPACE and NP=EXP.

We also prove that if NP is not small in SUBEXP, then

NP=AM, improving a former result which held for the measure ...
more >>>

Frank Neumann, Carsten Witt

Ant Colony Optimization (ACO) has become quite popular in recent

years. In contrast to many successful applications, the theoretical

foundation of this randomized search heuristic is rather weak.

Building up such a theory is demanded to understand how these

heuristics work as well as to ...
more >>>