2 citations · 2 across the 3 of their papers we have counts for
4 papers
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Sumegha Garg, Songhua He, Yuanzhi Li +2
We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix and parameters…
Query Lower Bounds for Correlation Clustering under Memory Constraints
Sumegha Garg, Songhua He, Periklis A. Papakonstantinou
This work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that…
Arbitrarily Large Labelled Random Satisfiability Formulas for Machine Learning Training
Dimitris Achlioptas, Amrit Daswaney, Periklis A. Papakonstantinou
Applying deep learning to solve real-life instances of hard combinatorial problems has tremendous potential. Research in this direction has focused on the Boolean satisfiability (S…
Width-parameterized SAT: Time-Space Tradeoffs
Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou +1
Width parameterizations of SAT, such as tree-width and path-width, enable the study of computationally more tractable and practical SAT instances. We give two simple algorithms. On…