Ali Çivril

Türkçe sayfa

I am an Associate Professor at Istinye University, Computer Engineering Department, Istanbul, Turkey.


Research Interests:

I am broadly interested in theoretical computer science, and currently doing research on approximation algorithms and scheme-theoretic approach to computational complexity.

Google Scholar page

Unpublished Manuscripts:

- 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. Approximation of Steiner Forest via the Bidirected Cut Relaxation, Journal of Combinatorial Optimization, 38(4): 1196-1212, 2019. pdf

- 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”.