Aaron Potechin

79 papers A* 24A 5Journal 48Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2026	A*	`conf`	MAX BISECTION might be harder to approximate than MAX CUT. SODA Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2026	A*	`conf`	New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. SODA Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný
2026	J	`jnl`	New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. CoRR Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný
2026	J	`jnl`	On induced subgraphs of $H(n,3)$ with maximum degree $1$. Discret. Math. Theor. Comput. Sci. Aaron Potechin, Hing Yin Tsang
2026	J	`jnl`	SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. Math. Oper. Res. Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
2025	A	`conf`	Hardness of Sampling for the Anti-Ferromagnetic Ising Model on Random Graphs. ITCS Neng Huang, Will Perkins, Aaron Potechin
2025	J	`jnl`	Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023 Special Issue. ACM Trans. Algorithms Nikhil Bansal, Eun Jung Kim, Viswanath Nagarajan, Aaron Potechin, Lars Rohwedder
2025	J	`jnl`	MAX BISECTION might be harder to approximate than MAX CUT. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2025	J	`jnl`	On the Mysteries of MAX NAE-SAT. SIAM J. Discret. Math. Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2025	A*	`conf`	Sum-of-Squares Lower Bounds for Coloring Random Graphs. STOC Aaron Potechin, Jeff Xu
2024	A*	`conf`	Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle. ICALP Aaron Potechin, Aaron Zhang
2024	J	`jnl`	Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients. CoRR Susanna F. de Rezende, Aaron Potechin, Kilian Risse
2024	J	`jnl`	Hardness of sampling for the anti-ferromagnetic Ising model on random graphs. CoRR Neng Huang, Will Perkins, Aaron Potechin
2024	J	`jnl`	Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs. CoRR Pravesh Kothari, Aaron Potechin, Jeff Xu
2024	A*	`conf`	Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. STOC Pravesh K. Kothari, Aaron Potechin, Jeff Xu
2024	A*	`conf`	Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis. FOCS Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, Aaron Potechin
2024	J	`jnl`	Sum-of-squares lower bounds for Non-Gaussian Component Analysis. CoRR Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, Aaron Potechin
2023	A*	`conf`	Clique Is Hard on Average for Unary Sherali-Adams. FOCS Susanna F. de Rezende, Aaron Potechin, Kilian Risse
2023	J	`jnl`	Ellipsoid Fitting Up to a Constant. CoRR Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu
2023	A*	`conf`	Ellipsoid Fitting up to a Constant. ICALP Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu
2023	A*	`conf`	Near-optimal fitting of ellipsoids to random points. COLT Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein
2023	A*	`conf`	Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2023	A*	`conf`	Sum-of-Squares Lower Bounds for Densest k-Subgraph. STOC Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu
2023	J	`jnl`	Sum-of-Squares Lower Bounds for Densest k-Subgraph. CoRR Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu
2022	A	`conf`	Almost-Orthogonal Bases for Inner Product Polynomials. ITCS Chris Jones, Aaron Potechin
2022	J	`jnl`	Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle. CoRR Aaron Potechin, Aaron Zhang
2022	A*	`conf`	Expander Random Walks: The General Case and Limitations. ICALP Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
2022	J	`jnl`	Separating MAX 2-AND, MAX DI-CUT and MAX CUT. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2022	A*	`conf`	Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis. NeurIPS Aaron Potechin, Goutham Rajendran
2021	J	`jnl`	Almost-Orthogonal Bases for Inner Product Polynomials. CoRR Chris Jones, Aaron Potechin
2021	J	`jnl`	Expander Random Walks: The General Case and Limitations. Electron. Colloquium Comput. Complex. Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
2021	A*	`conf`	On the Mysteries of MAX NAE-SAT. SODA Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2021	A*	`conf`	SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. ICALP Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
2021	J	`jnl`	SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization. CoRR Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
2021	A*	`conf`	Sum-of-Squares Lower Bounds for Sparse Independent Set. FOCS Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
2021	J	`jnl`	Sum-of-Squares Lower Bounds for Sparse Independent Set. CoRR Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
2020	J	`jnl`	Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS. CoRR Bohdan Kivva, Aaron Potechin
2020	J	`jnl`	Lengths of words accepted by nondeterministic finite automata. Inf. Process. Lett. Aaron Potechin, Jeffrey O. Shallit
2020	J	`jnl`	Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. CoRR Aaron Potechin, Goutham Rajendran
2020	—	`conf`	On the Approximability of Presidential Type Predicates. APPROX-RANDOM Neng Huang, Aaron Potechin
2020	J	`jnl`	On the Mysteries of MAX NAE-SAT. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2020	A	`conf`	Sum of Squares Bounds for the Ordering Principle. CCC Aaron Potechin
2020	A*	`conf`	Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. FOCS Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran
2020	J	`jnl`	Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. CoRR Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran
2020	J	`jnl`	The Spectrum of the Singular Values of Z-Shaped Graph Matrices. CoRR Wenjun Cai, Aaron Potechin
2019	J	`jnl`	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM J. Comput. Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
2019	J	`jnl`	On the Approximability of Presidential Type Predicates. CoRR Neng Huang, Aaron Potechin
2019	A*	`conf`	On the approximation resistance of balanced linear threshold functions. STOC Aaron Potechin
2019	A	`conf`	Sum of Squares Lower Bounds from Symmetry and a Good Story. ITCS Aaron Potechin
2018	J	`jnl`	Lengths of Words Accepted by Nondeterministic Finite Automata. CoRR Aaron Potechin, Jeffrey O. Shallit
2018	J	`jnl`	On the Approximation Resistance of Balanced Linear Threshold Functions. CoRR Aaron Potechin
2018	J	`jnl`	Sum of squares bounds for the total ordering principle. CoRR Aaron Potechin
2017	A	`conf`	A Note on Amortized Branching Program Complexity. CCC Aaron Potechin
2017	J	`jnl`	A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation. CoRR Aaron Potechin, Liu Yang
2017	J	`jnl`	Bounds on Monotone Switching Networks for Directed Connectivity. J. ACM Aaron Potechin
2017	A*	`conf`	Exact tensor completion with sum-of-squares. COLT Aaron Potechin, David Steurer
2017	J	`jnl`	Exact tensor completion with sum-of-squares. CoRR Aaron Potechin, David Steurer
2017	J	`jnl`	Sum of squares lower bounds from symmetry and a good story. CoRR Aaron Potechin
2017	A*	`conf`	The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2017	J	`jnl`	The power of sum-of-squares for detecting hidden structures. CoRR Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2016	A*	`conf`	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
2016	J	`jnl`	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. CoRR Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
2016	J	`jnl`	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Electron. Colloquium Comput. Complex. Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
2016	J	`jnl`	A Note on Amortized Space Complexity. CoRR Aaron Potechin
2016	—	`conf`	Bounds on the Norms of Uniform Low Degree Graph Matrices. APPROX-RANDOM Dhruv Medarametla, Aaron Potechin
2015	J	`jnl`	SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four. CoRR Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
2015	A*	`conf`	Sum-of-squares Lower Bounds for Planted Clique. STOC Raghu Meka, Aaron Potechin, Avi Wigderson
2015	J	`jnl`	Sum-of-squares lower bounds for planted clique. CoRR Raghu Meka, Aaron Potechin, Avi Wigderson
2014	J	`jnl`	Tight Bounds for Monotone Switching Networks via Fourier Analysis. Theory Comput. Siu Man Chan, Aaron Potechin
2013	J	`jnl`	Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees CoRR Joshua Brakensiek, Aaron Potechin
2013	J	`jnl`	Improved upper and lower bound techniques for monotone switching networks for directed connectivity CoRR Aaron Potechin
2012	J	`jnl`	Tight Bounds for Monotone Switching Networks via Fourier Analysis. Electron. Colloquium Comput. Complex. Siu Man Chan, Aaron Potechin
2012	A*	`conf`	Tight bounds for monotone switching networks via fourier analysis. STOC Siu Man Chan, Aaron Potechin
2011	J	`jnl`	Monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks CoRR Aaron Potechin
2010	A*	`conf`	Bounds on Monotone Switching Networks for Directed Connectivity. FOCS Aaron Potechin
2009	J	`jnl`	Bounds on Monotone Switching Networks for Directed Connectivity. Electron. Colloquium Comput. Complex. Aaron Potechin
2009	J	`jnl`	Bounds on monotone switching networks for directed connectivity CoRR Aaron Potechin
2008	J	`jnl`	Maximal caps in AG (6, 3). Des. Codes Cryptogr. Aaron Potechin