Остановите войну!
for scientists:
default search action
Jin-Yi Cai
- > Home > Persons > Jin-Yi Cai
Publications
- 2023
- [i62]Jin-Yi Cai:
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise. CoRR abs/2306.10072 (2023) - 2013
- [c99]Jin-Yi Cai:
Complexity Dichotomy for Counting Problems. LATA 2013: 1-11 - 2011
- [c92]Jin-yi Cai:
Progress in Complexity of Counting Problems. FAW-AAIM 2011: 1-3 - 2008
- [j50]Jin-yi Cai:
Holographic algorithms: guest column. SIGACT News 39(2): 51-81 (2008) - 2007
- [j48]Jin-yi Cai:
S2p is subset of ZPPNP. J. Comput. Syst. Sci. 73(1): 25-35 (2007) - 2003
- [j37]Jin-yi Cai:
A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor. Discret. Appl. Math. 126(1): 9-31 (2003) - [j36]Jin-yi Cai:
Essentially Every Unimodular Matrix Defines an Expander. Theory Comput. Syst. 36(2): 105-135 (2003) - 2002
- [c52]Jin-yi Cai:
On the Minimum Volume of a Perturbed Unit Cube. ISAAC 2002: 67-78 - 2001
- [c50]Jin-yi Cai:
On the Average-Case Hardness of CVP. FOCS 2001: 308-317 - [c49]Jin-yi Cai:
Sp2 subseteq ZPPNP. FOCS 2001: 620-629 - [i10]Jin-yi Cai:
Essentially every unimodular matrix defines an expander. Electron. Colloquium Comput. Complex. TR01 (2001) - [i9]Jin-yi Cai:
S_2p \subseteq ZPPNP. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [c47]Jin-yi Cai:
The Complexity of Some Lattice Problems. ANTS 2000: 1-32 - [c46]Jin-yi Cai:
Essentially Every Unimodular Matrix Defines and Expander. ISAAC 2000: 2-22 - 1999
- [j29]Jin-yi Cai:
A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes. Inf. Process. Lett. 69(4): 167-174 (1999) - [c44]Jin-yi Cai:
Some Recent Progress on the Complexity of Lattice Problems. CCC 1999: 158- - [c43]Jin-yi Cai:
Applications of a New Transference Theorem to Ajtai's Connection Factor. CCC 1999: 205-214 - [c42]Jin-yi Cai:
A New Transference Theorem in the Geometry of Numbers. COCOON 1999: 113-122 - [i7]Jin-yi Cai:
Some Recent Progress on the Complexity of Lattice Problems. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j22]Jin-yi Cai:
Frobenius's Degree Formula and Toda's Polynomials. Theory Comput. Syst. 31(1): 67-75 (1998) - [j21]Jin-yi Cai:
A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem. Theor. Comput. Sci. 207(1): 105-116 (1998) - [i5]Jin-yi Cai:
A new transference theorem and applications to Ajtai's connection factor. Electron. Colloquium Comput. Complex. TR98 (1998) - 1994
- [j17]Jin-yi Cai:
Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time. Int. J. Found. Comput. Sci. 5(3/4): 293-302 (1994) - 1993
- [e1]Jin-Yi Cai:
Advances In Computational Complexity Theory, Proceedings of a DIMACS Workshop, New Jersey, USA, December 3-7, 1990. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13, DIMACS/AMS 1993, ISBN 978-0-8218-6597-2 [contents] - 1992
- [c18]Jin-yi Cai:
Parallel Computation Over Hyperbolic Groups. STOC 1992: 106-115 - 1991
- [c16]Jin-yi Cai:
Computations Over Infinite Groups. FCT 1991: 22-32 - 1990
- [j8]Jin-yi Cai:
A Note on the Determinant and Permanent Problem. Inf. Comput. 84(1): 119-127 (1990) - [j7]Jin-yi Cai:
Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. Inf. Process. Lett. 36(2): 79-83 (1990) - 1989
- [j4]Jin-yi Cai:
With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. J. Comput. Syst. Sci. 38(1): 68-85 (1989) - [c12]Jin-yi Cai:
Lower Bounds for Constant Depth Circuits in the Presence of Help Bits. FOCS 1989: 532-537 - 1987
- [c4]Jin-yi Cai:
Probability One Separation of the Boolean Hierarchy. STACS 1987: 148-158 - 1986
- [b1]Jin-Yi Cai:
On Some Most Probable Separations of Complexity Classes. Cornell University, USA, 1986 - [c3]Jin-yi Cai:
With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy. SCT 1986: 104-104 - [c1]Jin-yi Cai:
With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. STOC 1986: 21-29
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-21 17:37 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint