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 Forest Augmentation Problem, 2024. pdf
8 A. Çivril. 9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-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