Ali Çivril


Türkçe sayfa

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

CV-Eng
CV-Tr

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:

9 A. Çivril. 3/2-Approximation for the Forest Augmentation Problem, 2024. pdf

8 A. Çivril. 9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity, 2024. pdf

7 A. Çivril, M. Mirza Biçer, B. Tahsin Tunca and M. Yasin Kangal. An Improved Integrality Gap for Steiner Tree, 2023. pdf

6 A. Çivril. 4/3-Approximation of Graphic TSP, 2023. pdf

5 A. Çivril. A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph an 2-Vertex-Connected Spanning Subgraph, 2023. pdf

4 A. Çivril. Scheme-theoretic Approach to Computational Complexity IV. A New Perspective on Hardness of Approximation, 2023. pdf

3 A. Çivril. Scheme-theoretic Approach to Computational Complexity III. SETH, 2023. pdf

2 A. Çivril. Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over C, R, and Z, 2023. pdf

1 A. Çivril. Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP, 2023. 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
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.


Published Work:

- A. Çivril. A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem, Theoretical Computer Science, 943: 121-130, 2023.

         Note: This paper is retracted. Please see the unpublished manuscript 5 for a correct and simpler algorithm.

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