default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJoshua Brakensiek
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
[j10]Joshua Brakensiek, Sami Davies:
Robust Factorizations and Colorings of Tensor Graphs. SIAM J. Discret. Math. 38(1): 883-916 (2024)- [j9]Joshua Brakensiek
, Manik Dhar, Sivakanth Gopi:
Improved Field Size Bounds for Higher Order MDS Codes. IEEE Trans. Inf. Theory 70(10): 6950-6960 (2024) - [c22]Joshua Brakensiek, Neng Huang, Uri Zwick:
Tight approximability of MAX 2-SAT and relatives, under UGC. SODA 2024: 1328-1344 - [c21]Joshua Brakensiek, Manik Dhar, Sivakanth Gopi:
Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. STOC 2024: 728-739 - [c20]Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang:
AG Codes Achieve List Decoding Capacity over Constant-Sized Fields. STOC 2024: 740-751 - [i35]Joshua Brakensiek, Manik Dhar, Jiyang Gao, Sivakanth Gopi, Matt Larson:
Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes. CoRR abs/2405.00778 (2024) - 2023
- [j8]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. TheoretiCS 2 (2023) - [c19]Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS 2023: 234-252 - [c18]Joshua Brakensiek, Manik Dhar, Sivakanth Gopi:
Improved Field Size Bounds for Higher Order MDS Codes. ISIT 2023: 1243-1248 - [c17]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
SDPs and Robust Satisfiability of Promise CSP. STOC 2023: 609-622 - [c16]Joshua Brakensiek, Sivakanth Gopi, Visu Makam:
Generic Reed-Solomon Codes Achieve List-Decoding Capacity. STOC 2023: 1488-1501 - [i34]Joshua Brakensiek, Manik Dhar, Sivakanth Gopi:
Generalized GM-MDS: Polynomial Codes are Higher Order MDS. CoRR abs/2310.12888 (2023) - [i33]Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang:
AG codes achieve list decoding capacity over contant-sized fields. CoRR abs/2310.12898 (2023) - [i32]Joshua Brakensiek, Neng Huang, Uri Zwick:
Tight approximability of MAX 2-SAT and relatives, under UGC. CoRR abs/2310.12911 (2023) - 2022
- [j7]Joshua Brakensiek, Marijn Heule, John Mackey, David E. Narváez:
The Resolution of Keller's Conjecture. J. Autom. Reason. 66(3): 277-300 (2022) - [j6]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. SIAM J. Comput. 51(3): 577-626 (2022) - [j5]Joshua Brakensiek, Sivakanth Gopi, Visu Makam:
Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes. IEEE Trans. Inf. Theory 68(11): 7125-7140 (2022) - [i31]Joshua Brakensiek, Sivakanth Gopi, Visu Makam:
Generic Reed-Solomon codes achieve list-decoding capacity. CoRR abs/2206.05256 (2022) - [i30]Joshua Brakensiek, Sami Davies:
Robust Factorizations and Colorings of Tensor Graphs. CoRR abs/2207.08913 (2022) - [i29]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
SDPs and Robust Satisfiability of Promise CSP. CoRR abs/2211.08373 (2022) - [i28]Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. CoRR abs/2212.11191 (2022) - [i27]Joshua Brakensiek, Manik Dhar, Sivakanth Gopi:
Improved Field Size Bounds for Higher Order MDS Codes. CoRR abs/2212.11262 (2022) - 2021
- [j4]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM J. Comput. 50(6): 1663-1700 (2021) - [j3]Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Trans. Algorithms 17(3): 27:1-27:35 (2021) - [c15]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. ICALP 2021: 37:1-37:15 - [c14]Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
On the Mysteries of MAX NAE-SAT. SODA 2021: 484-503 - [i26]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. CoRR abs/2102.11854 (2021) - [i25]Joshua Brakensiek, Sivakanth Gopi, Visu Makam:
Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes. CoRR abs/2107.10822 (2021) - [i24]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j2]Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. SIAM J. Comput. 49(6): 1232-1248 (2020) - [c13]Joshua Brakensiek, Marijn Heule, John Mackey, David E. Narváez:
The Resolution of Keller's Conjecture. IJCAR (1) 2020: 48-65 - [c12]Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein:
Smoothed Complexity of 2-player Nash Equilibria. FOCS 2020: 271-282 - [c11]Joshua Brakensiek, Ray Li, Bruce Spang:
Coded trace reconstruction in a constant number of traces. FOCS 2020: 482-493 - [c10]Joshua Brakensiek, Venkatesan Guruswami:
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. SODA 2020: 297-304 - [c9]Joshua Brakensiek, Aviad Rubinstein:
Constant-factor approximation of near-linear edit distance in near-linear time. STOC 2020: 685-698 - [d1]Joshua Brakensiek, Marijn Heule, John Mackey, David E. Narváez:
The Resolution of Keller's Conjecture - Computation Logs. Zenodo, 2020
- [i23]Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein:
Smoothed Complexity of 2-player Nash Equilibria. CoRR abs/2007.10857 (2020) - [i22]Joshua Brakensiek, Moses Charikar, Aviad Rubinstein:
A Simple Sublinear Algorithm for Gap Edit Distance. CoRR abs/2007.14368 (2020) - [i21]Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
On the Mysteries of MAX NAE-SAT. CoRR abs/2009.10677 (2020) - [i20]Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [c8]Joshua Brakensiek, Venkatesan Guruswami:
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. SODA 2019: 436-455 - [c7]Joshua Brakensiek, Venkatesan Guruswami:
Bridging between 0/1 and linear programming via random walks. STOC 2019: 568-577 - [c6]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
CSPs with global modular constraints: algorithms and hardness via polynomial representations. STOC 2019: 590-601 - [i19]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. CoRR abs/1902.04740 (2019) - [i18]Joshua Brakensiek, Venkatesan Guruswami:
Bridging between 0/1 and Linear Programming via Random Walks. CoRR abs/1904.04860 (2019) - [i17]Joshua Brakensiek, Aviad Rubinstein:
Constant-factor approximation of near-linear edit distance in near-linear time. CoRR abs/1904.05390 (2019) - [i16]Joshua Brakensiek, Venkatesan Guruswami:
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. CoRR abs/1907.04383 (2019) - [i15]Joshua Brakensiek, Ray Li, Bruce Spang:
Coded trace reconstruction in a constant number of traces. CoRR abs/1908.03996 (2019) - [i14]Joshua Brakensiek, Marijn Heule, John Mackey:
The Resolution of Keller's Conjecture. CoRR abs/1910.03740 (2019) - [i13]Joshua Brakensiek, Venkatesan Guruswami:
Bridging between 0/1 and Linear Programming via Random Walks. Electron. Colloquium Comput. Complex. TR19 (2019) - [i12]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j1]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. IEEE Trans. Inf. Theory 64(5): 3403-3410 (2018) - [c5]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. SODA 2018: 1782-1801 - [i11]Joshua Brakensiek, Venkatesan Guruswami:
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. CoRR abs/1807.05194 (2018) - [i10]Joshua Brakensiek, Venkatesan Guruswami:
Combining LPs and Ring Equations via Structured Polymorphisms. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c4]Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. APPROX-RANDOM 2017: 4:1-4:20 - [c3]Joshua Brakensiek:
Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. APPROX-RANDOM 2017: 33:1-33:15 - [i9]Joshua Brakensiek:
Vertex isoperimetry and independent set stability for tensor powers of cliques. CoRR abs/1702.04432 (2017) - [i8]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. CoRR abs/1704.01937 (2017) - [i7]Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. Electron. Colloquium Comput. Complex. TR17 (2017) - [i6]Joshua Brakensiek, Venkatesan Guruswami:
A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c2]Joshua Brakensiek, Venkatesan Guruswami:
New Hardness Results for Graph and Hypergraph Colorings. CCC 2016: 14:1-14:27 - [c1]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. SODA 2016: 1884-1892 - [i5]Joshua Brakensiek, Venkatesan Guruswami:
New hardness results for graph and hypergraph colorings. Electron. Colloquium Comput. Complex. TR16 (2016) - [i4]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i3]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. CoRR abs/1507.06175 (2015) - [i2]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. Electron. Colloquium Comput. Complex. TR15 (2015) - 2013
- [i1]Joshua Brakensiek, Aaron Potechin:
Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees. CoRR abs/1301.3780 (2013)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:19 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
