Randomness-efficient curve sampling

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions.

The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using O(log N + log(1/δ)) random bits exist, where N is the domain size and δ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in [TU06] where they obtained curve samplers with near-optimal randomness complexity.

In this thesis, we present an explicit construction of low-degree curve samplers with optimal randomness complexity (up to a constant factor) that sample curves of degree (m log_q(1/δ))^O(1) in F_q^m. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

The power of quantum Fourier sampling

How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms?

We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy.

Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.

The meaning of some common terms used in sampling toxic phytoplankton

The author explains some aspects of sampling phytoplankton blooms and the evaluation of results obtained from different methods. Qualitative and quantitative sampling is covered as well as filtration, freeze-drying and toxin separation.

A new synoptic survey of Northern Ireland lakes: sampling from the air

Northern Ireland has approximately 1670 lakes, which cover 4.4% of the land surface. However, most of the water area is accounted for by the large lakes such as Lough Neagh (385 km2) and Lower Lough Erne (109.5 km ). The majority of lakes are less than 100 hectares in area. They tend to be distributed towards the south and west of the Province, where extensive drumlin swarms are rich in small waterbodies. In 1988-1991, 610 of the 708 lakes between one and 100 hectares were sampled by the Northern Ireland Lake Survey. The objective was to assess their conservation status based on their aquatic macrophyte flora, but in addition to extensive plant surveys, the water of each lake was analysed for a range of chemical variables. This article reports on a full-scale survey carried out in early March 2002. The survey was taken with help of two helicopters. The authorise summarise the results of the chemical analysis of the survey.

Wave-front analysis method of circular aperture sampling for collimation testing

A new type of wave-front analysis method for the collimation testing of laser beams is proposed. A concept of wave-front height is defined, and, on this basis, the wave-front analysis method of circular aperture sampling is introduced. The wave-front height of the tested noncollimated wave can be estimated from the distance between two identical fiducial diffraction planes of the sampled wave, and then the divergence is determined. The design is detailed, and the experiment is demonstrated. The principle and experiment results of the method are presented. Owing to the simplicity of the method and its low cost, it is a promising method for checking the collimation of a laser beam with a large divergence. © 2005 Optical Society of America.

Development of a sampling expert system:"FISHMAP"

This research program consisted of three major component areas: (I) development of experimental design, (II) calibration of the trawl design, and (III) development of the foundation for stock assessment analysis. The products which have I. EXPERIMENTAL DESIGN resulted from - the program are indicated below: The study was successful in identifying spatial and temporal distribution characteristics of the several key species, and the relationships between given species catches and environmental and physical factors which are thought to influence species abundance by areas within the mainstem of the Chesapeake Bay and tributaries

Description of sampling stations, methods of benthic sampling and biological water quality assessment; with some consideration of the influence of sample variation on the assessment values obtained

The first bilateral study of methods of biological sampling and biological methods of water quality assessment took place during June 1977 on selected sampling sites in the catchment of the River Trent (UK). The study was arranged in accordance with the protocol established by the joint working group responsible for the Anglo-Soviet Environmental Agreement. The main purpose of the bilateral study in Nottingham was for some of the methods of sampling and biological assessment used by UK biologists to be demonstrated to their Soviet counterparts and for the Soviet biologists to have the opportunity to test these methods at first hand in order to judge the potential of any of these methods for use within the Soviet Union. This paper is concerned with the nine river stations in the Trent catchment.

Bertso transformation with pattern-based sampling

This paper presents a method to generate new melodies, based on conserving the semiotic structure of a template piece. A pattern discovery algorithm is applied to a template piece to extract significant segments: those that are repeated and those that are transposed in the piece. Two strategies are combined to describe the semiotic coherence structure of the template piece: inter-segment coherence and intra-segment coherence. Once the structure is described it is used as a template for new musical content that is generated using a statistical model created from a corpus of bertso melodies and iteratively improved using a stochastic optimization method. Results show that the method presented here effectively describes a coherence structure of a piece by discovering repetition and transposition relations between segments, and also by representing the relations among notes within the segments. For bertso generation the method correctly conserves all intra and inter-segment coherence of the template, and the optimization method produces coherent generated melodies.