**Ali ****Çivril**

I am an Associate Professor at Istinye 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:

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