
Privacy amplification is the task by which two cooperating parties transform
a shared weak secret, about which an eavesdropper may have side information,
into a uniformly random string uncorrelated from the eavesdropper. Privacy
amplification against passive adversaries, where it is assumed that the
communication is over a public but authenticated channel, can be achieved in
the presence of classical as well as quantum side information by a
singlemessage protocol based on strong extractors.
In 2009 Dodis and Wichs devised a twomessage protocol to achieve privacy
amplification against active adversaries, where the public communication
channel is no longer assumed to be authenticated, through the use of a
strengthening of strong extractors called nonmalleable extractors which they
introduced. Dodis and Wichs only analyzed the case of classical side
information.
We consider the task of privacy amplification against active adversaries with
quantum side information. Our main result is showing that the DodisWichs
protocol remains secure in this scenario provided its main building block, the
nonmalleable extractor, satisfies a notion of quantumproof nonmalleability
which we introduce. We show that an adaptation of a recent construction of
nonmalleable extractors due to Chattopadhyay et al. is quantum proof, thereby
providing the first protocol for privacy amplification that is secure against
active quantum adversaries. Our protocol is quantitatively comparable to the
nearoptimal protocols known in the classical setting.

Patterns on broken surfaces are wellknown from everyday experience, but
surprisingly, how and why they form are very much open questions. Welldefined
facets are commonly observed14 along fracture surfaces which are created by
slow tensile cracks. As facets appear in amorphous materials57, their
formation does not reflect microscopic order. Fracture mechanics, however,
predict that slow crack fronts should be straight, creating mirrorlike
surfaces813. In contrast, facetforming fronts propagate simultaneously within
different planes separated by steps. It is therefore unclear why steps are
stable, what determines their path and how they couple to crack front dynamics.
Here we show, by integrating realtime imaging of propagating crack fronts with
surface measurements, that steps are topological defects of crack fronts; crack
front separation into discontinuous overlapping segments provides the condition
for step stability. Steps drift at a constant angle to the local front
propagation direction and the increased local dissipation due to step formation
couples to the longrange deformation of the surrounding crack fronts. Slow
crack front dynamics are enslaved to changes in step heights and positions.
These observations show how 3D topology couples to 2D fracture dynamics to
provide a fundamental picture of how patterned surfaces are generated.

We give the first construction of a family of quantumproof extractors that
has optimal seed length dependence $O(\log(n/\varepsilon))$ on the input length
$n$ and error $\varepsilon$. Our extractors support any minentropy
$k=\Omega(\log{n} + \log^{1+\alpha}(1/\varepsilon))$ and extract
$m=(1\alpha)k$ bits that are $\varepsilon$close to uniform, for any desired
constant $\alpha > 0$. Previous constructions had a quadratically worse seed
length or were restricted to very large input minentropy or very few output
bits.
Our result is based on a generic reduction showing that any strong classical
condenser is automatically quantumproof, with comparable parameters. The
existence of such a reduction for extractors is a longstanding open question,
here we give an affirmative answer for condensers. Once this reduction is
established, to obtain our quantumproof extractors one only needs to consider
high entropy sources. We construct quantumproof extractors with the desired
parameters for such sources by extending a classical approach to extractor
construction, based on the use of blocksources and sampling, to the quantum
setting.
Our extractors can be used to obtain improved protocols for
deviceindependent randomness expansion and for privacy amplification.

