Source author record

Allison Lewko

Allison Lewko appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CA math.PR Distributed, Parallel, and Cluster Computing math.NT Data Structures and Algorithms Information Theory math.CO math.IT

Catalog footprint

What is connected

11works

8topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Balancing Communication for Multi-party Interactive Coding

We consider interactive coding in a setting where $n$ parties wish to compute a joint function of their inputs via an interactive protocol over imperfect channels. We assume that adversarial errors can comprise a $\mathcal{O}(\frac{1}{n})$ fraction of the total communication, occurring anywhere on the communication network. Our goal is to maintain a constant multiplicative overhead in the total communication required, as compared to the error-free setting, and also to balance the workload over the different parties. We build upon the prior protocol of Jain, Kalai, and Lewko, but while that protocol relies on a single coordinator to shoulder a heavy burden throughout the protocol, we design a mechanism to pass the coordination duties from party to party, resulting in a more even distribution of communication over the course of the computation.

preprint2013arXiv

Maximal Operators Associated to Multiplicative Characters

We show that the natural analogue of the Carleson-Hunt inequality fails for multiplicative characters.

preprint2013arXiv

On the Complexity of Asynchronous Agreement Against Powerful Adversaries

We introduce new techniques for proving lower bounds on the running time of randomized algorithms for asynchronous agreement against powerful adversaries. In particular, we define a \emph{strongly adaptive adversary} that is computationally unbounded and has a limited ability to corrupt a dynamic subset of processors by erasing their memories. We demonstrate that the randomized agreement algorithms designed by Ben-Or and Bracha to tolerate crash or Byzantine failures in the asynchronous setting extend to defeat a strongly adaptive adversary. These algorithms have essentially perfect correctness and termination, but at the expense of exponential running time. In the case of the strongly adaptive adversary, we show that this dismally slow running time is \emph{inherent}: we prove that any algorithm with essentially perfect correctness and termination against the strongly adaptive adversary must have exponential running time. We additionally interpret this result as yielding an enhanced understanding of the tools needed to simultaneously achieving perfect correctness and termination as well as fast running time for randomized algorithms tolerating crash or Byzantine failures.

preprint2012arXiv

A Variational Barban-Davenport-Halberstam Theorem

We prove variational forms of the Barban-Davenport-Halberstam Theorem and the large sieve inequality. We apply our result to prove an estimate for the sum of the squares of prime differences, averaged over arithmetic progressions.

preprint2012arXiv

Estimates for the Square Variation of Partial Sums of Fourier Series and their Rearrangements

We investigate the square variation operator $V^2$ (which majorizes the partial sum maximal operator) on general orthonormal systems (ONS) of size $N$. We prove that the $L^2$ norm of the $V^2$ operator is bounded by $O(\ln(N))$ on any ONS. This result is sharp and refines the classical Rademacher-Menshov theorem. We show that this can be improved to $O(\sqrt{\ln(N)})$ for the trigonometric system, which is also sharp. We show that for any choice of coefficients, this truncation of the trigonometric system can be rearranged so that the $L^2$ norm of the associated $V^2$ operator is $O(\sqrt{\ln\ln(N)})$. We also show that for $p>2$, a bounded ONS of size $N$ can be rearranged so that the $L^2$ norm of the $V^p$ operator is at most $O_p(\ln \ln (N))$ uniformly for all choices of coefficients. This refines Bourgain's work on Garsia's conjecture, which is equivalent to the $V^{\infty}$ case. Several other results on operators of this form are also obtained. The proofs rely on combinatorial and probabilistic methods.

preprint2012arXiv

Orthonormal Systems in Linear Spans

We show that any $N$-dimensional linear subspace of $L^2(\mathbb{T})$ admits an orthonormal system such that the $L^2$ norm of the square variation operator $V^2$ is as small as possible. When applied to the span of the trigonometric system, we obtain an orthonormal system of trigonometric polynomials with a $V^2$ operator that is considerably smaller than the associated operator for the trigonometric system itself.

