**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 scheme-theoretic approach to computational complexity and
approximation algorithms.

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, its
contributions 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 the final object of the category
of schemes.

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.