In his 1947 paper that inaugurated the probabilistic method, Erd\H{o}s proved
the existence of $2\log{n}$Ramsey graphs on $n$ vertices. Matching Erd\H{o}s'
result with a constructive proof is a central problem in combinatorics, that
has gained a significant attention in the literature. The state of the art
result was obtained in the celebrated paper by Barak, Rao, Shaltiel and
Wigderson [Ann. Math'12], who constructed a
$2^{2^{(\log\log{n})^{1\alpha}}}$Ramsey graph, for some small universal
constant $\alpha > 0$.
In this work, we significantly improve the result of Barak~\etal and
construct $2^{(\log\log{n})^c}$Ramsey graphs, for some universal constant $c$.
In the language of theoretical computer science, our work resolves the problem
of explicitly constructing twosource dispersers for polylogarithmic entropy.

When fast cracks become unstable to microscopic branching (microbranching),
fracture no longer occurs in an effective 2D medium. We follow inplane crack
front dynamics via realtime measurements in brittle gels as microbranching
unfolds and progresses. We first show that {\em spatially local} energy balance
quantitatively describes crack dynamics, even when translational invariance is
badly broken. Furthermore, our results explain microbranch dynamics; why
microbranches form along spatially localized chains and how finitetime
formation of cusps along the crack front leads to their death.

In this paper, two structural results concerning low degree polynomials over
finite fields are given. The first states that over any finite field
$\mathbb{F}$, for any polynomial $f$ on $n$ variables with degree $d \le
\log(n)/10$, there exists a subspace of $\mathbb{F}^n$ with dimension $\Omega(d
\cdot n^{1/(d1)})$ on which $f$ is constant. This result is shown to be tight.
Stated differently, a degree $d$ polynomial cannot compute an affine disperser
for dimension smaller than $\Omega(d \cdot n^{1/(d1)})$. Using a recursive
argument, we obtain our second structural result, showing that any degree $d$
polynomial $f$ induces a partition of $F^n$ to affine subspaces of dimension
$\Omega(n^{1/(d1)!})$, such that $f$ is constant on each part.
We extend both structural results to more than one polynomial. We further
prove an analog of the first structural result to sparse polynomials (with no
restriction on the degree) and to functions that are close to low degree
polynomials. We also consider the algorithmic aspect of the two structural
results.
Our structural results have various applications, two of which are:
* Dvir [CC 2012] introduced the notion of extractors for varieties, and gave
explicit constructions of such extractors over large fields. We show that over
any finite field, any affine extractor is also an extractor for varieties with
related parameters. Our reduction also holds for dispersers, and we conclude
that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over
$F_2$.
* BenSasson and Kopparty [SIAM J. C 2012] proved that any degree 3 affine
disperser over a prime field is also an affine extractor with related
parameters. Using our structural results, and based on the work of Kaufman and
Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this
result to any constant degree.

We construct a biLipschitz bijection from the Boolean cube to the Hamming
ball of equal volume. More precisely, we show that for all even n there exists
an explicit bijection f from the ndimensional Boolean cube to the Hamming ball
of equal volume embedded in (n+1)dimensional Boolean cube, such that for all x
and y it holds that distance(x,y) / 5 <= distance(f(x),f(y)) <= 4 distance(x,y)
where distance(,) denotes the Hamming distance. In particular, this implies
that the Hamming ball is biLipschitz transitive.
This result gives a strong negative answer to an open problem of Lovett and
Viola [CC 2012], who raised the question in the context of sampling
distributions in lowlevel complexity classes. The conceptual implication is
that the problem of proving lower bounds in the context of sampling
distributions will require some new ideas beyond the sensitivitybased
structural results of Boppana [IPL 97].
We study the mapping f further and show that it (and its inverse) are
computable in DLOGTIMEuniform TC0, but not in AC0. Moreover, we prove that f
is "approximately local" in the sense that all but the last output bit of f are
essentially determined by a single input bit.

We perform realtime measurements of the net contact area between two blocks
of like material at the onset of frictional slip. We show that the process of
interface detachment, which immediately precedes the inception of frictional
sliding, is governed by three different types of detachment fronts. These
cracklike detachment fronts differ by both their propagation velocities and by
the amount of net contact surface reduction caused by their passage. The most
rapid fronts propagate at intersonic velocities but generate a negligible
reduction in contact area across the interface. SubRayleigh fronts are
cracklike modes which propagate at velocities up to the Rayleigh wave speed,
VR, and give rise to an approximate 10% reduction in net contact area. The most
efficient contact area reduction (~20%) is precipitated by the passage of slow
detachment fronts. These fronts propagate at anomalously slow velocities, which
are over an order of magnitude lower than VR yet orders of magnitude higher
than other characteristic velocity scales such as either slip or loading
velocities. Slow fronts are generated, in conjunction with intersonic fronts,
by the sudden arrest of subRayleigh fronts. No overall sliding of the
interface occurs until either of the slower two fronts traverses the entire
interface, and motion at the leading edge of the interface is initiated. Slip
at the trailing edge of the interface accompanies the motion of both the slow
and subRayleigh fronts. We might expect these modes to be important in both
fault nucleation and earthquake dynamics.

The dynamics of soliton pulses in the Nonlinear Schrodinger Equation (NLSE)
driven by an external Traveling wave is studied analytically and numerically.
The Hamiltonian structure of the system is used to show that, in the adiabatic
approximation for a single soliton, the problem is integrable despite the large
number of degrees of freedom. Fixed points of the system are found, and their
linear stability is investigated. The fixed points correspond to a Doppler
shifted resonance between the external wave and the soliton. The structure and
topological changes of the phase space of the soliton parameters as functions
of the strength of coupling are investigated. A physical derivation of the
driven NLSE is given in the context of optical pulse propagation in asymmetric,
twincore optical fibers. The results can be applied to soliton stabilization
and amplification.