
TARA (Telescope Array Radar) is a cosmic ray radar detection experiment
colocated with Telescope Array, the conventional surface scintillation detector
(SD) and fluorescence telescope detector (FD) near Delta, Utah, U.S.A. The TARA
detector combines a 40 kW, 54.1 MHz VHF transmitter and highgain transmitting
antenna which broadcasts the radar carrier over the SD array and within the FD
field of view, towards a 250 MS/s DAQ receiver. TARA has been collecting data
since 2013 with the primary goal of observing the radar signatures of extensive
air showers (EAS). Simulations indicate that echoes are expected to be short in
duration (~10 microseconds) and exhibit rapidly changing frequency, with rates
on the order of 1 MHz/microsecond. The EAS radar crosssection (RCS) is
currently unknown although it is the subject of over 70 years of speculation. A
novel signal search technique is described in which the expected radar echo of
a particular air shower is used as a matched filter template and compared to
waveforms obtained by triggering the radar DAQ using the Telescope Array
fluorescence detector. No evidence for the scattering of radio frequency
radiation by EAS is obtained to date. We report the first quantitative RCS
upper limits using EAS that triggered the Telescope Array Fluorescence
Detector.

We study threeway joins on MapReduce. Joins are very useful in a multitude
of applications from data integration and traversing social networks, to mining
graphs and automatabased constructions. However, joins are expensive, even for
moderate data sets; we need efficient algorithms to perform distributed
computation of joins using clusters of many machines. MapReduce has become an
increasingly popular distributed computing system and programming paradigm. We
consider a stateoftheart MapReduce multiway join algorithm by Afrati and
Ullman and show when it is appropriate for use on very large data sets. By
providing a detailed experimental study, we demonstrate that this algorithm
scales much better than what is suggested by the original paper. However, if
the join result needs to be summarized or aggregated, as opposed to being only
enumerated, then the aggregation step can be integrated into a cascade of
twoway joins, making it more efficient than the other algorithm, and thus
becomes the preferred solution.

Regret minimizing sets are a very recent approach to representing a dataset D
with a small subset S of representative tuples. The set S is chosen such that
executing any top1 query on S rather than D is minimally perceptible to any
user. To discover an optimal regret minimizing set of a predetermined
cardinality is conjectured to be a hard problem. In this paper, we generalize
the problem to that of finding an optimal k$regret minimizing set, wherein the
difference is computed over topk queries, rather than top1 queries.
We adapt known geometric ideas of topk depth contours and the reverse topk
problem. We show that the depth contours themselves offer a means of comparing
the optimality of regret minimizing sets using L2 distance. We design an
O(cn^2) plane sweep algorithm for two dimensions to compute an optimal regret
minimizing set of cardinality c. For higher dimensions, we introduce a greedy
algorithm that progresses towards increasingly optimal solutions by exploiting
the transitivity of L2 distance.

We consider the recently introduced monochromatic reverse topk queries which
ask for, given a new tuple q and a dataset D, all possible topk queries on D
union {q} for which q is in the result. Towards this problem, we focus on
designing indexes in two dimensions for repeated (or batch) querying, a novel
but practical consideration. We present the insight that by representing the
dataset as an arrangement of lines, a critical kpolygon can be identified and
used exclusively to respond to reverse topk queries. We construct an index
based on this observation which has guaranteed worstcase query cost that is
logarithmic in the size of the kpolygon.
We implement our work and compare it to related approaches, demonstrating
that our index is fast in practice. Furthermore, we demonstrate through our
experiments that a kpolygon is comprised of a small proportion of the original
data, so our index structure consumes little disk space.

In this paper, we present a method for recognising an agent's behaviour in
dynamic, noisy, uncertain domains, and across multiple levels of abstraction.
We term this problem online plan recognition under uncertainty and view it
generally as probabilistic inference on the stochastic process representing the
execution of the agent's plan. Our contributions in this paper are twofold. In
terms of probabilistic inference, we introduce the Abstract Hidden Markov Model
(AHMM), a novel type of stochastic processes, provide its dynamic Bayesian
network (DBN) structure and analyse the properties of this network. We then
describe an application of the RaoBlackwellised Particle Filter to the AHMM
which allows us to construct an efficient, hybrid inference method for this
model. In terms of plan recognition, we propose a novel plan recognition
framework based on the AHMM as the plan execution model. The RaoBlackwellised
hybrid inference for AHMM can take advantage of the independence properties
inherent in a model of plan execution, leading to an algorithm for online
probabilistic plan recognition that scales well with the number of levels in
the plan hierarchy. This illustrates that while stochastic models for plan
execution can be complex, they exhibit special structures which, if exploited,
can lead to efficient plan recognition algorithms. We demonstrate the
usefulness of the AHMM framework via a behaviour recognition system in a
complex spatial environment using distributed video surveillance data.

