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:
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: Please see the
unpublished manuscript 5 for a simpler algorithm, and a clearer analysis.
- A. Çivril.
Corrigendum to “A New Approximation Algorithm
for the Minimum 2-Edge-Connected Spanning Subgraph Problem”, Theoretical Computer Science, 963, 2023
- 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”.