1,249 research outputs found
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
No full textResolution over linear equations is a natural extension of the popular resolution refutation system, augmented with the ability to carry out basic counting. Denoted Res(lin_R), this refutation system operates with disjunctions of linear equations with boolean variables over a ring R, to refute unsatisfiable sets of such disjunctions. Beginning in the work of [Ran Raz and Iddo Tzameret, 2008], through the work of [Dmitry Itsykson and Dmitry Sokolov, 2014] which focused on tree-like lower bounds, this refutation system was shown to be fairly strong. Subsequent work (cf. [Jan Krajícek, 2017; Dmitry Itsykson and Dmitry Sokolov, 2014; Jan Krajícek and Igor Carboni Oliveira, 2018; Michal Garlik and Lezsek Kołodziejczyk, 2018]) made it evident that establishing lower bounds against general Res(lin_R) refutations is a challenging and interesting task since the system captures a "minimal" extension of resolution with counting gates for which no super-polynomial lower bounds are known to date.
We provide the first super-polynomial size lower bounds on general (dag-like) resolution over linear equations refutations in the large characteristic regime. In particular we prove that the subset-sum principle 1+ x_1 + ̇s +2^n x_n = 0 requires refutations of exponential-size over ℚ. Our proof technique is nontrivial and novel: roughly speaking, we show that under certain conditions every refutation of a subset-sum instance f=0, where f is a linear polynomial over ℚ, must pass through a fat clause containing an equation f=α for each α in the image of f under boolean assignments. We develop a somewhat different approach to prove exponential lower bounds against tree-like refutations of any subset-sum instance that depends on n variables, hence also separating tree-like from dag-like refutations over the rationals.
We then turn to the finite fields regime, showing that the work of Itsykson and Sokolov [Dmitry Itsykson and Dmitry Sokolov, 2014] who obtained tree-like lower bounds over ?_2 can be carried over and extended to every finite field. We establish new lower bounds and separations as follows: (i) for every pair of distinct primes p,q, there exist CNF formulas with short tree-like refutations in Res(lin_{?_p}) that require exponential-size tree-like Res(lin_{?_q}) refutations; (ii) random k-CNF formulas require exponential-size tree-like Res(lin_{?_p}) refutations, for every prime p and constant k; and (iii) exponential-size lower bounds for tree-like Res(lin_?) refutations of the pigeonhole principle, for every field ?
Replication data for: Text analysis of public comments to reveal alternative understandings of fracking and their distribution along proximity to proposed development
No full textReplication data for "Text analysis of public comments to reveal alternative understandings of fracking and their distribution along proximity to proposed development." Dokshin, Fedor. Nature Energy. Files include processed, de-identified datasets and R code, which permit replication of the figures reported in the paper. The original public comments data are part of the public record and available freely from the New York State Department of Environmental Conservation through a public records request (https://www.dec.ny.gov/public/373.html). Because the full records include personally identifiable information (names, addresses, and emails), they are not shared here. Comment data that exclude personal identifiers are however available from the author upon reasonable request for replication and research purposes
[Abstract composition].
No full textAbstract composition of small dashes in subdued tones of blues, browns, and yellows.Edourd RoditiFedor Ganz was a writer and a painter, born in Hamburg in 1910, raised in Geneva, Switzerland, and educated in France at the Sorbonne. From the 1930s until his death in 1983, Ganz was active both politically and artistically, exhibiting his artwork (mostly paintings) and publishing poetry and political essays in Spanish, French, and German. He lived a relatively itinerant lifestyle, and from his university days onwards traveled extensively between South America, Europe, and North America. At least part of the reason for this extensive travel may be traced to translation work which he performed for the United Nations and other diplomatic and cultural organizations. His Ensayo marxista de la historia de Espana (Marxist essay on the history of Spain), first published in 1934, won favorable notices, and Nobel Prize winner Gabriela Mistral wrote the preface to one of his volumes of poetry. During the 1960s he reclaimed German citizenship. Fedor Ganz died in Paris in December 1983.Updated recordDigital imag
Fedor Ganz Collection 1870-1984
No full textThe collection contains documents, correspondence, unpublished writings, sketches, photos, and various flyers, postcards, posters, and similar printed materials advertising artistic, literary, and political exhibitions, events, and happenings. A substantial amount of family documents are also included; some of these may have been amassed for research into a larger literary work entitled 'Inventar vor dem Brand' which was loosely inspired by the life of Fedor Ganz's mother, Elsbeth Klemperer. This work was still incomplete at the time of his death, but a large manuscript draft is present in the collection. The extended family documents also include handbills for operas and theatrical works performed in 1870. Finally, the collection contains some political flyers and postcards dating to the era of World War I.Writer, painter, born Hamburg, 1910; raised in Geneva, Switzerland; studied in France, Sorbonne. From the 1930s until his death in 1983, Ganz was active both politically and artistically, exhibiting his artwork (mostly paintings) and publishing poetry and political essays in Spanish, French, and German. He lived a relatively itinerant lifestyle, and from his university days onwards traveled extensively between South America, Europe, and North America. At least part of the reason for this extensive travel may be traced to translation work which he performed for the United Nations and other diplomatic and cultural organizations. His 'Ensayo marxista de la historia de Espana' ('Marxist essay on the history of Spain'), first published in 1934, won favorable notices, and Nobel Prize winner Gabriela Mistral wrote the preface to one of his volumes of poetry. As a young man in Paris he entered Surrealist and Dadaist literary circles, and he also exhibited his paintings throughout his life. During the 1960s he reclaimed German citizenship, and he died in December 1983.An inventory is available in folder 1, with an account of Ganz's death and the circumstances of donationFinding available online.digitize
Recommended from our members
Fedor Bucholtz, mycologist and his herbarium
No full textBeginning shortly after the death of Fedor Bucholtz in 1924 correspondence was initiated by Roland Thaxter with Alexander Bucholz, mycologist Fedor Bucholtz’s son, concerning the purchase of his father’s herbarium and library. This began an exchange that lasted for six years and resulted in the purchase of the library and part of the herbarium of Fedor Bucholtz for the Farlow Reference Library and Herbarium of Cryptogamic Botany. About 5200 specimens and about 800 books and reprints were received. These purchases are documented through correspondence, which also throws light on the difficulties Bucholtz and his family endured in the wake of World War 1.Organismic and Evolutionary BiologyVersion of Recor
Fedor Bucholtz, mycologist and his herbarium
No full textBeginning shortly after the death of Fedor Bucholtz in 1924 correspondence was initiated by Roland Thaxter with Alexander Bucholz, mycologist Fedor Bucholtz’s son, concerning the purchase of his father’s herbarium and library. This began an exchange that lasted for six years and resulted in the purchase of the library and part of the herbarium of Fedor Bucholtz for the Farlow Reference Library and Herbarium of Cryptogamic Botany. About 5200 specimens and about 800 books and reprints were received. These purchases are documented through correspondence, which also throws light on the difficulties Bucholtz and his family endured in the wake of World War 1.
Memory, Kinship and the Mobilization of the Dead: The Russian State and the "Immortal Regiment" Movement
No full textThis chapter examines a new addition to the repertoire of Victory Day commemorative traditions in post-Soviet space: the newly invented annual “Immortal Regiment” parade, in which people march bearing photographs of their ancestors who fought in the Great Patriotic War of 1941–45. The chapter focuses on attempts by the state authorities and their supporters to instrumentalize the new ritual and to appropriate the Red Army’s war dead, and the emotions they evoke. It explores the ways in which the figure of the dead Red Army soldier is being brought back to life in new ways as part of the current regime’s authoritarian project
Hydrolutos breweri Derka & Fedor, sp. nov.
No full textHydrolutos breweri Derka & Fedor sp. nov. Description. Male. Colour and markings: Body dark brown. Head capsule, including mandibles, dark brown with a bright belt-like pattern on vertex and 3 bright spots triangularly situated on frons, shiny and almost smooth, eyes black. Palpi light basally and distally, with dark middle section. Thorax and abdomen very dark brown dorsally, with light bands on terga (light area on pronotum). Legs brighter than body (Fig. 2, 3). Head: Antennal flagellum about 2.5 times total body length, proximally smooth, in middle and distal section swollen and covered by short fine microsetae. Fastigium as broad as antennal segment S 1, horizontal, slightly flattened, not declinate, with a median carina. Vertex convex, clypeus subtriangular with indistinct median carina. Labrum heart-shaped, proximally broader than distally, with median carina in its apical half. Maxillary palps bright, the last segment swollen and covered by short fine and soft microsetae. Eyes elevated in frontal view (Fig. 4). Thorax: Pronotum slightly elevated over mesonotum, as long as wide, bordered by a smooth rolled margin, containing both smooth and gently rugose areas. All thoracic sterna with 2 spines, prosternum: 2 moderate spines posterolaterally elevated, mesosternum: 2 spines posterolaterally elevated, metasternum: 2 distinct spines with no lateral elevation (Fig. 2, 3). Legs long, forecoxa with a moderate lateral spine, midcoxa with a short blunt spine, femora without spines. Fore tibiae dorsally with 2 spines subapically and 2 apically, ventrally with 2 rows of 5 spines (including the apical ones). Middle tibiae dorsally with a row of 4 spines on internal side and a row of 3 spines on external side, ventrally with 2 rows of 5 spines. Hind tibiae with 2 lateral combs of short but firm spines, ventrally with 2 moderate subterminal and 2 superior terminal spines. Tympanum elypsoid, dark brown. Abdomen: Abdominal apex and genitalia as on Figures 5, 6, 7. Abdominal tergites smooth with fine transverse striae mesally and with posterior edges darker. Genitalia pubescent. Supra-anal plate bilobulate terminally slightly curved upwards. Cerci cylindrical, rugose, directed gently upwards, with blunt apices and without internal processes. Subgenital plate as long as wide, very gently concave laterally, without any emargination between styles, with flat posterior margin and long styli directed ventrad. Measurements. Body length 43.2 mm (including cerci 47.1), fastigium width 1.2 mm, interocular space 5 mm, pronotum length 9.9 mm, width 11.1 mm, hind femur length 35.5, width (7 mm max.), (2 mm min.), hind tibia length 35.5 mm, hind tarsus length 11.3 mm, hind tarsi length: I 4.1 mm, II 3.0 mm, III 2.1 mm, IV 1.5 mm, abdomen length (without cerci) 22.4 mm. Female. Unknown. Material examined. Holotype. 1 ɗ body length 43.2 mm, Venezuela, Edo. Bolívar, Chimantá Massif, Churí tepui, Cueva Charles Brewer, ca 2300 m a.s.l., 15.I. 2009. Holotype has been preserved dry and pinned. Paratypes. ɗ body length 43 mm, 1 Ψ nymph, body length 30 mm. The same data as holotype. The paratypes are stored in 70 % ethanol. Holotype and paratypes will be deposited in Museo del Instituto de Zoología Agrícola (MIZA), Facultad de Agronomía, Universidad Central de Venezuela, Maracay, Edo. Aragua, Venezuela. Etymology. Species named in honour of Charles Brewer-Carías, in recognition of his great contribution to exploration of Venezuelan Guyana. He has led over 200 expeditions in Venezuelan Guyana Highlands. His most famous discoveries are in geological features in the tepuis such as the giant sink holes on Sarisariñama, the world’s largest quartzite cave on Churí-tepui and many other previously unexplored caves. Ecology. As other members of the genus, H. breweri inhabits aquatic habitats. Numerous individuals were observed walking and swimming inside the stream and walking outside the water at the bottom and walls of the Cueva Charles Brewer (Fig. 8). Thanks to high ability to cling by means of strong legs and tarsal claws it is able to move even against strong current. Because of permanent darkness in the cave, individuals were observed active 24 hours, not only during the night as it was reported for other members of the genus (Issa & Iaffe 1999, pers. observ.). However, it can not be considered troglobiont because of lack of typical adaptations (e.g. reduction of eyes and coloration), and the occurrence of this species can be expected in other streams at Churí-tepui plateau outside the Cueva Charles Brewer. Diagnosis. The species is easily distinguished on a few characters. Clypeus triangular (subtriangular in H. chimantea), laterally more distinct than in H. ayuan. Palpi bright but dark in H. aracamuni. Labrum heartshaped, but oval in H. raraimae and H. auyan. Fastigium as broad as antennal segment I, but broader in H. roraimae and H. aracamuni. Epiproct bilobulate terminally, but oval in H. aracamuni. H. breweri is unique among other members of the genus by extremely long hind tibiae reaching length of hind femur. In remnant Hydrolutos species hind femur is always longer then hind tibia.Published as part of Derka, Tomáš & Fedor, Peter, 2010, Hydrolutos breweri sp. n., a new aquatic Lutosini species (Orthoptera: Anostostomatidae) from Churí-tepui (Chimantá Massif, Venezuela), pp. 51-59 in Zootaxa 2653 on pages 53-58, DOI: 10.5281/zenodo.27620
Graph Decompositions and Algorithms (Invited Talk)
No full textWe overview the recent progress in solving intractable optimization problems on planar graphs as well as other classes of sparse graphs. In particular, we discuss how tools from Graph Minors theory can be used to obtain:
* subexponential parameterized algorithms
* approximation algorithms, and
* preprocessing and kernelization algorithms
on these classes of graphs
Kernelization of Whitney Switches
No full textA fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney’s theorem: Given 2-isomorphic graphs, can we transform one into another by applying at most k Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size (k), and thus, is fixed-parameter tractable when parameterized by k
- …
