Ali Çivril
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.
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”.