Computational complexity of linear algebra problems with exponential size and real entries실수에서의 지수 크기 선형대수학 문제의 계산 복잡도

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 253
  • Download : 0
DC FieldValueLanguage
dc.contributor.advisorZiegler, Martin-
dc.contributor.advisor마틴 지글러-
dc.contributor.authorKoswara, Ivan Adrian-
dc.date.accessioned2022-04-27T19:31:55Z-
dc.date.available2022-04-27T19:31:55Z-
dc.date.issued2021-
dc.identifier.urihttp://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=948475&flag=dissertationen_US
dc.identifier.urihttp://hdl.handle.net/10203/296109-
dc.description학위논문(석사) - 한국과학기술원 : 전산학부, 2021.2,[i, 30 p. :]-
dc.description.abstractExponential-size problems have not been investigated very well in complexity theory even though they appear in several applications. For example, approximating the solution of a partial differential equation requires one to raise an exponential-size matrix to a large power. We formally define linear algebra problems when the input vectors and matrices have size that is exponential in a parameter and have real number entries. We also investigate the computational complexity of these problems. We show that computing exponential-size inner product is in $\#\mathsf{P}$ and computing exponential-size matrix powering is in $\mathsf{FPSPACE}$, and these are both optimal. Furthermore, inspired from the partial differential equation motivation, we show some matrices can be converted into polynomials, and that computing polynomial powering is in $\#\mathsf{P}$, improving the matrix powering result for these matrices. We also show that some cases of polynomial powering are in $\mathsf{FP}$ with novel methods, and computing (not exponential-size) inner product and matrix powering can be done in sublinear space.-
dc.languageeng-
dc.publisher한국과학기술원-
dc.subjectComputational complexity▼aExponential-size problem▼aExact real computation-
dc.subject계산복잡도▼a지수 크기 문제▼a정확한 실수 계산-
dc.titleComputational complexity of linear algebra problems with exponential size and real entries-
dc.title.alternative실수에서의 지수 크기 선형대수학 문제의 계산 복잡도-
dc.typeThesis(Master)-
dc.identifier.CNRN325007-
dc.description.department한국과학기술원 :전산학부,-
dc.contributor.alternativeauthor코스아라 이반 아드리안-
Appears in Collection
CS-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0