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:
9 A. Çivril. 3/2-Approximation for the Matching Augmentation Problem, 2024. pdf
8 A. Çivril. 9/7-Approximation for Two-Edge-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
Bu, hesapsal karmaşıklığa şema-kuramsal yaklaşımı ortaya koyan
makale olup P ve NP problemini çözmektedir. 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 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ış Çalışmalar:
- A. Çivril.
A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem, Theoretical Computer Science, 943: 121-130,
2023.
Not: Bu makale geri çekildi. Doğru ve daha basit bir algoritma
için lütfen 5 numaralı yayınlanmamış çalışmaya bakınız.
- 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