MINA DALIRROOYFARD |  RAY LI... -  《Journal of the ACM》 - 2025,72(1) - 6.1～6.32 - 共32页

摘要：Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from...

关键词： Fine-grained complexity |  hardness of approximation |  graph diameter |  undirected graphs

Julia Chuzhoy |  Mina Dalirrooyfard... -  《14th Innovations in Theoretical Computer Science Conference: ITCS 2023, 10-13 January 2023, Cambridge, Massachusetts, USA, Part 2 of 3》 -  Innovations in Theoretical Computer Science Conference - 2023, - 38:1～38:23 - 共23页

摘要：We propose a new conjecture on hardness of 2-CSP's, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a...

关键词： Hardness of approximation |  Densest k-Subgraph

Mina Dalirrooyfard |  Virginia Vassilevska... -  《2022 IEEE 63rd Annual Symposium on Foundations of Computer Science: FOCS 2022, Denver, Colorado, USA, 31 October - 3 November 2022, [v.1]》 -  IEEE Annual Symposium on Foundations of Computer Science - 2022, - 531～542 - 共12页

摘要：The goal of the paper is to give fine-grained hardness results for the Subgraph Isomorphism (SI) problem for fixed size induced patterns H, based on the k-Clique hypothesis that the current best algor...

关键词： Computer science |  Costs |  Image edge detection

Mina Dalirrooyfard |  Ray Li... -  《IEEE 62nd Annual Symposium on Foundations of Computer Science: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 7-10 Feb. 2022, Virtual Conference, Denver, CO, USA》 -  IEEE Annual Symposium on Foundations of Computer Science - 2022, - 1021～1032 - 共12页

摘要：Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from...

关键词： Computer science |  Directed graphs |  Approximation algorithms |  Complexity theory |  Task analysis

NSTL主题词： Soundness |  undirected graph |  hardness |  Approximate |  Diameter

Mina Dalirrooyfard |  Ce Jin... -  《2022 IEEE 63rd Annual Symposium on Foundations of Computer Science: FOCS 2022, Denver, Colorado, USA, 31 October - 3 November 2022, [v.1]》 -  IEEE Annual Symposium on Foundations of Computer Science - 2022, - 290～300 - 共11页

摘要：We study the approximability of two related problems on graphs with n nodes and m edges: n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O(n) prespecified pairs, and ...

关键词： Computer science |  Fault tolerance |  Upper bound |  Additives |  Fault tolerant systems |  Approximation algorithms

Mina Dalirrooyfard |  Andrea Lincoln... -  《2020 IEEE 61st Annual Symposium on Foundations of Computer Science: IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), 16-19 Nov. 2020, Durham, NC, USA》 -  IEEE Annual Symposium on Foundations of Computer Science - 2020, - 774～785 - 共12页

摘要：The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). Prior work [Goldreich-Rothblum 2018, Boix-Adserà et al. 2019,...

关键词： Computer science |  C |  languages

NSTL主题词： new technique |  Soundness |  hardness

Mina Dalirrooyfard |  Andrea Lincoln... -  《2020 IEEE 61st Annual Symposium on Foundations of Computer Science: FOCS 2020, Durham, North Carolina, USA, 16-19 November 2020, [v.2]》 -  IEEE Annual Symposium on Foundations of Computer Science - 2020, - 774～785 - 共12页

摘要：The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). Prior work [Goldreich-Rothblum 2018, Boix-Adsera et al. 2019,...

关键词： Fine-Grained complexity |  Average-Case lower bounds |  Worst-Case to average-Case

Mina Dalirrooyfard |  Andrea Lincoln... -  《Annual ACM-SIAM Symposium on Discrete Algorithms,volume 7 of 8》 -  Annual ACM-SIAM Symposium on Discrete Algorithms - 2025, - 4613～4643 - 共31页

摘要：This work establishes conditional lower bounds for average-case parity-counting versions of the problems k-XOR, k-SUM, and k-OV. The main contribution is a set of self-reductions for the problems, pro...

Mina Dalirrooyfard |  Konstantin Makaryche...... -  《2024 International Conference on Machine Learning,Part 13 of 75》 -  International Conference on Machine Learning - 2024, - 9931～9952 - 共22页

摘要：Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the nodes so to minimize the total number of between-cluster positive and within-cluster negati...

L. Elisa Celis |  Mina Dalirrooyfard... -  《Web and Internet Economics: 13th International Conference, WINE 2017, Bangalore, India, December 17-20, 2017, Proceedings》 -  International Conference on Web and Internet Economics - 2017, - 88～102 - 共15页

摘要：We study the following question facing businesses in the world of online advertising: how should an advertising budget be spent when there are competing products? Broadly, there are two primary modes ...

NSTL主题词： Advertising as Topic |  Network |  dynamics