| 1. |
- Atserias, Albert, et al.
(författare)
-
Clique Is Hard on Average for Regular Resolution
- 2021
-
Ingår i: Journal of the ACM. - : Association for Computing Machinery (ACM). - 0004-5411 .- 1557-735X. ; 68:4, s. 1-26
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that for k ≫; 4√n regular resolution requires length nω(k) to establish that an ErdÅ's-Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional nω(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
|
|
| 2. |
- Berkholz, Christoph, et al.
(författare)
-
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
- 2023
-
Ingår i: Journal of the ACM. - 0004-5411. ; 70:5
-
Tidskriftsartikel (refereegranskat)abstract
- We prove near-optimal tradeoffs for quantifier depth (also called quantifier rank) versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least nω (k/log k). Our tradeoffs also apply to first-order counting logic and, by the known connection to the k-dimensional Weisfeiler-Leman algorithm, imply near-optimal lower bounds on the number of refinement iterations.A key component in our proof is the hardness condensation technique introduced by Razborov in the context of proof complexity. We apply this method to reduce the domain size of relational structures while maintaining the minimal quantifier depth needed to distinguish them in finite variable logics.
|
|
| 3. |
- Chatzipanagiotou, Marita, et al.
(författare)
-
Automated recognition of geographical named entities in titles of Ukiyo-e prints
- 2021
-
Ingår i: Journal of the ACM / Association for Computing Machinery. - New York, NY, USA : ACM. - 0004-5411. ; , s. 70-77
-
Tidskriftsartikel (refereegranskat)abstract
- This paper investigates the application of Natural Language Processing as a means to study the relationship between topography and its visual renderings in early modern Japanese ukiyo-e landscape prints. We introduce a new dataset with titles of landscape prints that have been annotated by an art historian for any included place-names. The prints are hosted by the digital database of the Art Research Center at the Ritsumeikan University, Kyoto, one of the hubs of Digital Humanities in Japan. By applying, calibrating and assessing a Named Entity Recognition (NER) tool, we argue that ‘distant viewing’ or macroanalysis of visual datasets can be facilitated, which is needed to assist art historical studies of this rich, complex and diverse research material. Experimental results indicated that the performance of NER can be improved by 30% and reach 50% precision, by using part of the introduced dataset.
|
|
| 4. |
- Håstad, Johan, 1960-
(författare)
-
On Small-depth Frege Proofs for Tseitin for Grids
- 2021
-
Ingår i: Journal of the ACM. - : Association for Computing Machinery (ACM). - 0004-5411 .- 1557-735X. ; 68:1
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that a small-depth Frege refutation of the Tseitin contradiction on the grid requires subexponential size. We conclude that polynomial size Frege refutations of the Tseitin contradiction must use formulas of almost logarithmic depth.
|
|
