Ali Çivril
Atlas Üniversitesi, Bilgisayar Mühendisliği Bölümü’nde
doçent olarak görev yapmaktayım.
CV-İng
CV-Tr
Araştırma Alanları:
En geniş manasıyla kuramsal bilgisayar bilimiyle ilgileniyor, ve şu an yaklaştırma
algoritmaları ve hesapsal karmaşıklığın şema-kuramsal yorumu üzerine araştırma
yapıyorum.
Google
Scholar sayfası
Yayınlanmamış Çalışmalar:
- A. Çivril. Scheme-theoretic Approach to Computational Complexity IV. A New
Perspective on Hardness of Approximation, 2022. pdf
- A. Çivril. An Improved Approximation
Algorithm for the Minimum 2-Vertex-Connected Spanning Subgraph Problem,
2022. pdf
- A. Çivril. 4/3-Approximation of
Graphic TSP, 2022. pdf
- A. Çivril. Scheme-theoretic Approach to Computational Complexity III. SETH, 2022. pdf
- A. Çivril. A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning
Subgraph Problem, 2022. pdf
- 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
Bu, hesapsal karmaşıklığa şema-kuramsal yaklaşımı ortaya koyan makale
olup P ve NP problemini çözmektedir. 2010-2022 arasında
geliştirilen ve bu makalede bir embriyo halinde ortaya konan teori, uzun vadede
alanı kategori-kuramsal ve cebirsel-geometrik yöntemlerle matematiğin ana
gövdesine eklemlemeyi hedeflemektedir. Özellikle konuya yabancı olanlar için
daha somut olmak adına, makalenin katkıları şu şekilde sıralanabilir:
0) Hesapsal problemlerin kategorisinde TRIVIAL problemi tanımlıyor (alan için
0’ın keşfi), ve bu kategoriden şemaların kategorisine anlamlı bir fonktör
tanımlıyor.
1) Algoritma denilen şeyi eldeki probleme karşılık gelen şemayı, TRIVIAL’i temsil
eden tek bir noktaya indirgeyen bir geometrik büzme prosedürü olarak ele
alıyor.
2) Bir problemin zaman karmaşıklığını ona karşılık gelen şemanın belli bir
alt-şemasının geometrisiyle ilişkilendiriyor.
3) 3-SAT’a karşılık gelen şemanın bağlantılı bir alt-şemasının geometrisini ele
alarak P’yi NP’den ayırıyor.
Yayınlanmış Bazı Çalışmalar:
- 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
Not: Yaroslav Shitov tarafından çok daha basit bir NP-hardness ispatı
var. Burada
- 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