10,452 research outputs found
Recommended from our members
Asian American Crossroads Lecture Series: Dr. Eric Tang
No full textThis flyer promotes Dr. Eric Tang's lecture 'No Justice: Anti-Asian Violence, White-Supremacist Terror & Mental Illness" for the Asian American Crossroads Lecture Series.Asian American Studie
Width-parameterized SAT: time-space tradeoffs,
No full textAlekhnovich and Razborov (2002) presented an algorithm that solves SAT on instances ϕ of size n and tree-width TW(ϕ), using time and space bounded by 2O(TW(ϕ))nO(1). Although several follow-up works appeared over the last decade, the first open question of Alekhnovich and Razborov remained essentially unresolved: Can one check satisfiability of formulas with small tree-width in polynomial space and time as above? We essentially resolve this question, by (1) giving a polynomial space algorithm with a slightly worse run-time, (2) providing a complexity-theoretic characterization of bounded tree-width SAT, which strongly suggests that no polynomial-space algorithm can run significantly faster, and (3) presenting a spectrum of algorithms trading off time for space, between our PSPACE algorithm and the fastest known algorithm.
First, we give a simple algorithm that runs in polynomial space and achieves run-time 3TW(ϕ)lognnO(1), which approaches the run-time of Alekhnovich and Razborov (2002), but has an additional log n factor in the exponent. Then, we conjecture that this annoying log n factor is in general unavoidable.
Our negative results show our conjecture true if one believes a well-known complexity assumption, which is the SC ≠ NC conjecture and its scaled variants. Technically, we base our result on the following lemma. For arbitrary k, SAT of tree-width logkn is complete for the class of problems computed by circuits of logarithmic depth, semi-unbounded fan-in and size 2O(logkn) (SAC1 when k=1). Problems in this class can be solved simultaneously in time-space (2O(logk+1n),O(logk+1n)), and also in (2O(logkn), 2O(logkn)). Then, we show that our conjecture (for SAT instances with poly-log tree-width) is equivalent to the question of whether the small-space simulation of semi-unbounded circuit classes can be sped up without incurring a large space penalty. This is a recasting of the conjecture that SAC1 (and even its subclass NL) is not contained in SC.
Although we cannot hope for an improvement asymptotically in the exponent of time and space, we introduce a new algorithmic technique which trades constants in the exponents: for each ε with 0<ε<1, we give an algorithm in time-space
(31.441(1−ε)TW(ϕ)log|ϕ||ϕ|O(1),22εTW(ϕ)|ϕ|O(1)).
We systematically study the limitations of our technique for trading off time and space, and we show that our bounds are the best achievable using this technique.Licensed under a Creative Commons Attribution License (CC-BY) http://creativecommons.org/licenses/by/3.0/Peer reviewe
Review of \u3cem\u3eUnsettled: Cambodian Refugees in the New York City Hyperghetto\u3c/em\u3e. Eric Tang. Reviewed by Robert Forrant
No full textEric Tang, Unsettled: Cambodian Refugees in the New York City Hyperghetto. Temple University Press, (2015), 220 pages, 70 (hardcover)
Tang Code, Tang Rite, and Other Manuscripts of Tang Dynasty
No full textIn the present paper, the author gives the preliminary reports on three newly found Tang 唐 official documents, pointing out their important value, and offering the all texts for further studies.1. In Tunhuang and Turfan Documents concerning Social and Economic History I. Legal Texts (Tokyo 1978-1980), Professors T. Yamamoto, O. Ikeda, and M. Okano published the joined texts of O. 5098 and O. 8099 from Otani collection. They identified the fragments with the Section on Violence and Robbery of the Tang Code (唐律), and pointed out the article comes from the Yonghui 永徽 or Chuigong 垂拱 Code according to the Zetian 則天 characters used in the Buddhist text on the verso. The author joins another fragment based on an old photograph of the Turfan document preserved in the Lüshun Museum (旅順博物館). The new text contains one different article from the printed text after the Song 宋 dynasty.2. Among the Dunhuang 敦煌 manuscripts in the National Library of China in Beijing, there is a good copy of the Tang Rite (唐礼) in high Tang characters (No. zhou 周 70A). It contains the text corresponding to the Da Tang Kaiyuan li 大唐開元礼, vol. 37: “Huangdi shixiang yu Taimiao 皇帝時享於太廟”. It is the first time to find the book in Dunhuang or Turfan manuscripts.3. In his Dunhuang Turfan Tangdai fazhi wenshu kaoshi 敦煌吐魯番唐代法制文書考釈, Liu Junwen thought the document of zhou 51 should be the Regulations of the Regional Military Organization. But the form of the original document could not conform to the Tang Regulations, so the author refutes his view and thinks that it is an official document relating to the beacon of the military fortress in the area of Dunhuang or Turfan.journal articl
Tang O 1950-1954
No full textA report on the village of Tang O, detailing its location, the current projects there, and the resources available
Sogdian merchants and Chinese Han merchants during the Tang Dynasty
No full textÉtienne de La Vaissière, Eric Trombert ed., Les Sogdiens en Chine (Études thématiques, 17), Paris: École française d'Extrême-Orient, 2005.The establishment of the Tang Empire brought the commercial activities of Sogdian merchants to a new height, because that their commercial activities was reinforced by the communication system running all over the Tang Empire's territory and the "dian" shops set along the main post roads. The communicational condition mentioned above enabled Sogdians to complete long-distance joumeys, allowing speed and safe communication and transportation. And Chinese Han merchants in the Tang Empire, along with Sogdian merchants, expanded their commercial activities on a wide scale, encompassing Central Asia
Reinventing the Pre-Tang Tradition: Compiling and Publishing Pre-Tang Poetry Anthologies in Sixteenth-Century China
No full textAbstract
This article examines how the making of pre-Tang poetry anthologies in sixteenth-century Ming China led to a reinvention of the pre-Tang poetic tradition. From the Zhengde period 正德 (1506–21) well into the Wanli reign 萬曆 (1573–1620), the compilation and publication of new pre-Tang poetry anthologies saw a dramatic increase, making the anthologizing practices in the 1500s crucial to understanding the pre-Tang tradition. Through a study of paratextual elements (book titles, tables of contents, prefaces, postscripts, etc.) in twenty-two pre-Tang poetry anthologies compiled in the 1500s, this article identifies three types of anthologizing practices. By employing quantitative and network analysis, the author hopes to historicize these practices, investigate the motivations for the anthologies, and explore their citation networks. These anthologizing practices, I conclude, gradually transformed the classification principles of previous anthologies, expanded the scope of canonized anthologies, and established a distinct pre-Tang tradition by the end of the sixteenth century.</jats:p
View of exterior facade Kuomintang Club building, Little Bourke Street, Melbourne, Victoria, 1 [picture].
No full textPart of the collection: Eric Milton Nicholls collection.; Title from acquisitions documentation.; "951"--Stamped on verso.; Condition: Good.; W.B.G. facade design.; Source for dating, Beyond Architecture, p. 110.; Photograph probably taken by Walter Burley Griffin and Marion Mahony Griffin.; "Chinese Nationalist Party, Kuo Min Tang"--Sign in Chinese on facade of building.; Also available in electronic version via the Internet at: http://nla.gov.au/nla.pic-vn3603884a-s681; Purchased from Marie and Glynn Nicholls, 2006.; Eric Milton Nicholls papers ; located at; National Library of Australia Manuscript collection MS 9957.; Vernon inventory, Pt.III Box 3 bb
- …
