2,135 research outputs found
Translationally Invariant Constraint Optimization Problems
No full textWe study the complexity of classical constraint satisfaction problems on a 2D
grid. Specifically, we consider the complexity of function versions of such
problems, with the additional restriction that the constraints are
translationally invariant, namely, the variables are located at the vertices of
a 2D grid and the constraint between every pair of adjacent variables is the
same in each dimension. The only input to the problem is thus the size of the
grid. This problem is equivalent to one of the most interesting problems in
classical physics, namely, computing the lowest energy of a classical system of
particles on the grid. We provide a tight characterization of the complexity of
this problem, and show that it is complete for the class . Gottesman
and Irani (FOCS 2009) also studied classical translationally-invariant
constraint satisfaction problems; they show that the problem of deciding
whether the cost of the optimal solution is below a given threshold is
NEXP-complete. Our result is thus a strengthening of their result from the
decision version to the function version of the problem. Our result can also be
viewed as a generalization to the translationally invariant setting, of
Krentel's famous result from 1988, showing that the function version of SAT is
complete for the class . An essential ingredient in the proof is a
study of the complexity of a gapped variant of the problem. We show that it is
NEXP-hard to approximate the cost of the optimal assignment to within an
additive error of , for an grid. To the best of
our knowledge, no gapped result is known for CSPs on the grid, even in the
non-translationally invariant case. As a byproduct of our results, we also show
that a decision version of the optimization problem which asks whether the cost
of the optimal assignment is odd or even is also complete for .Comment: 75 pages, 13 figure
The Subset Assignment Problem for Data Placement in Caches
No full textWe introduce the subset assignment problem in which items of varying sizes are placed in a set of bins with limited capacity. Items can be replicated and placed in any subset of the bins. Each (item, subset) pair has an associated cost. Not assigning an item to any of the bins is not free in general and can potentially be the most expensive option. The goal is to minimize the total cost of assigning items to subsets without exceeding the bin capacities. This problem is motivated by the design of caching systems composed of banks of memory with varying cost/performance specifications. The ability to replicate a data item in more than one memory bank can benefit the overall performance of the system with a faster recovery time in the event of a memory failure. For this setting, the number n of data objects (items) is very large and the number d of memory banks (bins) is a small constant (on the order of 3 or 4). Therefore, the goal is to determine an optimal assignment in time that minimizes dependence on n. The integral version of this problem is NP-hard since it is a generalization of the knapsack problem. We focus on an efficient solution to the LP relaxation as the number of fractionally assigned items will be at most d. If the data objects are small with respect to the size of the memory banks, the effect of excluding the fractionally assigned data items from the cache will be small. We give an algorithm that solves the LP relaxation and runs in time O(binom{3^d}{d+1} poly(d) n log(n) log(nC) log(Z)), where Z is the maximum item size and C the maximum storage cost
Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction
No full textWe introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in Õ(√{nh}) time, w.h.p., where h is the size of the output
Quantum search-to-decision reductions and the state synthesis problem
No full textIt is a useful fact in classical computer science that many search problems
are reducible to decision problems; this has led to decision problems being
regarded as the computational task to study in complexity
theory. In this work, we explore search-to-decision reductions for quantum
search problems, wherein a quantum algorithm makes queries to a classical
decision oracle to output a desired quantum state. In particular, we focus on
search-to-decision reductions for , and show that there exists a
quantum polynomial-time algorithm that can generate a witness for a
problem up to inverse polynomial precision by making one query
to a decision oracle. We complement this result by showing that
-search does reduce to -decision in
polynomial-time, relative to a quantum oracle.
We also explore the more general , in which
the goal is to efficiently synthesize a target state by making queries to a
classical oracle encoding the state. We prove that there exists a classical
oracle with which any quantum state can be synthesized to inverse polynomial
precision using only one oracle query and to inverse exponential precision
using two oracle queries. This answers an open question of Aaronson from 2016,
who presented a state synthesis algorithm that makes queries to a
classical oracle to prepare an -qubit state, and asked if the query
complexity could be made sublinear.Comment: v2 included new figures and improved explanations. No technical
content was changed between versions. Comments are welcome and encouraged
Non-discursive knowledge and the construction of identity. Potters, potting and performance at the bronze age tell of Százhalombatta, Hungary
No full textThis article explores the relationship between the making of things and the making of people at the Bronze Age tell at Százhalombatta, Hungary. Focusing on potters and potting, we explore how the performance of non-discursive knowledge was critical to the construction of social categories. Potters literally came into being as potters through repeated bodily enactment of potting skills. Potters also gained their identity in the social sphere through the connection between their potting performance and their audience. We trace degrees of skill in the ceramic record to reveal the material articulation of non-discursive knowledge and consider the ramifications of the differential acquisition of non-discursive knowledge for the expression of different kinds of potter's identities. The creation of potters as a social category was essential to the ongoing creation of specific forms of material culture. We examine the implications of altered potters' performances and the role of non-discursive knowledge in the construction of social models of the Bronze Ag
Microtus irani Thomas 1921
No full text173. Iranian Vole Microtus irani French: Campagnol persan / German: Iran-Wihlmaus / Spanish: Topillo de Iran Other common names: Persian Vole; Schidlovsky Pine Vole (schidlovskii) Taxonomy. Microtus irani Thomas, 1921, “Bagh-i-Rezi, Shiraz, [Iran]. Alt. 5200" [= 1585 m].” Microtus irani is in subgenus Sumeriomys and socialis species group. In the past, M. irani was occasionally synonymized with M. socialis. If recognized as a species on its own right, then rani included medium-sized species of Microtus with moderately shallow skull, swollen bullae, and complex molar pattern (paradoxus, mustersi, and partly also guentheri). Taxonomic scope of rani is still ill-defined. Diploid number is 60 in subspecies karamani and schidlovskii but is not known with certainty in subspecies wrani. Molecular studies identified close relationships between rani, schidlovski, and karamani, which are synonymized here. A new species was described recently near Kilis, southern Turkey, as M. elbeyli by N. Yigit, E. Colak and M. Sozen in 2016. Earlier, the same population was classified as M. irani. Karyotype of M. elbeyli is unique (2n = 46), but its molecular makeup is not known. M. elbeyli is known only from the type locality and its position within the subgenus Sumeriomys is enigmatic. Low diploid number suggests elbeyli to belong to the guenther: species group and may be close to M. dogramacii. Three subspecies recognized. Subspecies and Distribution. M.i.rantThomas,1921—SWIran. M.i.karamaniKrystufeketal.,2010—STurkey,Lebanon,NWSyria,andWIran. M. i. schidlovskii Argyropulo, 1933 — E Turkey, SC Georgia, W Armenia, and NW & N Iran. Also present in Iraq, but subspecies involved not known. Descriptive notes. Head-body 105-130 mm, tail 20-36 mm for subspecies rani head-body 107-123 mm, tail 26-31-7 mm, and weight 33-41-7 g for subspecies karamani; head-body 84-112 mm, tail 21-34 mm for subspecies schidlovskii. Males (schidlovskii) are, on average, heavier (32-7 g) than females (26-9 g). The Iranian Vole is mediumto large-sized, with tail less than 25% of head-body length. Eyes are relatively large, and ears overtop pelage. Females have two pairs of pectoral and two pairs of inguinal nipples. Fur is long, dense, and soft. Dorsum is pale and sandy buff in rani, grayish brown or brown in schidlovskii, and pinkish buff to brownish buff with fawn tints, grizzled by blackish tips of long hair, in karamani. Venter is whitish to grayish white, clouded by slate-colored bases of hairs; demarcation on flanks is faint (irani) or distinct (karamani). Tail is indistinctly bicolored, fawn, white, buffwhite, or brownish above. Skull is moderately deep, with wide interorbital region. Bullae are swollen in karamani. Angular process on outer wall of mandibular rhamus is prominent. Incisors are orthodont in karamani, and proodont in the remaining subspecies. Molars are complex, and M? has in some populations a high incidence of postero-lingual loop. Habitat. Steppe in mountains, grasslands with clumps of bushes, cultivated fields, and orchards at elevations of 1000-2100 m. Food and Feeding. Iranian Voles can cause local damage to agriculture. Breeding. Gestation of subspecies schidlovskii lasts 21-22 days, and mean litter size is 3-4. At low densities, female Iranian Voles mature at 65 days old, but at high densities, maturity is postponed to 76 days. Activity patterns. Iranian Voles were captured during day and night. They dig simple burrows. Movements, Home range and Social organization. No information. Status and Conservation. Classified as Data Deficient on The IUCN Red List. Subspecies schidlovskii was classified as a distinct species as Least Concern on The IUCN Red List (as M. schidlovskii). Unsettled taxonomy is the main obstacle for objective assessment of conservation status. Bibliography. Arslan et al. (2016), Gromov & Erbajeva (1995), Krystufek & Kefelioglu (2001), Krystufek, Abi-Said & Hladnik (2013), Krystufek, Buzan et al. (2009), Krystufek, Vohralik et al. (2010), Mahmoudi, Darvish & Aliabadian (2014, 2015), Yigit et al. (2016), Zorenko (2013), Zorenko et al. (1994).Published as part of Don E. Wilson, Russell A. Mittermeier & Thomas E. Lacher, Jr, 2017, Cricetidae, pp. 204-535 in Handbook of the Mammals of the World – Volume 7 Rodents II, Barcelona :Lynx Edicions on page 350, DOI: 10.5281/zenodo.670714
Structural analysis and parametric study ballasted track in sandy regions
No full textThe sand intrusion in railway tracks in sandy regions can significantly change the mechanical behaviour of tracks and thus threaten the safety of train operation. This paper presents substantial field tests on both sandy and clean railway tracks to study the effect of sand intrusion on the longitudinal resistance of ballast bed and the vibration behaviour of track structures. After that, a 3D multi-scale the discrete element model is developed to study the micro-contact between ballast particles and the vibration behaviour of sandy tracks during train passing in detail. Also, the effect of train speeds and axle loads on the mechanical behaviour of sandy tracks is discussed. The results show that the sand intrusion increases the vibration acceleration amplitude of rail and sleeper by 11.3% and 50.3%, while ballast bed decreases by 44.9%. Besides, the sand intrusion significantly changes the energy distribution in the track, wherein the frequencies of the highest energy of rail and sleeper are increased while that of the ballast bed is decreased. The parametric study shows the high train speed can cause the increase in overall acceleration of the ballast bed and high axle load can cause an increase in the micro-contact forces between ballast particles, diffusion angle of the contact force chain, displacements of ballast particles, acceleration of ballast particles, and sleeper displacements.Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Mechanics and Physics of Structure
Crushed rock and clay amelioration of a nutrient decifient, sandy soil of Maputaland
No full textBibliography: leaves 57-62.Various studies have suggested the possibility that food derived through subsistence agriculture in the Mseleni region of Maputaland contributes to malnutrition within the local community, particularfy within the high proportion of the population which suffers from a severe, disabling form of osteoarthritis. This study was conducted to determine if the application of local crushed rock or black clay to these nutrient deficient, sandy soils would increase available nutrient concentrations and improve the growth of plants in the ameliorated soil
Probabilistic analysis for scheduling with conflicts
No full textAbstractIn this paper, we consider scheduling jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that all concurrently running jobs must form an independent set in the graph. Our goal is to bound the maximum response time of any job in the system. We adopt a discrete model of time and assume that each job requires one time unit to be completed once it is started. It has been previously shown [S. Irani, V. Leung, Scheduling with conflicts, and applications to traffic signal control, in: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 1996] that the best competitive ratio achievable by any online algorithm is Ω(n), where n is the number of nodes in the graph. As a result, we study scheduling with conflicts under probabilistic assumptions about the input. Each node i has a value pi such that a job arrives at node i in any given time unit with probability pi. Arrivals at different nodes and during different time periods are independent. Under reasonable assumptions on the value for the pi’s, we are able to obtain a bounded competitive ratio for an arbitrary conflict graph. In addition, if the conflict graph is a perfect graph, we give an algorithm whose competitive ratio converges to 1
- …
