I am an Associate Professor at Istinye University, Computer Engineering Department, Istanbul, Turkey.
I am broadly interested in theoretical computer science, and currently doing research on approximation algorithms and scheme-theoretic approach to computational complexity.
- A. Çivril. Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over C, R, and Z, 2021. pdf
- A. Çivril. Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP, 2021. pdf
This is the paper introducing the scheme-theoretic
approach to computational complexity, and resolving the P vs NP problem. The theory, as presented in its
embryonic form in this paper, aims in the long run to integrate the field with
the body of mainstream mathematics via category-theoretical and algebro-geometric
methods. To be more concrete especially for the uninitiated reader, the contributions of the paper can
be listed as follows:
0) It defines the TRIVIAL problem in the category of computational problems (the discovery of 0 for the field), and a meaningful functor from this category to the category of schemes.
1) It considers an algorithm as a geometric contraction procedure reducing the scheme corresponding to the problem at hand to a single point representing TRIVIAL.
2) It relates the time complexity of a problem to the geometry of a certain subscheme of the associated scheme.
3) Considering the geometry of a connected subscheme of the scheme associated to 3-SAT, it separates P and NP.
- A. Çivril. Dual Growth with
Variable Rates: An Improved Integrality Gap for Steiner Tree, 2019. pdf
Some Published Work:
- A. Çivril. Sparse Approximation is Provably Hard under Coherent Dictionaries, Journal of Computer and System Sciences, 84(1): 32-43, 2017. pdf
- A. Çivril. Column Subset Selection Problem is UG-hard, Journal of Computer and System Sciences, 80(4): 849-859, 2014. pdf
Note: There is a much simpler NP-hardness proof by Yaroslav Shitov. Here
- A. Çivril. A Note on the Hardness of Sparse Approximation, Information Processing Letters, 113(14-16):543-545, 2013. pdf
- A. Çivril and M. Magdon-Ismail. Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix, Algorithmica, 65(1): 159-176, 2013. pdf
- A. Çivril and M. Magdon-Ismail. Column Subset Selection via Sparse Approximation of SVD. Theoretical Computer Science, 421:1-14, 2012. pdf
- A. Çivril and M. Magdon-Ismail. On Selecting A Maximum Volume Sub-matrix of a Matrix and Related Problems. Theoretical Computer Science, 410(47-49):4801-4811, 2009. pdf
- Y. Koren and A. Çivril. Binary Stress Model for graph Drawing. Graph Drawing 2008, 193-205. pdf
- A. Çivril, M.
Magdon-Ismail and E. Bocek-Rivele. SSDE:
Fast Graph Drawing Using Sampled Spectral Distance Embedding. Graph Drawing 2006, 30-41. pdf
Pronunciation of name: The first letter of my name is a C with cedilla, which is to be pronounced as Ch.