Остановите войну!
for scientists:
default search action
Alexander A. Sherstov
Person information
- affiliation: University of California, Los Angeles, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2023
- [j32]Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. SIAM J. Comput. 52(2): 525-567 (2023) - 2021
- [j31]Alexander A. Sherstov:
The hardest halfspace. Comput. Complex. 30(2): 11 (2021) - [j30]Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov:
Quantum communication complexity of distribution testing. Quantum Inf. Comput. 21(15&16): 1261-1273 (2021) - 2020
- [j29]Alexander A. Sherstov:
Algorithmic Polynomials. SIAM J. Comput. 49(6): 1173-1231 (2020) - [j28]Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. ACM Trans. Comput. Theory 12(4): 26:1-26:28 (2020) - 2019
- [j27]Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. IEEE Trans. Inf. Theory 65(10): 5971-6000 (2019) - 2018
- [j26]Alexander A. Sherstov:
Compressing Interactive Communication Under Product Distributions. SIAM J. Comput. 47(2): 367-419 (2018) - [j25]Alexander A. Sherstov:
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. SIAM J. Comput. 47(5): 1809-1857 (2018) - [j24]Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. SIAM J. Comput. 47(6): 2362-2434 (2018) - [j23]Alexander A. Sherstov:
On Multiparty Communication with Large versus Unbounded Error. Theory Comput. 14(1): 1-17 (2018) - 2016
- [j22]Alexander A. Sherstov:
The Multiparty Communication Complexity of Set Disjointness. SIAM J. Comput. 45(4): 1450-1489 (2016) - 2014
- [j21]Alexander A. Sherstov:
Communication Lower Bounds Using Directional Derivatives. J. ACM 61(6): 34:1-34:71 (2014) - 2013
- [j20]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Comb. 33(1): 73-96 (2013) - [j19]Alexander A. Sherstov:
The Intersection of Two Halfspaces Has High Threshold Degree. SIAM J. Comput. 42(6): 2329-2374 (2013) - [j18]Alexander A. Sherstov:
Making Polynomials Robust to Noise. Theory Comput. 9: 593-615 (2013) - [j17]Alexander A. Sherstov:
Approximating the AND-OR Tree. Theory Comput. 9: 653-663 (2013) - 2012
- [j16]Alexander A. Sherstov:
Strong Direct Product Theorems for Quantum Communication and Query Complexity. SIAM J. Comput. 41(5): 1122-1165 (2012) - [j15]Alexander A. Sherstov:
The Communication Complexity of Gap Hamming Distance. Theory Comput. 8(1): 197-208 (2012) - 2011
- [j14]Alexander A. Sherstov:
The unbounded-error communication complexity of symmetric functions. Comb. 31(5): 583-614 (2011) - [j13]Alexander A. Sherstov:
The Pattern Matrix Method. SIAM J. Comput. 40(6): 1969-2000 (2011) - 2010
- [j12]Alexander A. Sherstov:
Communication Complexity Under Product and Nonproduct Distributions. Comput. Complex. 19(1): 135-150 (2010) - [j11]Adam R. Klivans, Alexander A. Sherstov:
Lower Bounds for Agnostic Learning via Approximate Rank. Comput. Complex. 19(4): 581-604 (2010) - [j10]Alexander A. Sherstov:
On quantum-classical equivalence for composed communication problems. Quantum Inf. Comput. 10(5&6): 435-455 (2010) - [j9]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC0. SIAM J. Comput. 39(5): 1833-1855 (2010) - [j8]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. Theory Comput. 6(1): 227-245 (2010) - 2009
- [j7]Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Comput. Complex. 18(2): 219-247 (2009) - [j6]Adam R. Klivans, Alexander A. Sherstov:
Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci. 75(1): 2-12 (2009) - [j5]Alexander A. Sherstov:
SeparatingAC0 from Depth-2 Majority Circuits. SIAM J. Comput. 38(6): 2113-2129 (2009) - 2008
- [j4]Alexander A. Sherstov:
Halfspace Matrices. Comput. Complex. 17(2): 149-178 (2008) - [j3]Alexander A. Sherstov:
Communication Lower Bounds Using Dual Polynomials. Bull. EATCS 95: 59-93 (2008) - 2007
- [j2]Alexander A. Sherstov:
Powering requires threshold depth 3. Inf. Process. Lett. 102(2-3): 104-107 (2007) - [j1]Adam R. Klivans, Alexander A. Sherstov:
Unconditional lower bounds for learning intersections of halfspaces. Mach. Learn. 69(2-3): 97-114 (2007)
Conference and Workshop Papers
- 2022
- [c31]Alexander A. Sherstov:
The approximate degree of DNF and CNF formulas. STOC 2022: 1194-1207 - 2021
- [c30]Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An optimal separation of randomized and Quantum query complexity. STOC 2021: 1289-1302 - 2019
- [c29]Alexander A. Sherstov, Pei Wu:
Near-optimal lower bounds on the threshold degree and sign-rank of AC0. STOC 2019: 401-412 - 2018
- [c28]Alexander A. Sherstov:
Algorithmic polynomials. STOC 2018: 311-324 - 2017
- [c27]Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. FOCS 2017: 240-251 - 2016
- [c26]Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov:
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. FOCS 2016: 1-10 - [c25]Alexander A. Sherstov:
Compressing Interactive Communication under Product Distributions. FOCS 2016: 535-544 - 2015
- [c24]Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. FOCS 2015: 431-450 - 2014
- [c23]Alexander A. Sherstov:
Communication Complexity Theory: Thirty-Five Years of Set Disjointness. MFCS (1) 2014: 24-43 - [c22]Alexander A. Sherstov:
Breaking the minsky-papert barrier for constant-depth circuits. STOC 2014: 223-232 - 2013
- [c21]Alexander A. Sherstov:
Communication lower bounds using directional derivatives. STOC 2013: 921-930 - 2012
- [c20]Alexander A. Sherstov:
The multiparty communication complexity of set disjointness. STOC 2012: 525-548 - [c19]Alexander A. Sherstov:
Making polynomials robust to noise. STOC 2012: 747-758 - 2011
- [c18]Alexander A. Sherstov:
Strong direct product theorems for quantum communication and query complexity. STOC 2011: 41-50 - 2010
- [c17]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. STOC 2010: 523-532 - 2009
- [c16]Alexander A. Sherstov:
The Intersection of Two Halfspaces Has High Threshold Degree. FOCS 2009: 343-362 - 2008
- [c15]Alexander A. Sherstov:
Communication Complexity under Product and Nonproduct Distributions. CCC 2008: 64-70 - [c14]Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. CCC 2008: 112-123 - [c13]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^O. FOCS 2008: 57-66 - [c12]Alexander A. Sherstov:
The Unbounded-Error Communication Complexity of Symmetric Functions. FOCS 2008: 384-393 - [c11]Alexander A. Sherstov:
The pattern matrix method for lower bounds on quantum communication. STOC 2008: 85-94 - 2007
- [c10]Alexander A. Sherstov:
Halfspace Matrices. CCC 2007: 83-95 - [c9]Adam R. Klivans, Alexander A. Sherstov:
A Lower Bound for Agnostically Learning Disjunctions. COLT 2007: 409-423 - [c8]Alexander A. Sherstov:
Separating AC0 from depth-2 majority circuits. STOC 2007: 294-301 - 2006
- [c7]Adam R. Klivans, Alexander A. Sherstov:
Improved Lower Bounds for Learning Intersections of Halfspaces. COLT 2006: 335-349 - [c6]Adam R. Klivans, Alexander A. Sherstov:
Cryptographic Hardness for Learning Intersections of Halfspaces. FOCS 2006: 553-562 - 2005
- [c5]Alexander A. Sherstov, Peter Stone:
Improving Action Selection in MDP's via Knowledge Transfer. AAAI 2005: 1024-1029 - [c4]Alexander A. Sherstov, Peter Stone:
Function Approximation via Tile Coding: Automating Parameter Choice. SARA 2005: 194-205 - 2004
- [c3]Alexander A. Sherstov, Peter Stone:
Three Automated Stock-Trading Agents: A Comparative Study. AMEC 2004: 173-187 - 2003
- [c2]Alexander A. Sherstov:
Distributed visualization of graph algorithms. SIGCSE 2003: 376-380 - 2002
- [c1]Michael J. Jipping, Steve Marlowe, Alexander A. Sherstov:
Using Java to design and test hardware circuits over a classroom network. SIGCSE 2002: 162-166
Informal and Other Publications
- 2022
- [i43]Alexander A. Sherstov:
The Approximate Degree of DNF and CNF Formulas. CoRR abs/2209.01584 (2022) - [i42]Alexander A. Sherstov:
The Approximate Degree of DNF and CNF Formulas. Electron. Colloquium Comput. Complex. TR22 (2022) - 2020
- [i41]Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov:
Quantum Communication Complexity of Distribution Testing. CoRR abs/2006.14870 (2020) - [i40]Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. CoRR abs/2008.10223 (2020) - [i39]Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i38]Alexander A. Sherstov, Pei Wu:
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. CoRR abs/1901.00988 (2019) - [i37]Alexander A. Sherstov:
The Hardest Halfspace. CoRR abs/1902.01765 (2019) - [i36]Alexander A. Sherstov, Justin Thaler:
Vanishing-Error Approximate Degree and QMA Complexity. CoRR abs/1909.07498 (2019) - [i35]Alexander A. Sherstov:
The hardest halfspace. Electron. Colloquium Comput. Complex. TR19 (2019) - [i34]Alexander A. Sherstov, Justin Thaler:
Vanishing-Error Approximate Degree and QMA Complexity. Electron. Colloquium Comput. Complex. TR19 (2019) - [i33]Alexander A. Sherstov, Pei Wu:
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i32]Alexander A. Sherstov:
Algorithmic Polynomials. CoRR abs/1801.04607 (2018) - [i31]Alexander A. Sherstov:
Algorithmic polynomials. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i30]Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. CoRR abs/1711.10661 (2017) - [i29]Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. Electron. Colloquium Comput. Complex. TR17 (2017) - [i28]Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i27]Alexander A. Sherstov:
Compressing interactive communication under product distributions. Electron. Colloquium Comput. Complex. TR16 (2016) - [i26]Alexander A. Sherstov:
On multiparty communication with large versus unbounded error. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i25]Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i24]Alexander A. Sherstov:
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i23]Alexander A. Sherstov:
Communication Lower Bounds Using Directional Derivatives. Electron. Colloquium Comput. Complex. TR13 (2013) - [i22]Alexander A. Sherstov:
Approximating the AND-OR Tree. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i21]Alexander A. Sherstov:
Making Polynomials Robust to Noise. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i20]Alexander A. Sherstov:
Strong Direct Product Theorems for Quantum Communication and Query Complexity. Electron. Colloquium Comput. Complex. TR11 (2011) - [i19]Alexander A. Sherstov:
The Communication Complexity of Gap Hamming Distance. Electron. Colloquium Comput. Complex. TR11 (2011) - [i18]Alexander A. Sherstov:
The Multiparty Communication Complexity of Set Disjointness. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i17]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. CoRR abs/1004.0817 (2010) - [i16]Alexander A. Sherstov:
Strong direct product theorems for quantum communication and query complexity. CoRR abs/1011.4935 (2010) - [i15]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. TR10 (2010) - [i14]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i13]Alexander A. Sherstov:
On Quantum-Classical Equivalence for Composed Communication Problems. CoRR abs/0906.1399 (2009) - [i12]Alexander A. Sherstov:
The Pattern Matrix Method (Journal Version). CoRR abs/0906.4291 (2009) - [i11]Alexander A. Sherstov:
The intersection of two halfspaces has high threshold degree. CoRR abs/0910.1862 (2009) - [i10]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. CoRR abs/0910.4224 (2009) - [i9]Alexander A. Sherstov:
The intersection of two halfspaces has high threshold degree. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i8]Alexander A. Sherstov:
Communication Lower Bounds Using Dual Polynomials. CoRR abs/0805.2135 (2008) - [i7]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. TR08 (2008) - [i6]Alexander A. Sherstov:
Communication Lower Bounds Using Dual Polynomials. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [i5]Alexander A. Sherstov:
Communication Complexity under Product and Nonproduct Distributions. Electron. Colloquium Comput. Complex. TR07 (2007) - [i4]Alexander A. Sherstov:
The Pattern Matrix Method for Lower Bounds on Quantum Communication. Electron. Colloquium Comput. Complex. TR07 (2007) - [i3]Alexander A. Sherstov:
Unbounded-Error Communication Complexity of Symmetric Functions. Electron. Colloquium Comput. Complex. TR07 (2007) - [i2]Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i1]Adam R. Klivans, Alexander A. Sherstov:
Cryptographic Hardness Results for Learning Intersections of Halfspaces. Electron. Colloquium Comput. Complex. TR06 (2006)
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-04-25 05:48 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint