Search results for "3SUM"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
124	Mihai Patrascu	Towards polynomial lower bounds for dynamic problems.	STOC	2010	DBLP DOI BibTeX RDF	3SUM, lower bounds, dynamic data structures
102	Kuan-Yu Chen, Ping-Hui Hsu, Kun-Mao Chao	Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard.	CPM	2009	DBLP DOI BibTeX RDF	3sum, wildcard matching, k-mismatches, alignment, run-length encoding
78	Ilya Baran, Erik D. Demaine, Mihai Patrascu	Subquadratic Algorithms for 3SUM.	Algorithmica	2008	DBLP DOI BibTeX RDF	3SUM, Randomization, Word RAM
76	Esther Ezra, Micha Sharir	Counting and representing intersections among triangles in three dimensions.	SCG	2004	DBLP DOI BibTeX RDF	3SUM-hard problems, counting intersections, curve-sensitive cuttings, triangles in three dimensions, arrangements
54	Timothy M. Chan	More Logarithmic-factor Speedups for 3SUM, (median, +)-convolution, and Some Geometric 3SUM-hard Problems.	ACM Trans. Algorithms	2020	DBLP DOI BibTeX RDF
54	Timothy M. Chan, Qizheng He	Reducing 3SUM to Convolution-3SUM.	SOSA	2020	DBLP DOI BibTeX RDF
54	Timothy M. Chan	More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems.	SODA	2018	DBLP DOI BibTeX RDF
51	Virginia Vassilevska, Ryan Williams 0001	Finding, minimizing, and counting weighted subgraphs.	STOC	2009	DBLP DOI BibTeX RDF	3sum, cliques, paths, subgraph isomorphism, weighted graph
51	Mostafa Nouri, Alireza Zarei, Mohammad Ghodsi	Weak Visibility of Two Objects in Planar Polygonal Scenes.	ICCSA (1)	2007	DBLP DOI BibTeX RDF	weak visibility, 3sum-hard problems, object inter-visibility, Computational geometry
51	Ilya Baran, Erik D. Demaine, Mihai Patrascu	Subquadratic Algorithms for 3SUM.	WADS	2005	DBLP DOI BibTeX RDF
27	Nick Fischer, Piotr Kaliciak, Adam Polak 0001	Deterministic 3SUM-Hardness.	ITCS	2024	DBLP DOI BibTeX RDF
27	Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir	Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision-tree model.	Comput. Geom.	2023	DBLP DOI BibTeX RDF
27	Nick Fischer, Piotr Kaliciak, Adam Polak 0001	Deterministic 3SUM-Hardness.	CoRR	2023	DBLP DOI BibTeX RDF
27	Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu	Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More.	CoRR	2023	DBLP DOI BibTeX RDF
27	Eldon Chung, Kasper Green Larsen	Stronger 3SUM-Indexing Lower Bounds.	SODA	2023	DBLP DOI BibTeX RDF
27	Ce Jin 0001, Yinzhan Xu	Removing Additive Structure in 3SUM-Based Reductions.	STOC	2023	DBLP DOI BibTeX RDF
27	Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu	Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More.	STOC	2023	DBLP DOI BibTeX RDF
27	Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu	Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV.	CoRR	2022	DBLP DOI BibTeX RDF
27	Ce Jin 0001, Yinzhan Xu	Removing Additive Structure in 3SUM-Based Reductions.	CoRR	2022	DBLP DOI BibTeX RDF
27	Eldon Chung, Kasper Green Larsen	Stronger 3SUM-Indexing Lower Bounds.	CoRR	2022	DBLP DOI BibTeX RDF
27	Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu	Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV.	STOC	2022	DBLP DOI BibTeX RDF
27	Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir	Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model.	CoRR	2021	DBLP BibTeX RDF
27	Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir	Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model.	ISAAC	2021	DBLP DOI BibTeX RDF
27	Virginia Vassilevska Williams	3SUM and Related Problems in Fine-Grained Complexity (Invited Talk).	SoCG	2021	DBLP DOI BibTeX RDF
27	Andrzej Lingas	Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism.	LAGOS	2021	DBLP DOI BibTeX RDF
27	Esther Ezra	On 3SUM-hard Problems in the Decision Tree Model.	CiE	2021	DBLP DOI BibTeX RDF
27	Andrzej Lingas	Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism.	CoRR	2020	DBLP BibTeX RDF
27	Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan	Data structures meet cryptography: 3SUM with preprocessing.	STOC	2020	DBLP DOI BibTeX RDF
27	Tsvi Kopelowitz, Ely Porat	The Strong 3SUM-INDEXING Conjecture is False.	CoRR	2019	DBLP BibTeX RDF
27	Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan	3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications.	CoRR	2019	DBLP BibTeX RDF
27	Sergio Cabello, Jean Cardinal, John Iacono, Stefan Langerman, Pat Morin, Aurélien Ooms	Encoding 3SUM.	CoRR	2019	DBLP BibTeX RDF
27	Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, Noam Solomon	Subquadratic Algorithms for Algebraic 3SUM.	Discret. Comput. Geom.	2019	DBLP DOI BibTeX RDF
27	Ari Freund 0001	Improved Subquadratic 3SUM.	Algorithmica	2017	DBLP DOI BibTeX RDF
27	Omer Gold, Micha Sharir	Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy.	ESA	2017	DBLP DOI BibTeX RDF
27	Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, Noam Solomon	Subquadratic Algorithms for Algebraic Generalizations of 3SUM.	SoCG	2017	DBLP DOI BibTeX RDF
27	Zahra Jafargholi, Emanuele Viola	3SUM, 3XOR, Triangles.	Algorithmica	2016	DBLP DOI BibTeX RDF
27	Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, Noam Solomon	Subquadratic Algorithms for Algebraic Generalizations of 3SUM.	CoRR	2016	DBLP BibTeX RDF
27	Tsvi Kopelowitz, Seth Pettie, Ely Porat	Higher Lower Bounds from the 3SUM Conjecture.	SODA	2016	DBLP DOI BibTeX RDF
27	Omer Gold, Micha Sharir	Improved Bounds for 3SUM, K-SUM, and Linear Degeneracy.	CoRR	2015	DBLP BibTeX RDF
27	Timothy M. Chan, Moshe Lewenstein	Clustered Integer 3SUM via Additive Combinatorics.	CoRR	2015	DBLP BibTeX RDF
27	Timothy M. Chan, Moshe Lewenstein	Clustered Integer 3SUM via Additive Combinatorics.	STOC	2015	DBLP DOI BibTeX RDF
27	Tsvi Kopelowitz, Seth Pettie, Ely Porat	3SUM Hardness in (Dynamic) Data Structures.	CoRR	2014	DBLP BibTeX RDF
27	Zahra Jafargholi, Emanuele Viola	3SUM, 3XOR, Triangles.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
27	Zahra Jafargholi, Emanuele Viola	3SUM, 3XOR, Triangles	CoRR	2013	DBLP BibTeX RDF
27	Gill Barequet, Sariel Har-Peled	Polygon Containment and Translational Min-Hausdorff-Distance Between Segment Sets are 3SUM-Hard.	Int. J. Comput. Geom. Appl.	2001	DBLP DOI BibTeX RDF
27	Gill Barequet, Sariel Har-Peled	Polygon-containment and Translational min-Hausdorff-Distance between segment Sets are 3SUM-hard.	SODA	1999	DBLP BibTeX RDF