832 lines
27 KiB
BibTeX
832 lines
27 KiB
BibTeX
@inproceedings{10.1109/FOCS.2014.22,
|
||
author = {Curticapean, Radu and Marx, D\'{a}niel},
|
||
title = {Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts},
|
||
year = {2014},
|
||
isbn = {9781479965175},
|
||
publisher = {IEEE Computer Society},
|
||
address = {USA},
|
||
url = {https://doi.org/10.1109/FOCS.2014.22},
|
||
doi = {10.1109/FOCS.2014.22},
|
||
abstract = {For a class C of graphs, #Sub(C) is the counting problem that, given a graph H from C and an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that if C has bounded vertex-cover number (equivalently, the size of the maximum matching in C is bounded), then #Sub(C) is polynomial-time solvable. We complement this result with a corresponding lower bound: if C is any recursively enumerable class of graphs with unbounded vertex-cover number, then #Sub(C) is #W[1]-hard parameterized by the size of H and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT is equal to #W[1]. As a first step of the proof, we show that counting k-matchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting k-matchings in general graphs, our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no f(k)*no(k/log(k)) time algorithm for counting k-matchings in bipartite graphs for any computable function f. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length k is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.},
|
||
booktitle = {Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science},
|
||
pages = {130–139},
|
||
numpages = {10},
|
||
series = {FOCS '14}
|
||
}
|
||
@misc{https://doi.org/10.48550/arxiv.2201.11524,
|
||
doi = {10.48550/ARXIV.2201.11524},
|
||
url = {https://arxiv.org/abs/2201.11524},
|
||
author = {Grohe, Martin and Lindner, Peter and Standke, Christoph},
|
||
keywords = {Databases (cs.DB), FOS: Computer and information sciences, FOS: Computer and information sciences},
|
||
title = {Probabilistic Query Evaluation with Bag Semantics},
|
||
publisher = {arXiv},
|
||
year = {2022},
|
||
copyright = {arXiv.org perpetual, non-exclusive license}
|
||
}
|
||
|
||
@INPROCEEDINGS{4497507,
|
||
author={Antova, Lyublena and Jansen, Thomas and Koch, Christoph and Olteanu, Dan},
|
||
booktitle={2008 IEEE 24th International Conference on Data Engineering},
|
||
title={Fast and Simple Relational Processing of Uncertain Data},
|
||
year={2008},
|
||
volume={},
|
||
number={},
|
||
pages={983-992},
|
||
doi={10.1109/ICDE.2008.4497507}}
|
||
|
||
@article{CHEN20061346,
|
||
title = {Strong computational lower bounds via parameterized complexity},
|
||
journal = {Journal of Computer and System Sciences},
|
||
volume = {72},
|
||
number = {8},
|
||
pages = {1346-1367},
|
||
year = {2006},
|
||
issn = {0022-0000},
|
||
doi = {https://doi.org/10.1016/j.jcss.2006.04.007},
|
||
url = {https://www.sciencedirect.com/science/article/pii/S0022000006000675},
|
||
author = {Jianer Chen and Xiuzhen Huang and Iyad A. Kanj and Ge Xia},
|
||
keywords = {Parameterized computation, Computational complexity, Lower bound, Clique, Polynomial time approximation scheme},
|
||
abstract = {We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/ϵ)no(1/ϵ) for any function f unless an unlikely collapse occurs in parameterized complexity theory.}
|
||
}
|
||
@inproceedings{10.5555/645413.652181,
|
||
author = {Flum, J\"{o}rg and Grohe, Martin},
|
||
title = {The Parameterized Complexity of Counting Problems},
|
||
year = {2002},
|
||
isbn = {0769518222},
|
||
publisher = {IEEE Computer Society},
|
||
address = {USA},
|
||
abstract = {We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W[t], for t geqslant 1 , that corresponds to Downey and Fellows's W-hierarchy [12] and show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems.Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k , is#W[1]-complete. This makes it highly unlikely that any of these problems is fixed-parameter tractable, even though their decision versions are fixed-parameter tractable. More explicitly, our result shows that most likely there is no f(k) cdot n^c-algorithm for counting cycles or paths of length k in a graph of size n for any computable function f: mathbb{N} to mathbb{N} and constant c , even though there is a 2^{0(k)}cdot n^{2.376}algorithm for finding a cycle or path of length k [2].},
|
||
booktitle = {Proceedings of the 43rd Symposium on Foundations of Computer Science},
|
||
pages = {538},
|
||
series = {FOCS '02}
|
||
}
|
||
|
||
@misc{pdbench,
|
||
key = {pdbench utility},
|
||
title = "pdbench",
|
||
url = {http://pdbench.sourceforge.net/},
|
||
note = {Accessed: 2020-12-15},
|
||
year="2008"
|
||
}
|
||
|
||
@article{AF18,
|
||
author = {Arab, Bahareh and Feng, Su and Glavic, Boris and Lee, Seokki and Niu, Xing and Zeng, Qitian},
|
||
journal = {IEEE Data Eng. Bull.},
|
||
number = {1},
|
||
pages = {51--62},
|
||
title = {GProM - A Swiss Army Knife for Your Provenance Needs},
|
||
volume = {41},
|
||
year = {2018}
|
||
}
|
||
|
||
@inproceedings{10.1145/1265530.1265571,
|
||
author = {Dalvi, Nilesh and Suciu, Dan},
|
||
booktitle = {PODS},
|
||
numpages = {10},
|
||
pages = {293--302},
|
||
title = {The Dichotomy of Conjunctive Queries on Probabilistic Structures},
|
||
year = {2007}
|
||
}
|
||
|
||
@inproceedings{DBLP:conf/icde/OlteanuHK10,
|
||
author = {Dan Olteanu and
|
||
Jiewen Huang and
|
||
Christoph Koch},
|
||
booktitle = {ICDE},
|
||
pages = {145--156},
|
||
title = {Approximate confidence computation in probabilistic databases},
|
||
year = {2010}
|
||
}
|
||
|
||
@book{DBLP:series/synthesis/2011Suciu,
|
||
author = {Dan Suciu and
|
||
Dan Olteanu and
|
||
Christopher Ré and
|
||
Christoph Koch},
|
||
publisher = {Morgan \& Claypool Publishers},
|
||
title = {Probabilistic Databases},
|
||
year = {2011}
|
||
}
|
||
|
||
@inproceedings{feng:2019:sigmod:uncertainty,
|
||
author = {Feng, Su and Huber, Aaron and Glavic, Boris and Kennedy, Oliver},
|
||
booktitle = {SIGMOD},
|
||
title = {Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers},
|
||
year = {2019}
|
||
}
|
||
|
||
@article{FH12,
|
||
author = {Fink, Robert and Han, Larisa and Olteanu, Dan},
|
||
journal = {PVLDB},
|
||
number = {5},
|
||
pages = {490--501},
|
||
title = {Aggregation in probabilistic databases via knowledge compilation},
|
||
volume = {5},
|
||
year = {2012}
|
||
}
|
||
|
||
|
||
|
||
@inproceedings{DBLP:conf/tapp/Zavodny11,
|
||
author = {Jakub Závodný},
|
||
booktitle = {TaPP},
|
||
title = {On Factorisation of Provenance Polynomials},
|
||
year = {2011}
|
||
}
|
||
|
||
|
||
@inproceedings{kennedy:2010:icde:pip,
|
||
author = {Kennedy, Oliver and Koch, Christoph},
|
||
booktitle = {ICDE},
|
||
title = {PIP: A Database System for Great and Small Expectations},
|
||
year = {2010}
|
||
}
|
||
|
||
@inproceedings{DBLP:conf/icde/AntovaKO07a,
|
||
author = {Lyublena Antova and
|
||
Christoph Koch and
|
||
Dan Olteanu},
|
||
booktitle = {ICDE},
|
||
title = {MayBMS: Managing Incomplete Information with Probabilistic World-Set
|
||
Decompositions},
|
||
year = {2007}
|
||
}
|
||
|
||
@inproceedings{DBLP:conf/pods/KhamisNR16,
|
||
author = {Mahmoud Abo Khamis and
|
||
Hung Q. Ngo and
|
||
Atri Rudra},
|
||
booktitle = {PODS},
|
||
pages = {13--28},
|
||
title = {FAQ: Questions Asked Frequently},
|
||
year = {2016}
|
||
}
|
||
|
||
@article{DBLP:journals/sigmod/GuagliardoL17,
|
||
author = {Paolo Guagliardo and
|
||
Leonid Libkin},
|
||
journal = {SIGMOD Rec.},
|
||
number = {3},
|
||
pages = {5--16},
|
||
title = {Correctness of SQL Queries on Databases with Nulls},
|
||
volume = {46},
|
||
year = {2017}
|
||
}
|
||
|
||
@inproceedings{DBLP:conf/vldb/AgrawalBSHNSW06,
|
||
author = {Parag Agrawal and
|
||
Omar Benjelloun and
|
||
Anish Das Sarma and
|
||
Chris Hayworth and
|
||
Shubha U. Nabar and
|
||
Tomoe Sugihara and
|
||
Jennifer Widom},
|
||
booktitle = {VLDB},
|
||
pages = {1151--1154},
|
||
title = {Trio: A System for Data, Uncertainty, and Lineage},
|
||
year = {2006}
|
||
}
|
||
|
||
@inproceedings{k-match,
|
||
author = {Radu Curticapean},
|
||
booktitle = {ICALP},
|
||
pages = {352--363},
|
||
title = {Counting Matchings of Size k Is W[1]-Hard},
|
||
volume = {7965},
|
||
year = {2013}
|
||
}
|
||
|
||
|
||
@inproceedings{DBLP:conf/sigmod/SinghMMPHS08,
|
||
author = {Sarvjeet Singh and
|
||
Chris Mayfield and
|
||
Sagar Mittal and
|
||
Sunil Prabhakar and
|
||
Susanne E. Hambrusch and
|
||
Rahul Shah},
|
||
booktitle = {SIGMOD},
|
||
pages = {1239--1242},
|
||
title = {Orion 2.0: native support for uncertain data},
|
||
year = {2008}
|
||
}
|
||
|
||
@inproceedings{DBLP:conf/pods/GreenKT07,
|
||
author = {Todd J. Green and
|
||
Gregory Karvounarakis and
|
||
Val Tannen},
|
||
booktitle = {PODS},
|
||
pages = {31--40},
|
||
title = {Provenance semirings},
|
||
year = {2007}
|
||
}
|
||
|
||
|
||
@inproceedings{ngo-survey,
|
||
author = {Hung Q. Ngo},
|
||
booktitle = {PODS},
|
||
title = {Worst-Case Optimal Join Algorithms: Techniques, Results, and Open
|
||
Problems},
|
||
year = {2018}
|
||
}
|
||
|
||
|
||
|
||
@article{skew,
|
||
author = {Hung Q. Ngo and
|
||
Christopher Ré and
|
||
Atri Rudra},
|
||
journal = {SIGMOD Rec.},
|
||
number = {4},
|
||
pages = {5--16},
|
||
title = {Skew strikes back: new developments in the theory of join algorithms},
|
||
volume = {42},
|
||
year = {2013}
|
||
}
|
||
|
||
@article{NPRR,
|
||
author = {Hung Q. Ngo and
|
||
Ely Porat and
|
||
Christopher Ré and
|
||
Atri Rudra},
|
||
journal = {J. ACM},
|
||
number = {3},
|
||
pages = {16:1--16:40},
|
||
title = {Worst-case Optimal Join Algorithms},
|
||
volume = {65},
|
||
year = {2018}
|
||
}
|
||
|
||
@book{arith-complexity,
|
||
author = {Peter Bürgisser and
|
||
Michael Clausen and
|
||
Mohammad Amin Shokrollahi},
|
||
publisher = {Springer},
|
||
title = {Algebraic complexity theory},
|
||
volume = {315},
|
||
year = {1997}
|
||
}
|
||
|
||
@inproceedings{triang-hard,
|
||
author = {Tsvi Kopelowitz and
|
||
Virginia Vassilevska Williams},
|
||
booktitle = {ICALP},
|
||
pages = {74:1--74:16},
|
||
title = {Towards Optimal Set-Disjointness and Set-Intersection Data Structures},
|
||
volume = {168},
|
||
year = {2020}
|
||
}
|
||
|
||
@article{LL97,
|
||
author = {Lakshmanan, L.V.S. and Leone, N. and Ross, R. and Subrahmanian, VS},
|
||
journal = {TODS},
|
||
number = {3},
|
||
pages = {419--469},
|
||
title = {Probview: A flexible probabilistic database system},
|
||
volume = {22},
|
||
year = {1997}
|
||
}
|
||
|
||
@article{jha-13-kcmdt,
|
||
author = {Jha, Abhay and Suciu, Dan},
|
||
title = {Knowledge Compilation Meets Database Theory: Compiling Queries
|
||
To Decision Diagrams},
|
||
journal = {Theory of Computing Systems},
|
||
volume = 52,
|
||
number = 3,
|
||
pages = {403--440},
|
||
year = 2013,
|
||
publisher = {Springer},
|
||
}
|
||
@inproceedings{BS06,
|
||
author = {Omar Benjelloun and Anish Das Sarma and Alon Y. Halevy and Jennifer Widom},
|
||
booktitle = {VLDB},
|
||
pages = {953--964},
|
||
title = {ULDBs: Databases with Uncertainty and Lineage},
|
||
year = {2006}
|
||
}
|
||
|
||
@conference{RS07,
|
||
author = {Ré, C. and Suciu, D.},
|
||
booktitle = {VLDB},
|
||
pages = {51--62},
|
||
title = {Materialized views in probabilistic databases: for information exchange and query optimization},
|
||
year = {2007}
|
||
}
|
||
|
||
|
||
|
||
@article{VS17,
|
||
Author = {Van den Broeck, Guy and Suciu, Dan},
|
||
Title = {Query Processing on Probabilistic Data: A Survey},
|
||
Year = {2017},
|
||
}
|
||
|
||
@incollection{GT06,
|
||
author = {Green, Todd J and Tannen, Val},
|
||
booktitle = {EDBT},
|
||
pages = {278--296},
|
||
title = {Models for incomplete and probabilistic information},
|
||
year = {2006}
|
||
}
|
||
|
||
@article{IL84a,
|
||
author = {Imieli\'nski, Tomasz and Lipski Jr, Witold},
|
||
journal = {JACM},
|
||
number = {4},
|
||
pages = {761--791},
|
||
title = {Incomplete Information in Relational Databases},
|
||
volume = {31},
|
||
year = {1984}
|
||
}
|
||
|
||
@article{DS12,
|
||
author = {Dalvi, Nilesh and Suciu, Dan},
|
||
journal = {JACM},
|
||
number = {6},
|
||
pages = {30},
|
||
title = {The dichotomy of probabilistic inference for unions of conjunctive queries},
|
||
volume = {59},
|
||
year = {2012}
|
||
}
|
||
|
||
|
||
@inproceedings{heuvel-19-anappdsd,
|
||
author = {Maarten Van den Heuvel and Peter Ivanov and Wolfgang Gatterbauer and Floris Geerts and Martin Theobald},
|
||
booktitle = {SIGMOD},
|
||
pages = {1295--1312},
|
||
title = {Anytime Approximation in Probabilistic Databases via Scaled Dissociations},
|
||
year = {2019}
|
||
}
|
||
|
||
|
||
@article{AB15,
|
||
author = {Amarilli, Antoine and Bourhis, Pierre and Senellart, Pierre},
|
||
journal = {PODS},
|
||
title = {Probabilities and provenance via tree decompositions},
|
||
year = {2015}
|
||
}
|
||
|
||
|
||
@inproceedings{OH09a,
|
||
author = {Olteanu, Dan and Huang, Jiewen},
|
||
booktitle = {SIGMOD},
|
||
pages = {389--402},
|
||
title = {Secondary-storage confidence computation for conjunctive queries with inequalities},
|
||
year = {2009}
|
||
}
|
||
|
||
@article{FO16,
|
||
author = {Robert Fink and Dan Olteanu},
|
||
journal = {TODS},
|
||
number = {1},
|
||
pages = {4:1--4:47},
|
||
title = {Dichotomies for Queries with Negation in Probabilistic Databases},
|
||
volume = {41},
|
||
year = {2016}
|
||
}
|
||
|
||
@article{FH13,
|
||
author = {Robert Fink and Jiewen Huang and Dan Olteanu},
|
||
journal = {VLDBJ},
|
||
number = {6},
|
||
pages = {823--848},
|
||
title = {Anytime approximation in probabilistic databases},
|
||
volume = {22},
|
||
year = {2013}
|
||
}
|
||
|
||
@inproceedings{AB15c,
|
||
author = {Antoine Amarilli and Pierre Bourhis and Pierre Senellart},
|
||
booktitle = {ICALP},
|
||
pages = {56--68},
|
||
title = {Provenance Circuits for Trees and Treelike Instances},
|
||
year = {2015}
|
||
}
|
||
|
||
@inproceedings{kenig-13-nclexpdc,
|
||
author = {Batya Kenig and Avigdor Gal and Ofer Strichman},
|
||
booktitle = {SUM},
|
||
pages = {219--232},
|
||
title = {A New Class of Lineage Expressions over Probabilistic Databases Computable in P-Time},
|
||
volume = {8078},
|
||
year = {2013}
|
||
}
|
||
|
||
@inproceedings{cavallo-87-tpd,
|
||
author = {Roger Cavallo and Michael Pittarelli},
|
||
booktitle = {VLDB},
|
||
pages = {71--81},
|
||
title = {The Theory of Probabilistic Databases},
|
||
year = {1987}
|
||
}
|
||
|
||
@inproceedings{roy-11-f,
|
||
author = {Sudeepa Roy and Vittorio Perduca and Val Tannen},
|
||
booktitle = {ICDT},
|
||
title = {Faster query answering in probabilistic databases using read-once functions},
|
||
year = {2011}
|
||
}
|
||
|
||
@article{sen-10-ronfqevpd,
|
||
author = {Prithviraj Sen and Amol Deshpande and Lise Getoor},
|
||
journal = {PVLDB},
|
||
number = {1},
|
||
pages = {1068--1079},
|
||
title = {Read-Once Functions and Query Evaluation in Probabilistic Databases},
|
||
volume = {3},
|
||
year = {2010}
|
||
}
|
||
@article{provan-83-ccccptg,
|
||
author = {J. Scott Provan and Michael O. Ball},
|
||
journal = {SIAM J. Comput.},
|
||
number = {4},
|
||
pages = {777--788},
|
||
title = {The Complexity of Counting Cuts and of Computing the Probability That a Graph Is Connected},
|
||
volume = {12},
|
||
year = {1983}
|
||
}
|
||
|
||
@article{valiant-79-cenrp,
|
||
author = {Leslie G. Valiant},
|
||
journal = {SIAM J. Comput.},
|
||
number = {3},
|
||
pages = {410--421},
|
||
title = {The Complexity of Enumeration and Reliability Problems},
|
||
volume = {8},
|
||
year = {1979}
|
||
}
|
||
|
||
@inproceedings{AD11d,
|
||
author = {Amsterdamer, Yael and Deutch, Daniel and Tannen, Val},
|
||
booktitle = {PODS},
|
||
pages = {153--164},
|
||
title = {Provenance for Aggregate Queries},
|
||
year = {2011}
|
||
}
|
||
|
||
|
||
|
||
@article{S18a,
|
||
author = {Senellart, Pierre},
|
||
journal = {SIGMOD Record},
|
||
number = {4},
|
||
pages = {5--15},
|
||
title = {Provenance and Probabilities in Relational Databases},
|
||
volume = {46},
|
||
year = {2018}
|
||
}
|
||
|
||
@article{RS09b,
|
||
author = {Christopher Ré and Dan Suciu},
|
||
journal = {VLDBJ},
|
||
number = {5},
|
||
pages = {1091--1116},
|
||
title = {The trichotomy of HAVING queries on a probabilistic database},
|
||
volume = {18},
|
||
year = {2009}
|
||
}
|
||
|
||
@article{gatterbauer-17-dpaplinws,
|
||
author = {Wolfgang Gatterbauer and Dan Suciu},
|
||
title = {Dissociation and Propagation for Approximate Lifted Inference
|
||
With Standard Relational Database Management Systems},
|
||
journal = {{VLDB} J.},
|
||
volume = 26,
|
||
number = 1,
|
||
pages = {5--30},
|
||
year = 2017
|
||
}
|
||
|
||
@inproceedings{fink-11,
|
||
author = {Robert Fink and Dan Olteanu},
|
||
booktitle = {ICDT},
|
||
pages = {174--185},
|
||
title = {On the optimal approximation of queries using tractable propositional languages},
|
||
year = {2011}
|
||
}
|
||
|
||
@article{jha-12-pdwm,
|
||
author = {Abhay Kumar Jha and Dan Suciu},
|
||
journal = {PVLDB},
|
||
number = {11},
|
||
pages = {1160--1171},
|
||
title = {Probabilistic Databases With Markoviews},
|
||
volume = {5},
|
||
year = {2012}
|
||
}
|
||
|
||
|
||
|
||
@conference{BD05,
|
||
author = {Boulos, J. and Dalvi, N. and Mandhani, B. and Mathur, S. and Re, C. and Suciu, D.},
|
||
booktitle = {SIGMOD},
|
||
title = {MYSTIQ: a system for finding more answers by using probabilities},
|
||
year = {2005}
|
||
}
|
||
|
||
@article{DS07,
|
||
author = {Dalvi, N. and Suciu, D.},
|
||
journal = {VLDB},
|
||
number = {4},
|
||
pages = {544},
|
||
title = {Efficient query evaluation on probabilistic databases},
|
||
volume = {16},
|
||
year = {2007}
|
||
}
|
||
|
||
@inproceedings{re-07-eftqevpd,
|
||
author = {Christopher Ré and Nilesh N. Dalvi and Dan Suciu},
|
||
booktitle = {ICDE},
|
||
pages = {886--895},
|
||
title = {Efficient Top-k Query Evaluation on Probabilistic Data},
|
||
year = {2007}
|
||
}
|
||
|
||
@inproceedings{DM14c,
|
||
author = {Deutch, Daniel and Milo, Tova and Roy, Sudeepa and Tannen, Val},
|
||
booktitle = {ICDT},
|
||
pages = {201--212},
|
||
title = {Circuits for Datalog Provenance},
|
||
year = {2014}
|
||
}
|
||
|
||
@inproceedings{bahar-93-al,
|
||
author = {R. Iris Bahar and Erica A. Frohm and Charles M. Gaona and Gary
|
||
D. Hachtel and Enrico Macii and Abelardo Pardo and Fabio
|
||
Somenzi},
|
||
booktitle = {IEEE CAD},
|
||
title = {Algebraic Decision Diagrams and Their Applications},
|
||
year = {1993}
|
||
}
|
||
|
||
@inproceedings{gogate-13-smp,
|
||
author = {Vibhav Gogate and Pedro M. Domingos},
|
||
booktitle = {UAI},
|
||
title = {Structured Message Passing},
|
||
year = {2013}
|
||
}
|
||
|
||
@article{chen-10-cswssr,
|
||
author = {Hubie Chen and Martin Grohe},
|
||
journal = {J. Comput. Syst. Sci.},
|
||
number = {8},
|
||
pages = {847--860},
|
||
title = {Constraint Satisfaction With Succinctly Specified Relations},
|
||
volume = {76},
|
||
year = {2010}
|
||
}
|
||
|
||
@inproceedings{GL16,
|
||
author = {Paolo Guagliardo and
|
||
Leonid Libkin},
|
||
booktitle = {PODS},
|
||
title = {Making SQL Queries Correct on Incomplete Databases: A Feasibility
|
||
Study},
|
||
year = {2016}
|
||
}
|
||
|
||
@inproceedings{jampani2008mcdb,
|
||
author = {Jampani, Ravi and Xu, Fei and Wu, Mingxi and Perez, Luis Leopoldo and Jermaine, Christopher and Haas, Peter J},
|
||
booktitle = {SIGMOD},
|
||
title = {MCDB: a monte carlo approach to managing uncertain data},
|
||
year = {2008}
|
||
}
|
||
|
||
|
||
@article{yang:2015:pvldb:lenses,
|
||
author = {Yang, Ying and Meneghetti, Niccolò and Fehling, Ronny and Liu, Zhen Hua and Gawlick, Dieter and Kennedy, Oliver},
|
||
title = {Lenses: An On-Demand Approach to ETL},
|
||
journal = {PVLDB},
|
||
volume = {8},
|
||
number = {12},
|
||
year = {2015},
|
||
pages = {1578--1589}
|
||
}
|
||
|
||
@article{factorized-db,
|
||
author = {Dan Olteanu and
|
||
Maximilian Schleich},
|
||
journal = {SIGMOD Rec.},
|
||
number = {2},
|
||
pages = {5--16},
|
||
title = {Factorized Databases},
|
||
volume = {45},
|
||
year = {2016}
|
||
}
|
||
|
||
@article{virgi-survey,
|
||
author = {Virginia Vassilevska Williams},
|
||
title = {Some Open Problems in Fine-Grained Complexity},
|
||
journal = {{SIGACT} News},
|
||
volume = {49},
|
||
number = {4},
|
||
pages = {29--35},
|
||
year = {2018},
|
||
url = {https://doi.org/10.1145/3300150.3300158},
|
||
doi = {10.1145/3300150.3300158},
|
||
timestamp = {Tue, 18 Dec 2018 15:19:27 +0100},
|
||
biburl = {https://dblp.org/rec/journals/sigact/Williams18.bib},
|
||
bibsource = {dblp computer science bibliography, https://dblp.org}
|
||
}
|
||
|
||
@inproceedings{param-comp,
|
||
title={Parameterized Complexity Theory},
|
||
author={J{\"o}rg Flum and Martin Grohe},
|
||
booktitle={Texts in Theoretical Computer Science. An EATCS Series},
|
||
year={2006}
|
||
}
|
||
|
||
|
||
@book{DBLP:books/daglib/0020812,
|
||
author = {Hector Garcia{-}Molina and
|
||
Jeffrey D. Ullman and
|
||
Jennifer Widom},
|
||
title = {Database Systems - The Complete Book {(2.} ed.)},
|
||
publisher = {Pearson Education},
|
||
year = {2009}
|
||
}
|
||
|
||
|
||
|
||
|
||
@article{DBLP:journals/jal/KarpLM89,
|
||
author = {Richard M. Karp and
|
||
Michael Luby and
|
||
Neal Madras},
|
||
title = {Monte-Carlo Approximation Algorithms for Enumeration Problems},
|
||
journal = {J. Algorithms},
|
||
volume = {10},
|
||
number = {3},
|
||
pages = {429--448},
|
||
year = {1989}
|
||
}
|
||
|
||
|
||
@inproceedings{ajar,
|
||
author = {Manas R. Joglekar and
|
||
Rohan Puttagunta and
|
||
Christopher R{\'{e}}},
|
||
editor = {Tova Milo and
|
||
Wang{-}Chiew Tan},
|
||
title = {{AJAR:} Aggregations and Joins over Annotated Relations},
|
||
booktitle = {Proceedings of the 35th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium on Principles
|
||
of Database Systems, {PODS} 2016, San Francisco, CA, USA, June 26
|
||
- July 01, 2016},
|
||
pages = {91--106},
|
||
publisher = {{ACM}},
|
||
year = {2016},
|
||
url = {https://doi.org/10.1145/2902251.2902293},
|
||
doi = {10.1145/2902251.2902293},
|
||
timestamp = {Tue, 06 Nov 2018 16:58:02 +0100},
|
||
biburl = {https://dblp.org/rec/conf/pods/JoglekarPR16.bib},
|
||
bibsource = {dblp computer science bibliography, https://dblp.org}
|
||
}
|
||
|
||
@book{graetzer-08-un,
|
||
author = {Gr{\"a}tzer, George},
|
||
title = {Universal algebra},
|
||
year = 2008,
|
||
publisher = {Springer Science \& Business Media}
|
||
}
|
||
|
||
@article{AGM,
|
||
author = {Albert Atserias and
|
||
Martin Grohe and
|
||
D{\'{a}}niel Marx},
|
||
title = {Size Bounds and Query Plans for Relational Joins},
|
||
journal = {{SIAM} J. Comput.},
|
||
volume = {42},
|
||
number = {4},
|
||
pages = {1737--1767},
|
||
year = {2013},
|
||
url = {https://doi.org/10.1137/110859440},
|
||
doi = {10.1137/110859440},
|
||
timestamp = {Thu, 08 Jun 2017 08:59:24 +0200},
|
||
biburl = {https://dblp.org/rec/journals/siamcomp/AtseriasGM13.bib},
|
||
bibsource = {dblp computer science bibliography, https://dblp.org}
|
||
}
|
||
|
||
|
||
|
||
@article{DBLP:journals/vldb/SaRR0W0Z17,
|
||
author = {Christopher De Sa and
|
||
Alexander Ratner and
|
||
Christopher R{\'{e}} and
|
||
Jaeho Shin and
|
||
Feiran Wang and
|
||
Sen Wu and
|
||
Ce Zhang},
|
||
title = {Incremental knowledge base construction using DeepDive},
|
||
journal = {{VLDB} J.},
|
||
volume = {26},
|
||
number = {1},
|
||
pages = {81--105},
|
||
year = {2017}
|
||
}
|
||
|
||
|
||
|
||
@article{DBLP:journals/pvldb/RekatsinasCIR17,
|
||
author = {Theodoros Rekatsinas and
|
||
Xu Chu and
|
||
Ihab F. Ilyas and
|
||
Christopher R{\'{e}}},
|
||
title = {HoloClean: Holistic Data Repairs with Probabilistic Inference},
|
||
journal = {Proc. {VLDB} Endow.},
|
||
volume = {10},
|
||
number = {11},
|
||
pages = {1190--1201},
|
||
year = {2017}
|
||
}
|
||
|
||
|
||
|
||
@article{DBLP:journals/pvldb/BeskalesIG10,
|
||
author = {George Beskales and
|
||
Ihab F. Ilyas and
|
||
Lukasz Golab},
|
||
title = {Sampling the Repairs of Functional Dependency Violations under Hard
|
||
Constraints},
|
||
journal = {Proc. {VLDB} Endow.},
|
||
volume = {3},
|
||
number = {1},
|
||
pages = {197--207},
|
||
year = {2010}
|
||
}
|
||
|
||
|
||
|
||
@article{DBLP:journals/tods/OlteanuS16,
|
||
author = {Dan Olteanu and
|
||
Sebastiaan J. van Schaik},
|
||
title = {ENFrame: {A} Framework for Processing Probabilistic Data},
|
||
journal = {{ACM} Trans. Database Syst.},
|
||
volume = {41},
|
||
number = {1},
|
||
pages = {3:1--3:44},
|
||
year = {2016}
|
||
}
|
||
|
||
|
||
|
||
@inproceedings{DBLP:conf/sigmod/GaoLPJ17,
|
||
author = {Zekai J. Gao and
|
||
Shangyu Luo and
|
||
Luis Leopoldo Perez and
|
||
Chris Jermaine},
|
||
title = {The {BUDS} Language for Distributed Bayesian Machine Learning},
|
||
booktitle = {{SIGMOD} Conference},
|
||
pages = {961--976},
|
||
publisher = {{ACM}},
|
||
year = {2017}
|
||
}
|
||
|
||
|
||
|
||
@inproceedings{DBLP:conf/sigmod/CaiVPAHJ13,
|
||
author = {Zhuhua Cai and
|
||
Zografoula Vagena and
|
||
Luis Leopoldo Perez and
|
||
Subramanian Arumugam and
|
||
Peter J. Haas and
|
||
Christopher M. Jermaine},
|
||
title = {Simulation of database-valued markov chains using SimSQL},
|
||
booktitle = {{SIGMOD} Conference},
|
||
pages = {637--648},
|
||
publisher = {{ACM}},
|
||
year = {2013}
|
||
}
|
||
|
||
|
||
|
||
@inproceedings{kumari:2016:qdb:communicating,
|
||
author = {Kumari, Poonam and Achmiz, Said and Kennedy, Oliver},
|
||
title = {Communicating Data Quality in On-Demand Curation},
|
||
booktitle = {QDB},
|
||
year = {2016}
|
||
}
|
||
|
||
|
||
|
||
@inproceedings{feng:2021:sigmod:efficient,
|
||
author = {Feng, Su and Glavic, Boris and Huber, Aaron and Kennedy, Oliver},
|
||
title = {Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds},
|
||
booktitle = {SIGMOD},
|
||
year = {2021}
|
||
}
|
||
|
||
@article{eth,
|
||
title = {Which Problems Have Strongly Exponential Complexity?},
|
||
journal = {Journal of Computer and System Sciences},
|
||
volume = {63},
|
||
number = {4},
|
||
pages = {512-530},
|
||
year = {2001},
|
||
issn = {0022-0000},
|
||
doi = {https://doi.org/10.1006/jcss.2001.1774},
|
||
url = {https://www.sciencedirect.com/science/article/pii/S002200000191774X},
|
||
author = {Russell Impagliazzo and Ramamohan Paturi and Francis Zane},
|
||
abstract = {For several NP-complete problems, there have been a progression of better but still exponential algorithms. In this paper, we address the relative likelihood of sub-exponential algorithms for these problems. We introduce a generalized reduction that we call Sub-exponential Reduction Family (SERF) that preserves sub-exponential complexity. We show that Circuit-SAT is SERF-complete for all NP-search problems, and that for any fixed k⩾3, k-SAT, k-Colorability, k-Set Cover, Independent Set, Clique, and Vertex Cover, are SERF-complete for the class SNP of search problems expressible by second-order existential formulas whose first-order part is universal. In particular, sub-exponential complexity for any one of the above problems implies the same for all others. We also look at the issue of proving strongly exponential lower bounds for AC0, that is, bounds of the form 2Ω(n). This problem is even open for depth-3 circuits. In fact, such a bound for depth-3 circuits with even limited (at most nε) fan-in for bottom-level gates would imply a nonlinear size lower bound for logarithmic depth circuits. We show that with high probability even random degree 2 GF(2) polynomials require strongly exponential size for Σk3 circuits for k=o(loglogn). We thus exhibit a much smaller space of 2O(n2) functions such that almost every function in this class requires strongly exponential size Σk3 circuits. As a corollary, we derive a pseudorandom generator (requiring O(n2) bits of advice) that maps n bits into a larger number of bits so that computing parity on the range is hard for Σk3 circuits. Our main technical lemma is an algorithm that, for any fixed ε>0, represents an arbitrary k-CNF formula as a disjunction of 2εnk-CNF formulas that are sparse, that is, each disjunct has O(n) clauses.}
|
||
}
|
||
|