On the Parameterized Complexity of Learning First-Order Logic

Summary: Establishes parameterized complexity bounds for learning first-order queries: proves learning is at least as hard as FO model-checking, yielding AW[*]-hardness on general structures. Gives an FPT agnostic PAC algorithm for FO learning over nowhere-dense (sparse) data. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1845
Venue: PODS
Year: 2022
Pagerank: 4.1945683e-05
Overall Rank: 11,323 | 21.23%
DOI: 10.1145/3517804.3524151

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,124	Characterizing Schema Mappings via Data Examples	2010	PODS	9.4912951e-05
2,750	Learning and Verifying Quantified Boolean Queries by Example	2013	PODS	8.176296e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
11,556	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	4.1945683e-05
3,065	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.6230903e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
7,739	Symmetric Weighted First-Order Model Counting	2015	PODS	4.663547e-05
7,063	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	4.8461152e-05
12,031	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1945683e-05
6,239	The Parameterized Complexity of Database Queries	2001	PODS	5.1417208e-05