BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Brett Hemenway

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

ResearcherUnclaimed source record
Information Theorymath.ITmath.NTCryptography and Securityq-fin.CPq-fin.RMquant-ph

Catalog footprint

What is connected

6works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

6 published item(s)

preprint2016arXiv

Cryptographic applications of capacity theory: On the optimality of Coppersmith's method for univariate polynomials

We draw a new connection between Coppersmith's method for finding small solutions to polynomial congruences modulo integers and the capacity theory of adelic subsets of algebraic curves. Coppersmith's method uses lattice basis reduction to construct an auxiliary polynomial that vanishes at the desired solutions. Capacity theory provides a toolkit for proving when polynomials with certain boundedness properties do or do not exist. Using capacity theory, we prove that Coppersmith's bound for univariate polynomials is optimal in the sense that there are \emph{no} auxiliary polynomials of the type he used that would allow finding roots of size $N^{1/d+ε}$ for monic degree-$d$ polynomials modulo $N$. Our results rule out the existence of polynomials of any degree and do not rely on lattice algorithms, thus eliminating the possibility of even superpolynomial-time improvements to Coppersmith's bound. We extend this result to constructions of auxiliary polynomials using binomial polynomials, and rule out the existence of any auxiliary polynomial of this form that would find solutions of size $N^{1/d+ε}$ unless $N$ has a very small prime factor.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Sensitivity and Computational Complexity in Financial Networks

Modern financial networks exhibit a high degree of interconnectedness and determining the causes of instability and contagion in financial networks is necessary to inform policy and avoid future financial collapse. In the American Economic Review, Elliott, Golub and Jackson proposed a simple model for capturing the dynamics of complex financial networks. In Elliott, Golub and Jackson's model, each institution in the network can buy underlying assets or percentage shares in other institutions (cross-holdings) and if any institution's value drops below a critical threshold value, its value suffers an additional failure cost. This work shows that even in simple model put forward by Elliott, Golub and Jackson there are fundamental barriers to understanding the risks that are inherent in a network. First, if institutions are not required to maintain a minimum amount of self-holdings, an $ε$ change in investments by a single institution can have an arbitrarily magnified influence on the net worth of the institutions in the system. This sensitivity result shows that if institutions have small self-holdings, then estimating the market value of an institution requires almost perfect information about every cross-holding in the system. Second, we show that even if a regulator has complete information about all cross-holdings in the system, it may be computationally intractable to even estimate the number of failures that could be caused by an arbitrarily small shock to the system. Together, these results show that any uncertainty in the cross-holdings or values of the underlying assets can be amplified by the network to arbitrarily large uncertainty in the valuations of institutions in the network.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Linear-time list recovery of high-rate expander codes

We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have been useful recently in constructing efficiently list-decodable codes, as well as explicit constructions of matrices for compressive sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most 1/2; in contrast, our codes can have rate $1 - ε$ for any $ε> 0$. We can plug our high-rate codes into a construction of Meir (2014) to obtain linear-time list recoverable codes of arbitrary rates, which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code. While list-recovery is interesting on its own, our primary motivation is applications to list-decoding. A slight strengthening of our result would implies linear-time and optimally list-decodable codes for all rates, and our work is a step in the direction of solving this important problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Local Correctability of Expander Codes

In this work, we present the first local-decoding algorithm for expander codes. This yields a new family of constant-rate codes that can recover from a constant fraction of errors in the codeword symbols, and where any symbol of the codeword can be recovered with high probability by reading $N^ε$ symbols from the corrupted codeword, where $N$ is the block-length of the code. Expander codes, introduced by Sipser and Spielman, are formed from an expander graph $G = (V,E)$ of degree $d$, and an inner code of block-length $d$ over an alphabet $Σ$. Each edge of the expander graph is associated with a symbol in $Σ$. A string in $Σ^{E}$ will be a codeword if for each vertex in $V$, the symbols on the adjacent edges form a codeword in the inner code. We show that if the inner code has a smooth reconstruction algorithm in the noiseless setting, then the corresponding expander code has an efficient local-correction algorithm in the noisy setting. Instantiating our construction with inner codes based on finite geometries, we obtain novel locally decodable codes with rate approaching one. This provides an alternative to the multiplicity codes of Kopparty, Saraf and Yekhanin (STOC '11) and the lifted codes of Guo, Kopparty and Sudan (ITCS '13).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On congruent primes and class numbers of imaginary quadratic fields

We consider the problem of determining whether a given prime p is a congruent number. We present an easily computed criterion that allows us to conclude that certain primes for which congruency was previously undecided, are in fact not congruent. As a result, we get additional information on the possible sizes of Tate-Shafarevich groups of the associated elliptic curves. We also present a related criterion for primes p such that 16 divides the class number of the imaginary quadratic field Q(sqrt(-p)). Both results are based on descent methods. While we cannot show for either criterion individually that there are infinitely many primes that satisfy it nor that there are infinitely many that do not, we do exploit a slight difference between the two to conclude that at least one of the criteria is satisfied by infinitely many primes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On optimal entanglement assisted one-shot classical communication

The one-shot success probability of a noisy classical channel for transmitting one classical bit is the optimal probability with which the bit can be sent via a single use of the channel. Prevedel et al. (PRL 106, 110505 (2011)) recently showed that for a specific channel, this quantity can be increased if the parties using the channel share an entangled quantum state. We completely characterize the optimal entanglement-assisted protocols in terms of the radius of a set of operators associated with the channel. This characterization can be used to construct optimal entanglement-assisted protocols from the given classical channel and to prove the limit of such protocols. As an example, we show that the Prevedel et al. protocol is optimal for two-qubit entanglement. We also prove some simple upper bounds on the improvement that can be obtained from quantum and no-signaling correlations.

0 citations0 reviewsNo code linkedOpen access