Exchange bias effect is an important attribute in several device
applications. Traditionally, it is discussed as a form of exchange anisotropy
at the interface between the ferromagnetic/antiferromagnetic layers of two
distinct systems. We report here on the magnetically ordered alloys possessing
the feature of unidirectional anisotropy, which reverses its sign across a
characteristic temperature. These are admixed rare earth intermetallics,
comprising two dissimilar rare earth (RE) ions, belonging to the two different
halves of the 4fseries and imbibing the notion of ferromagnetic coupling
between the spins of all 4frare earth ions and that of the conduction
electrons. Magnetic moments of dissimilar RE ions in such admixed alloys,
however, get antiferromagnetically coupled and they display magnetic
compensation feature such that the field induced reversal in the orientation of
the magnetic moments of dissimilar rare earth ions happens across the
compensation temperature (Tcomp). Above a threshold field, the conduction
electron polarization also reverses its sign across Tcomp, this is argued to
correlate with the observed phase reversal in the exchange bias field.

We consider a fundamental problem in data structures, static predecessor
searching: Given a subset S of size n from the universe [m], store S so that
queries of the form "What is the predecessor of x in S?" can be answered
efficiently. We study this problem in the cell probe model introduced by Yao.
Recently, Beame and Fich obtained optimal bounds on the number of probes needed
by any deterministic query scheme if the associated storage scheme uses only
n^{O(1)} cells of word size (\log m)^{O(1)} bits. We give a new lower bound
proof for this problem that matches the bounds of Beame and Fich. Our lower
bound proof has the following advantages: it works for randomised query schemes
too, while Beame and Fich's proof works for deterministic query schemes only.
It also extends to `quantum addressonly' query schemes that we define in this
paper, and is simpler than Beame and Fich's proof. We prove our lower bound
using the round elimination approach of Miltersen, Nisan, Safra and Wigderson.
Using tools from information theory, we prove a strong round elimination lemma
for communication complexity that enables us to obtain a tight lower bound for
the predecessor problem. Our strong round elimination lemma also extends to
quantum communication complexity. We also use our round elimination lemma to
obtain a rounds versus communication tradeoff for the `greaterthan' problem,
improving on the tradeoff in Miltersen et al. We believe that our round
elimination lemma is of independent interest and should have other
applications.

We introduce a new model for studying quantum data structure problems  the
"quantum cell probe model". We prove a lower bound for the static predecessor
problem in the addressonly version of this model where we allow quantum
parallelism only over the `address lines' of the queries. The addressonly
quantum cell probe model subsumes the classical cell probe model, and many
quantum query algorithms like Grover's algorithm fall into this framework. Our
lower bound improves the previous known lower bound for the predecessor problem
in the classical cell probe model with randomised query schemes, and matches
the classical deterministic upper bound of Beame and Fich. Beame and Fich have
also proved a matching lower bound for the predecessor problem, but only in the
classical deterministic setting. Our lower bound has the advantage that it
holds for the more general quantum model, and also, its proof is substantially
simpler than that of Beame and Fich. We prove our lower bound by obtaining a
round elimination lemma for quantum communication complexity. A similar lemma
was proved by Miltersen, Nisan, Safra and Wigderson for classical communication
complexity, but it was not strong enough to prove a lower bound matching the
upper bound of Beame and Fich. Our quantum round elimination lemma also allows
us to prove rounds versus communication tradeoffs for some quantum
communication complexity problems like the "greaterthan" problem. We also
study the "static membership" problem in the quantum cell probe model.
Generalising a result of Yao, we show that if the storage scheme is implicit,
that is it can only store members of the subset and `pointers', then any
quantum query scheme must make $\Omega(\log n)$ probes.

We study the quantum complexity of the static set membership problem: given a
subset S (S \leq n) of a universe of size m (m \gg n), store it as a table of
bits so that queries of the form `Is x \in S?' can be answered. The goal is to
use a small table and yet answer queries using few bitprobes. This problem was
considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where
lower and upper bounds were shown for this problem in the classical
deterministic and randomized models. In this paper, we formulate this problem
in the "quantum bitprobe model" and show tradeoff results between space and
time.In this model, the storage scheme is classical but the query scheme is
quantum.We show, roughly speaking, that similar lower bounds hold in the
quantum model as in the classical model, which imply that the classical upper
bounds are more or less tight even in the quantum case. Our lower bounds are
proved using linear algebraic techniques.