preprint2012arXiv

The Square Variation of Rearranged Fourier Series

We prove that there exists a rearrangement of the first $N$ elements of the trigonometric system such that the $L^2$-norm of the square variation operator is at most $O_ε(\log^{9/22+ε}(N))$. This is an improvement over $O(\log^{1/2}(N))$ from the canonical ordering.

preprint2011arXiv

An Exact Asymptotic for the Square Variation of Partial Sum Processes

We establish an exact asymptotic formula for the square variation of certain partial sum processes. Let $\{X_{i}\}$ be a sequence of independent, identically distributed mean zero random variables with finite variance $σ$ and satisfying a moment condition $\mathbb{E}[|X_{i}|^{2+δ} ] < \infty$ for some $δ> 0$. If we let $\mathcal{P}_{N}$ denote the set of all possible partitions of the interval $[N]$ into subintervals, then we have that $\max_{π\in \mathcal{P}_{N}} \sum_{I \in π} | \sum_{i\in I} X_{i}|^2 \sim 2 σ^2N \ln \ln(N)$ holds almost surely. This can be viewed as a variational strengthening of the law of the iterated logarithm and refines results of J. Qian on partial sum and empirical processes. When $δ= 0$, we obtain a weaker `in probability' version of the result.

preprint2011arXiv

Endpoint restriction estimates for the paraboloid over finite fields

We prove certain endpoint restriction estimates for the paraboloid over finite fields in three and higher dimensions. Working in the bilinear setting, we are able to pass from estimates for characteristic functions to estimates for general functions while avoiding the extra logarithmic power of the field size which is introduced by the dyadic pigeonhole approach. This allows us to remove logarithmic factors from the estimates obtained by Mockenhaupt and Tao in three dimensions and those obtained by Iosevich and Koh in higher dimensions.

preprint2011arXiv

On the Structure of Sets of Large Doubling

We investigate the structure of finite sets $A \subseteq \Z$ where $|A+A|$ is large. We present a combinatorial construction that serves as a counterexample to natural conjectures in the pursuit of an "anti-Freiman" theory in additive combinatorics. In particular, we answer a question along these lines posed by O'Bryant. Our construction also answers several questions about the nature of finite unions of $B_2[g]$ and $B^\circ_2[g]$ sets, and enables us to construct a $Λ(4)$ set which does not contain large $B_2[g]$ or $B^\circ_2[g]$ sets.

preprint2011arXiv

The Contest Between Simplicity and Efficiency in Asynchronous Byzantine Agreement

In the wake of the decisive impossibility result of Fischer, Lynch, and Paterson for deterministic consensus protocols in the aynchronous model with just one failure, Ben-Or and Bracha demonstrated that the problem could be solved with randomness, even for Byzantine failures. Both protocols are natural and intuitive to verify, and Bracha's achieves optimal resilience. However, the expected running time of these protocols is exponential in general. Recently, Kapron, Kempe, King, Saia, and Sanwalani presented the first efficient Byzantine agreement algorithm in the asynchronous, full information model, running in polylogarithmic time. Their algorithm is Monte Carlo and drastically departs from the simple structure of Ben-Or and Bracha's Las Vegas algorithms. In this paper, we begin an investigation of the question: to what extent is this departure necessary? Might there be a much simpler and intuitive Las Vegas protocol that runs in expected polynomial time? We will show that the exponential running time of Ben-Or and Bracha's algorithms is no mere accident of their specific details, but rather an unavoidable consequence of their general symmetry and round structure. We define a natural class of "fully symmetric round protocols" for solving Byzantine agreement in an asynchronous setting and show that any such protocol can be forced to run in expected exponential time by an adversary in the full information model. We assume the adversary controls $t$ Byzantine processors for $t = cn$, where $c$ is an arbitrary positive constant $< 1/3$. We view our result as a step toward identifying the level of complexity required for a polynomial-time algorithm in this setting, and also as a guide in the search for new efficient algorithms.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint