All reports by Author Paul Beame:

__
TR24-011
| 24th January 2024
__

Paul Beame, Niels Kornerup#### Quantum Time-Space Tradeoffs for Matrix Problems

Revisions: 1

__
TR23-005
| 13th January 2023
__

Paul Beame, Niels Kornerup#### Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Revisions: 2

__
TR22-173
| 3rd December 2022
__

Paul Beame, Sajin Koroth#### On Disperser/Lifting Properties of the Index and Inner-Product Functions

Revisions: 1

__
TR18-114
| 6th June 2018
__

Paul Beame, Shayan Oveis Gharan, Xin Yang#### Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials

__
TR17-151
| 8th October 2017
__

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere#### Stabbing Planes

Revisions: 3

__
TR17-120
| 31st July 2017
__

Paul Beame, Shayan Oveis Gharan, Xin Yang#### Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions

Revisions: 1

__
TR13-127
| 15th September 2013
__

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

__
TR12-178
| 18th December 2012
__

Paul Beame, Raphael Clifford, Widad Machmouchi#### Sliding Windows With Limited Storage

Revisions: 1

__
TR11-149
| 4th November 2011
__

Paul Beame, Chris Beck, Russell Impagliazzo#### Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

__
TR10-104
| 29th June 2010
__

Paul Beame, Widad Machmouchi#### Making RAMs Oblivious Requires Superlogarithmic Overhead

Revisions: 3
,
Comments: 1

__
TR09-072
| 3rd September 2009
__

Paul Beame, Trinh Huynh#### Hardness Amplification in Proof Complexity

Revisions: 2
,
Comments: 2

__
TR08-082
| 11th September 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity and Threshold Circuit Size of AC^0

Revisions: 2

__
TR08-061
| 11th June 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity of AC^0

Revisions: 1

__
TR08-024
| 26th February 2008
__

Paul Beame, Trinh Huynh#### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

__
TR06-140
| 8th November 2006
__

Paul Beame, Russell Impagliazzo, Nathan Segerlind#### Formula Caching in DPLL

__
TR05-053
| 4th May 2005
__

Paul Beame, Nathan Segerlind#### Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

__
TR04-012
| 19th December 2003
__

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore#### The Resolution Complexity of Random Graph $k$-Colorability

__
TR02-023
| 16th April 2002
__

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal#### Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revisions: 1

__
TR00-025
| 20th May 2000
__

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee#### Super-linear time-space tradeoff lower bounds for randomized computation

__
TR98-067
| 12th November 1998
__

Paul Beame#### Propositional Proof Complexity: Past, Present and Future

__
TR98-053
| 30th August 1998
__

Paul Beame, Michael Saks, Jayram S. Thathachar#### Time-Space Tradeoffs for Branching Programs

Comments: 1

__
TR98-028
| 28th May 1998
__

Paul Beame, Faith Fich#### On Searching Sorted Lists: A Near-Optimal Lower Bound

Paul Beame, Niels Kornerup

We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems---including matrix-vector product, matrix inversion, matrix multiplication and powering---existing ... more >>>

Paul Beame, Niels Kornerup

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>

Paul Beame, Sajin Koroth

Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be ... more >>>

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by

branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ...
more >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior ... more >>>

Paul Beame, Raphael Clifford, Widad Machmouchi

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

Paul Beame, Raphael Clifford, Widad Machmouchi

We consider time-space tradeoffs for exactly computing frequency

moments and order statistics over sliding windows.

Given an input of length $2n-1$, the task is to output the function of

each window of length $n$, giving $n$ outputs in total.

Computations over sliding windows are related to direct sum problems

except ...
more >>>

Paul Beame, Chris Beck, Russell Impagliazzo

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>

Paul Beame, Widad Machmouchi

We prove a time-space tradeoff lower bound of $T =

\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for

randomized oblivious branching programs to compute $1GAP$, also

known as the pointer jumping problem, a problem for which there is a

simple deterministic time $n$ and space $O(\log n)$ RAM (random

access machine) algorithm.

In ... more >>>

Paul Beame, Trinh Huynh

We present a generic method for converting any family of unsatisfiable CNF formulas that require large resolution rank into CNF formulas whose refutation requires large rank for proof systems that manipulate polynomials or polynomial threshold functions of degree at most $k$ (known as ${\rm Th}(k)$ proofs). Such systems include: Lovasz-Schrijver ... more >>>

Paul Beame, Trinh Huynh

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>

Paul Beame, Trinh Huynh

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once ... more >>>

Paul Beame, Trinh Huynh

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

Paul Beame, Russell Impagliazzo, Nathan Segerlind

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability. We formalize these methods by ... more >>>

Paul Beame, Nathan Segerlind

We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>>

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.

For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ...
more >>>

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal

We prove a quasi-polynomial lower bound on the size of bounded-depth

Frege proofs of the pigeonhole principle $PHP^{m}_n$ where

$m= (1+1/{\polylog n})n$.

This lower bound qualitatively matches the known quasi-polynomial-size

bounded-depth Frege proofs for these principles.

Our technique, which uses a switching lemma argument like other lower bounds

for ...
more >>>

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

We prove the first time-space lower bound tradeoffs for randomized

computation of decision problems. The bounds hold even in the

case that the computation is allowed to have arbitrary probability

of error on a small fraction of inputs. Our techniques are an

extension of those used by Ajtai in his ...
more >>>

Paul Beame

Proof complexity, the study of the lengths of proofs in

propositional logic, is an area of study that is fundamentally connected

both to major open questions of computational complexity theory and

to practical properties of automated theorem provers. In the last

decade, there have been a number of significant advances ...
more >>>

Paul Beame, Michael Saks, Jayram S. Thathachar

We obtain the first non-trivial time-space tradeoff lower bound for

functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a

Boolean function f that requires exponential size to be computed by any

branching program of length cn, for some constant c>1. We also give the first

separation result between the ...
more >>>

Paul Beame, Faith Fich

We obtain improved lower bounds for a class of static and dynamic

data structure problems that includes several problems of searching

sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent

striking improvements in searching algorithms given by Fredman and

Willard's ...
more >>>